Questions tagged [irreducible-infeasible-subset]

For questions on subsets of constraints of an infeasible mathematical program whose (strict) subsets are feasible.

Filter by
Sorted by
Tagged with
4
votes
1answer
301 views

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 ...
2
votes
1answer
334 views

How to know which constraint in CP-SAT did not meet the feasibility gap

Is there any systematic way to retrieve some information on the constraint that caused infeasibility in Or.Tools CP-SAT? ...
11
votes
1answer
96 views

Computational complexity to compute an IIS

How hard is it to compute an irreducible infeasible subset (IIS) for a linear program? What about an integer program (e.g., removing the integrality constraint on a single variable may be enough to ...
16
votes
2answers
227 views

Is the Irreducible Infeasible Subset (IIS) of an LP unique?

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.