0
$\begingroup$

I have a problem where I have a bunch of inequalities in the form:

  • $a_{1,1}b_{1,1} + a_{1,2}b_{1,2} + ... + a_{1,n}b_{1,n} > a_{2,1}b_{2,1} + a_{2,2}b_{2,2} + ... + a_{2,n}b_{2,n}$

  • $a_{2,1}b_{2,1} + a_{2,2}b_{2,2} + ... + a_{2,n}b_{2,n} > a_{3,1}b_{3,1} + a_{3,2}b_{3,2} + ... + a_{3,n}b_{3,n}$

  • $a_{1,1}b_{1,1} + a_{1,2}b_{1,2} + ... + a_{1,n}b_{1,n} < a_{3,1}b_{3,1} + a_{3,2}b_{3,2} + ... + a_{3,n}b_{3,n}$

  • etc.

I've randomly distributed the < and > signs in the inequalities for the example; they can be any of ≤, ≥, <, or >. All the b variables are dummy variables (either 0 or 1).

I want to find values of all the a variables, assuming possible given the data. This seems like a linear programming problem, but I'm struggling to convert it to one.

One further problem is that I may come to a point where there is not solution by classic linear programming (ex. the example above). In this case, I would want to find the point that is "closest" to being a valid point (think OLS error reduction). I know how to do this for linear programming (another reason I jumped to lp), but am unsure on how to do it for the problem statement above. As a side note, I plan to do this mainly computationally.

What method would I use to solve the above?

$\endgroup$
4
  • 1
    $\begingroup$ What is a "dummy variable"? Do you mean they are constants or actual (binary) optimization variables in your model? $\endgroup$ – Michal Adamaszek Nov 30 '20 at 8:10
  • $\begingroup$ They're binary data variables, so for any equation we will end up with something of the form $a_{1,1} + a_{1,3} + \dots + a_{1,n} > a_{2,3} + a_{2,7} + \dots + a_{2,n}$. The b variables are there for expository ease $\endgroup$ – user760900 Nov 30 '20 at 8:13
  • 1
    $\begingroup$ So the $b$ come as part of input? Well then you already have an LP: every constraint is a linear inequality in the $a_{i,j}$s. You can maybe move all terms to one side to get a more standard form if necessary. $\endgroup$ – Michal Adamaszek Nov 30 '20 at 8:15
  • $\begingroup$ ah that's embarrassing. if you would like to make that an answer, i can accept it $\endgroup$ – user760900 Nov 30 '20 at 8:17
0
$\begingroup$

Accepting Micheal Adamaszek's answer that he commented. It's already in LP form, just move the terms to one side to get to standard form.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.