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
    Apr 25 at 18:25
  • $\begingroup$ If lots of dual variables are zero, this might be interesting: orinanobworld.blogspot.com/2011/07/… $\endgroup$
    – T_O
    Apr 26 at 15:24
  • $\begingroup$ In cplex, you can use ConflictRefiner which shows you examples of conflicting constraints. $\endgroup$
    – EhsanK
    Jun 20 at 17:36
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, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.