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.
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
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:
answered Jun 11, 2019 at 16:02
$\begingroup$
$\endgroup$
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
