[SCIP] minimal irreducible infeasible subsystem

Ali Baharev ali.baharev at gmail.com
Sat Dec 12 15:21:28 CET 2015

Dear Marc,

Thanks for the tips. I have the book "Feasibility and Infeasibility in
Optimization: Algorithms and Computational Methods" published in 2008
by John W. Chinneck. I am currently using Gurobi which can compute a
minimal (though not minimum) IIS. So what Gurobi does is also just a

I was hoping to get insight by doing the same with SCIP and inspect
what SCIP was doing.

Anyway, apparently I haven't missed anything obvious based on your feedback.

Thanks for your help,


On Sat, Dec 12, 2015 at 2:38 PM, Marc Pfetsch
<pfetsch at mathematik.tu-darmstadt.de> wrote:
> Hi Ali,
> there is currently no way to compute IISs of mixed-integer problems in
> the release version of SCIP. (If all variables are continuous this would
> be possible through an alternative polyhedron.)
> There are some heuristics, e.g., the ones described in
> O. Guieu and J.W. Chinneck (1999), "Analyzing Infeasible Mixed-Integer
> and Integer Linear Programs", INFORMS Journal on Computing, vol. 11, no.
> 1, pp. 63-77.
> Moreover, CPLEX and Gurobi implement heuristics for computing IISs.
> In your case, you might use a simple greedy strategy: remove the
> constraints one by one until your problem becomes feasible. Moreover,
> you can sort out constraints that are redundant for the modified
> problem. This is, however, still heuristic.
> The exact computation of an IIS of minimal size seems to be
> (computationally) more difficult.
> Best
> Marc
> On 11.12.2015 22:17, Ali Baharev wrote:
>> Hi Gregor,
>> Thanks for the advice.
>> Apparently this minuc feature is not what I was looking for; it does
>> not give a minimal irreducible infeasible subsystem (IIS). It seems to
>> me that with this minuc feature I can find a small set of constraints
>> that when dropped from the infeasible problem make the remaining
>> problem feasible.
>> To avoid the XY problem (http://xyproblem.info/), please let me
>> describe what I am doing. I am trying to find a minimal set of
>> constraints of an ILP that are necessary to find the same optimum that
>> we get when we solve the original ILP with all its constraints
>> included. (All the other constraints of the ILP can be dropped without
>> changing the optimum.)
>> My current hack is the following. I solve (minimize) the ILP, then I
>> add an artificial constraint. The body of this artificial constraint
>> is the body of the objective function, and this constraint demands
>> that the objective is 1 less than what we currently have at the
>> optimum. Of course, this is an infeasible ILP, the artificial
>> constraint made it infeasible. Then, I compute a minimal IIS. The
>> constraints in the IIS (minus the artificial constraint) are the
>> constraints I am looking for; all the other constraints of the
>> original ILP can be dropped without changing the optimum. (Probably my
>> hack is an overkill? Maybe I missed something obvious?)
>> Anyway, is there a way to get this set of rows that I am looking for
>> in the SCIP shell (without writing C++ code)?
>> Many thanks,
>> Ali
>> On Fri, Dec 11, 2015 at 2:19 PM, Gregor Hendel <hendel at zib.de> wrote:
>>> Hi Ali and list,
>>> you can figure out the number of violated constraints from the primal bound.
>>> After the transformation, there is one binary variable added for every
>>> constraint of the original problem, each with an objective coefficient of 1.
>>> These variables are named "<originalconsname>_master"
>>> You can display the problem after the minuc transformation by using 'display
>>> problem'.
>>> If you would like to know the constraints that are violated in the minuc
>>> solution, type display solution and check which of the master variables are
>>> set to 1.
>>> Kind regards,
>>> Gregor
>>> Am 11.12.2015 um 12:10 schrieb Ali Baharev:
>>>> Hi,
>>>> I have already found
>>>> http://listserv.zib.de/pipermail/scip/2012-October/001095.html
>>>> and in particular:
>>>> SCIP> read <file>
>>>> SCIP> change minuc
>>>> SCIP> optimize
>>>> which works fine but how do I proceed from here?
>>>> How can I figure out which constraints of the **original** problem
>>>> belong to the irreducible inconsistent subsystem (IIS)?
>>>> For the time being, it is sufficient for me to know the number of
>>>> constraints in the IIS that were also in the original problem.
>>>> Any help is greatly appreciated.
>>>> Ali
>>>> _______________________________________________
>>>> Scip mailing list
>>>> Scip at zib.de
>>>> http://listserv.zib.de/mailman/listinfo/scip
>>> _______________________________________________
>>> Scip mailing list
>>> Scip at zib.de
>>> http://listserv.zib.de/mailman/listinfo/scip
>> _______________________________________________
>> Scip mailing list
>> Scip at zib.de
>> http://listserv.zib.de/mailman/listinfo/scip
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> http://listserv.zib.de/mailman/listinfo/scip

More information about the Scip mailing list