Tag Info

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

11

Equivalently, you want to remove the smallest number of constraints so that the resulting problem is feasible. You can do this implicitly, without enumerating all Irreducible Infeasible Sets, by solving an auxiliary ILP problem. Introduce a binary variable $z_i$ for each constraint (including variable bounds as a special case) $$\sum_j a_{i,j} x_j \le b_i$$...

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

3

ILOG Cplex 20.1 installation comes with a directory with examples. To use the conflict refiner, you want to consult the manual which includes a list of files that contain examples on how to use the conflict refiner. Of particular interest are the following files: ./examples/src/java/ConflictEx1.java ./examples/src/cpp/iloconflictex1.cpp ./examples/src/python/...

3

As the docplex documentation says: Given an infeasible model, the conflict refiner can identify conflicting constraints and bounds within it. So, consider you have an infeasible model (I'll call my instance model). This is one way to use the conflict refiner. import docplex.mp.conflict_refiner as cr import docplex.mp.model as cpx model = cpx.Model(name='...

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