# Is there any automatic way to spot contradictory constraints in linear programming?

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?

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

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