16
$\begingroup$

The IIS is a standard part of most modern solvers, but is it unique for an LP? My intuition tells me that it should be, but I could find any proof.

$\endgroup$
27
$\begingroup$

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 infeasibility. As an example, take the following set of constraints:

$$ x_1 \le 0 \\ x_1 \ge 1 \\ x_2 \le 0 \\ x_2 \ge 1 $$

There are two options for an IIS: the first two constraints, and the last two constraints.

Sources:

  1. https://glossary.informs.org/ver2/mpgwiki/index.php/Irreducible_infeasible_subsystem
  2. https://orinanobworld.blogspot.com/2010/07/why-is-my-model-infeasible.html
| improve this answer | |
$\endgroup$
5
$\begingroup$

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

| improve this answer | |
$\endgroup$

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.