Can a linear program have strict inequalities?

Question

In all linear programs I have seen so far, the constraints are either of types $=$, $\geq$ or $\leq$. Can we have constraints that are purely $>$ or $<$ types? If so, how do we convert it into standard form?

Answer 1

The problem with such constraints is that the feasible set is no longer closed and we might not be able to attain the optimal solution even when the optimal solution is bounded.

For problem like $a^tx < b$, you might like to add a small positive constant such that $a^Tx + \epsilon \le b$.

Answer 2

I can't imagine having constraints with a strict inequality ($<$ or $>$). When you are solving a linear programming problem, you are typically trying to find a minimum or maximum value on a closed region (given with constraints that involve $\leq$ and $\geq$). You need the region to be closed to guarantee that a minimum or maximum exists, as opposed to just a supremum or infimum.

As for putting the constraints into standard form, I would just change all the $<$ and $>$ signs into $\leq$ and $\geq$ signs (so you're taking the closure of your region), and then after finding the solution to the linear programming problem, see if your solution lies on a boundary that you added in when you took the closure. If it doesn't, then you're good. If it does, you have to say that a solution doesn't exist, but does get arbitrarily close to the value of the solution you found.

Answer 3

If constraints are all purely > or < then the feasible region is open and no longer includes its boundary. The difficulty this creates is that there is no optimal solution - for any solution within the feasible region you can find a better solution also within the feasible region by moving closer to a boundary.

Answer 4

I agree with the other answers that if you want an optimization problem, then an open region may not actually obtain its least upper bound on an objective. Also, the statement of linear programming does not include the ability to directly state strict inequalities.

However, sometimes all you want to ask is a feasibility question rather than an optimization question. I believe it is then possible to model your problem in such a way as to include strict inequalities (someone please correct me if you see a flaw in my reasoning).

See slide 8-8 of https://web.stanford.edu/class/ee364a/lectures/geom.pdf .

You can place any inhomogeneous problem LP of the form $Ax \ge b$ into a homogenous form $A x' \ge 0$ by introducing a new variable $\lambda$ to scale b, and $x'$ which corresponds to $ x' = \lambda x$. Then any of those inequalities you want strict can be made so by including a 1 on the right hand side.

This might be equivalent to the above suggestion of introducing a small positive slack variable $\epsilon$ to the strict inequality, which is conceptually simpler. You'd add the constraint $\epsilon \ge 0$ and try to maximize $\epsilon$ to get the largest possible slack in the strict inequalities.