4
$\begingroup$

Let's have the following trivial linear program: \begin{align}\max&\quad z=20A+30B\\\text{s.t.}&\quad A\le60\\&\quad B\le50\\&\quad A+2B\ge220\\&\quad A,B\ge0\end{align}

It's easy to spot that the first three constraints are contradictory. So, there are no solutions.

Let's assume we have dozens, hundreds, or even thousands of variables and constraints. Is there any automatic way to spot the contradictory constraints? Maybe by some nuance of AI?

$\endgroup$
3
  • 2
    $\begingroup$ irreducible infeasible set $\endgroup$
    – RobPratt
    Commented Apr 25, 2021 at 18:25
  • $\begingroup$ If lots of dual variables are zero, this might be interesting: orinanobworld.blogspot.com/2011/07/… $\endgroup$
    – T_O
    Commented Apr 26, 2021 at 15:24
  • $\begingroup$ In cplex, you can use ConflictRefiner which shows you examples of conflicting constraints. $\endgroup$
    – EhsanK
    Commented Jun 20, 2021 at 17:36

1 Answer 1

5
$\begingroup$

Shameless plug: I recently gave a webinar on diagnosing infeasibility.

Here's what your example looks like in SAS:

proc optmodel;
   var A >= 0;
   var B >= 0;
   max z = 20*A + 30*B;
   con c1: A <= 60;
   con c2: B <= 50;
   con c3: A+2*B >= 220;
   solve with lp / iis=true;
   expand / iis;
quit;

The resulting IIS contains all three constraints but not the lower bounds on A and B:

Constraint c1: A <= 60                                                                         
Constraint c2: B <= 50                                                                         
Constraint c3: A + 2*B >= 220   
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.