SCIP
Solving Constraint Integer Programs
iisfinder_greedy.h File Reference
Detailed Description
greedy deletion and addition filter heuristic to compute IISs
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) |