Detailed Description

greedy deletion and addition filter heuristic to compute IISs

Author: Marc Pfetsch; Mark Turner; Paul Meinhold

An irreducible infeasible subsystem (IIS) is a subset of the constraints and bounds from a problem that is infeasible. The greedy filter heuristic has two different approaches for producing an (I)IS:

Remove constraints such that the remaining problem is still infeasible.
Add constraints from an empty problem until the problem becomes infeasible. Both these approaches can be augmented to include bounds. That is, existing bounds can be deleted while the IS remains infeasible. A common approach is to also apply the deletion based filter after applying the additive based filter. This greedy algorithm is based on

O. Guieu and J. Chinneck, Analyzing infeasible mixed-integer and integer linear programs,INFORMS J. Comput. 11, no. 1 (1999), pp. 63–77.

If the appropriate parameters are set then we can guarantee that the result is irreducible, i.e., an irreducible infeasible subsystem (IIS). Otherwise we may only obtain an infeasible subsystem (IS). This algorithm cannot guarantee to find the smallest possible IIS.

Definition in file iisfinder_greedy.h.

#include <scip/scip.h>

Go to the source code of this file.

Functions
SCIP_RETCODE	SCIPincludeIISfinderGreedy (SCIP *scip)
SCIP_RETCODE	SCIPiisGreedyMakeIrreducible (SCIP_IIS *iis)

Detailed Description

Functions