12
$\begingroup$

How should we deal with strict inequalities in a linear programming problem? For example:

inequalities such as $ax< b$;

$\endgroup$
3
  • 6
    $\begingroup$ Add a tolerance, $\epsilon>0$ and try solving with $ax \leq b-\epsilon$. $\endgroup$
    – copper.hat
    Commented Jul 20, 2012 at 7:57
  • $\begingroup$ @copper.hat Does tha apply to answer below? $\endgroup$
    – BCLC
    Commented Mar 3, 2016 at 3:40
  • 1
    $\begingroup$ @BCLC: In general, there will be no solution if the inequality is strict. So, what you do depends on what you want. The $\epsilon$ trick will work, but if the constraint is active, then the solution will not necessarily be optimal for the original problem. $\endgroup$
    – copper.hat
    Commented Mar 3, 2016 at 4:07

1 Answer 1

11
$\begingroup$

In general strict inequalities are not treated in linear programming problems, since the solution is not guaranteed to exist on corner points.

Consider the $1$-variable LPP: $Max$ $x$ subject to $x<3$. Now there does not exist any value of $x$ for which maximum is achieved and which lies in the feasible region.

$\endgroup$
2
  • 3
    $\begingroup$ 1. Linear programs are not necessarily about optimization, they can also be about feasibility. 2. Replacing ‘$\max$’ with ‘$\sup$’ evades the technical issue you point out. $\endgroup$
    – equaeghe
    Commented Jul 16, 2013 at 14:30
  • $\begingroup$ $x \le 3 - \epsilon$ ? $\endgroup$
    – BCLC
    Commented Mar 3, 2016 at 3:39

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .