[Scip] Misusing a SCIP instance as a separation oracle

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