SCIP
Solving Constraint Integer Programs
How to deduce reasons for infeasibility in SCIP
It is a common problem for integer programming practitioners to (unexpectedly) encounter infeasible instances. Often it desirable to better understand exactly why the instance is infeasible. Was it an error in the input data, was the underlying formulation incorrect, or is my model simply infeasible by construction? There are two main ways to analyse infeasible instances using SCIP:
Firstly, there is IIS (irreducible infeasible subsystem) functionality in SCIP. This produces an infeasible problem, which contains a subset of constraints and variable bounds from the original problem. The infeasible problem is also irreducible, in that removing any additional constraints results in the problem becoming feasible. This is a fantastic method for debugging problems, and for determining what needs to be changed in the formulation. To use this functionality in the SCIP shell do the following
This will read in your instance and then compute an IIS of your infeasible instance. To display or print the subscip that contains the modified instance that is still infeasible, and hopefully substantially smaller, do the following
Secondly there is the MinUC (minimize number of unsatisfied constraints) functionality in SCIP. This produces a minimum set of constraints, such that if those constraints were relaxed, the original problem would be feasible. To use this functionality in the SCIP shell do the following
SCIP> read path_to_instance
SCIP> change/minuc
static SCIP_RETCODE optimize(SCIP *scip, SCIP_SOL *worksol, SCIP_VAR **vars, int *blockstart, int *blockend, int nblocks, OPTTYPE opttype, SCIP_Real *activities, int nrows, SCIP_Bool *improvement, SCIP_Bool *varboundserr, SCIP_HEURDATA *heurdata)
Definition: heur_twoopt.c:967
The second command changes the loaded problem to now minimize the number of unsatisfied constraints. The primal bound during solving corresponds to current best solution, i.e., a set of constraints which when removed or relaxed will induce feasibility. One can view the constraints that art part of the MinUC by seeing which of the variables have value 1. The variables in the new problem have naming conventions originalconsname_master. The solution can be displayed in the shell with the command
SCIP> display/solution