# Converting set of inequalities to LP

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?

• What is a "dummy variable"? Do you mean they are constants or actual (binary) optimization variables in your model? – Michal Adamaszek Nov 30 '20 at 8:10
• 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 – user760900 Nov 30 '20 at 8:13
• 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. – Michal Adamaszek Nov 30 '20 at 8:15
• ah that's embarrassing. if you would like to make that an answer, i can accept it – user760900 Nov 30 '20 at 8:17