[SCIP] minimal irreducible infeasible subsystem

[Ali Baharev]

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
heuristic.

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,

Ali

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