Version: 0.1

Author: Marc Pfetsch

This code uses Benders decomposition to solve the Minimum IIS-Cover Problem (MinIISC). Here, one is given an infeasible linear system and wants to compute a subsystem of smallest size whose removal leaves a feasible subsystem. This corresponds to removing at least one constraint from each irreducible infeasible subsystem (IIS).

The approach is described in:

"Finding the Minimum Weight IIS Cover of an Infeasible System of Linear Inequalities"
by Mark Parker and Jennifer Ryan,
Ann. Math. Artif. Intell. 17, no. 1-2, 1996, pp. 107-126.

Solution Approach

This approach works as follows. MinIISC can be formulated as:

\begin{eqnarray*} \min && \sum_{i=1}^m y_i \\ s.t. && \sum_{i \in I} y_i \geq 1 \quad \forall \mbox{ IISs }I \\ && y_i \in \{0,1\} \quad \forall i. \end{eqnarray*}

We begin with a subset of IISs and solve the above set covering problem (using SCIP as a MIP solver). We then check whether the resulting vector \(y^*\) corresponds to an IIS-cover. If this is the case, we are done. Otherwise, we check for an uncovered IIS and add its inequality to the set covering problem. We then repeat the process.

Checking for an uncovered IIS can be done using a so-called alternative polyhedron. We explain the approach for the case in which the linear system is \(Dx \leq d\) where \(D\) is an \(m \times n\) matrix. The alternative polyhedron is then

\[ \{z : D^T z = 0,\; d^T z \leq -1,\; z \geq 0\}. \]

Gleeson and Ryan [1990] proved that the vertices of this polyhedron are in 1-to-1 correspondence with the IISs of the original system. If we are then given the solution \(y^* \in \{0,1\}^m\) from the set covering problem, we can consider

\[ \{z : D^T z = 0,\; d^T z \leq -1,\; z_i = 0 \mbox{ for all i with }y^*_i = 1,\; z \geq 0\}. \]

A vertex of this polyhedron corresponds to an IIS is the system remaining from \(D x \leq d\) when the inequalities given by \(y^* = 1\) are deleted.

Implementation

The implementation uses several tricks to speed up the solution process:

Several IISs are generated in one round using the technique described in Branch-And-Cut for the Maximum Feasible Subsystem Problem,
Marc Pfetsch, SIAM Journal on Optimization 19, No.1, 21-38 (2008)
The master problem can be solved approximately (using a gap limit) or using a stall limit (the final MIP has to be solved exactly).
Moreover, the master problem can be tackled using reoptimization.

The input to the code should be an infeasible linear program (the objective is ignored) in any format that SCIP can handle. The basic benders algorithm is implemented in the file benders.c using a call back for the cut generation.

Installation

See the Install file