27

The irreducible infeasible subsystem (IIS) for an infeasible linear program (LP) is a minimal subset of constraints that has no feasible solution, i.e., an inconsistent set of constraints for which any proper subset of the constraints is consistent. It is not true that an IIS is unique. For intuition, consider that there may be more than one source of ...


8

Finding a minimum-cardinality MIS for a linear program is an NP-hard problem in general, see Edoardo Amaldi, Marc E. Pfetsch, and Leslie E. Trotter Jr. On the maximum feasible subsystem problem, IISs and IIS-hypergraphs. Mathematical Programming, 95(3):533–554, 2003. For this reason, commercial solvers such as CPLEX use heuristics to identify small IIS which ...


5

An IIS is not unique. Given a system $Ax \le b$, the indices of an IIS are the supports of the vertices of the polyhedron $P=\{y: y^{\top}A=0, \; y^{\top}b \le -1, \; y \ge 0\}$. This is the theorem in https://pubsonline.informs.org/doi/abs/10.1287/ijoc.2.1.61


5

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 ...


4

Not yet, see https://github.com/google/or-tools/issues/973 For debugging I would recommend you to divide your constraints into groups so you can activate/deactivate some of them to pin down the infeasibility


Only top voted, non community-wiki answers of a minimum length are eligible