For an Integer Linear Programming problem (ILP), an irreducible infeasible set (IIS) is an infeasible subset of constraints, variable bounds, and integer restrictions that becomes feasible if any single constraint, variable bound, or integer restriction is removed. It is possible to have more than one IIS in an infeasible ILP. Is it possible to identify all possible Irreducible Infeasible Sets (IIS) for an infeasible Integer Linear Programming problem (ILP)? Ideally, I aim to find the MIN IIS COVER, which is the smallest cardinality subset of constraints to remove such that at least one constraint is removed from every IIS.
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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$$ and a binary variable $u_j$ and integer variable $v_j$ for each integer variable $x_j$, which you will relax to continuous. The problem is to minimize $$\sum_i z_i + \sum_j u_j \tag0$$ subject to \begin{align} \sum_j a_{i,j} x_j - b_i \le M_i z_i \quad \text{for all $i$} \tag1 \\ -u_j \le x_j - v_j \le u_j \quad \text{for all $j$} \tag2 \end{align} The objective $(0)$ minimizes the number of omitted restrictions. The linear big-M constraint $(1)$ enforces the logical implication $$z_i = 0 \implies \sum_j a_{i,j} x_j \le b_i$$ Constraint $(2)$ enforces $x_j \not= v_j \implies u_j = 1$ to penalize a fractional value for $x_j$.
