[Scip] Misusing a SCIP instance as a separation oracle

[Ambros Gleixner]

Hi Matthias,

One last comment:

 >> I am not sure how you would go about inspecting the new cuts most
 >> efficiently/conveniently.


If you are not afraid of writing an event handler, then this seems like 
a good way, because you get the rows immediately when they are added to 
the LP.  In the case that the LP becomes infeasible, I am not sure 
whether the LP will still be accessible after the infeasibilty has been 
detected by SCIP/the LP solver.

Because of trivial singleton cuts, you should probably also catch bound 
change events.


 > I will go and find out!

Good luck, you might be going where no man has gone before.

;)

Ambros




Am 06.03.2015 um 14:39 schrieb Matthias Walter:
> Hi Ambros,
>
> first thanks for the detailed reply!
>
> On 03/04/2015 04:51 PM, Ambros Gleixner wrote:
>> I am not sure whether you already received some feedback.  Just a
>> few comments.  Making integer variables continuous is dangerous if
>> they are contained in constraint handlers that allow only specific
>> types, like the knapsack constraint handler would only allow binary
>> variables.  If all your constraints are linear, for example, then
>> this should be ok.
>
> Okay, I see the point.
>
>> Furthermore, if you impose the current solution as lower bounds, the
>> LP may be infeasible after separation, so you have to be aware of
>> that possibility.
>
> Yes - I hope to be able to intercept SCIP at this point before it
> returns "infeasible" in order to see the rows of the LP.
>
>> Also, I am not sure whether you can forbid constraint handlers to
>> perform propagation during enforcement, so in general you may have
>> to convert bound changes to singleton cuts.
>
> But am I right here in that this (since I only solve the root node) can
> only result in bound changes? Since I know the original bounds, I can
> easily observe changes. And if some constraint sets a new bound, then
> mathematically I would say this inequality belongs to the LP relaxation
> associated to this constraint (or the set of constraints, since I don't
> care which one is guilty) and so I'm fine with it being added.
>
>> Adding locks to all variables is probably a good idea to be sure to
>> avoid anybody performing dual reductions using the artificial
>> objective function.
>
> Good point, thank you.
>
>> I am not sure how you would go about inspecting the new cuts most
>> efficiently/conveniently.
>
> I will go and find out!
>
> Best,
>
> Matthias
>
>> Am 18.02.2015 um 10:49 schrieb Matthias Walter:
>>> Dear list,
>>>
>>> I want to use a given SCIP instance (for a MIP) as a separation
>>> oracle for the linear relaxation, i.e., given some point x I want
>>> to find (if it exists) an inequality valid for the LP relaxation
>>> but not for x. I don't know the SCIP instance very well, except
>>> that I assume that all constraints can be enforced using linear
>>> inequalities. By LP relaxation I mean the intersection of all
>>> inequalities coming from constraints, e.g. for the TSP example the
>>> bounds, degree constraints, but also all subtour inequalities. I
>>> suppose that I can't just call the CONSENFOLP callback of every
>>> constraint outside of a SCIPsolve call since they might require
>>> other data to be set up, like a transformed problem, or they could
>>> even be deactivated, etc.
>>>
>>> So my idea was to do the following and I would be happy to get
>>> some feedback or hints on whether this sounds like a stupid one:
>>>
>>> - Turn off presolve, cuts, conflict propagation. and heuristics. -
>>> Make integer variables continuous. - Fix lower bounds to x and
>>> change objective to minimize the sum of all variables to make x the
>>> unique basic solution. - Run SCIP and inspect the LP whether x is
>>> cut off and which row(s) do it.
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> http://listserv.zib.de/mailman/listinfo/scip
>

-- 
______________________________________________________________
Ambros M. Gleixner
Zuse Institute Berlin - TU Berlin - Berlin Mathematical School
http://www.zib.de/gleixner