[SCIP] minimal irreducible infeasible subsystem

[Ali Baharev]

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