[SCIP] minimal irreducible infeasible subsystem

[Marc Pfetsch]

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
>