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?

Improve this question
$\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

Reset to default
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
Improve this answer
$\endgroup$
0