[Scip] branching on cutting plane slacks

Tobias Achterberg achterberg at zib.de
Tue May 24 09:50:53 MEST 2011


Timo Berthold wrote:
> Good morning James.
>
> I guess the straight-forward way is to branch on the linear constraint
> itself.
>
> E.g., your cut is 3x+ 5y (+s)<= 10. where s is the slack of the
> constraint. You would like to branch on s<= 6 OR>= 7. This is the same as
> branching 3x+5y>= 4 OR 3x+5y<= 3. In SCIP terminology this would mean to
> create a local constraint that gets attached to the two (or more) nodes
> that you create in branching. See also the "Further information" in "How
> to add branching rules" in SCIP's doy docs and the enforcement methods of
> the SOS constraint handlers.
>
> Just one question: Are your cuts local or do you want to branch on a point
> different from the LP solution? Because otherwise, a disjunction on the
> slack of a cut would always trigger one of the subproblems infeasible.

Why is this? Branching on a slack is pretty straight forward. I think the most efficient 
way for doing this in SCIP is to explicitly add the slack variable to the model and then 
add the constraint 3x + 5y + s == 10, s >= 0.
Note that you probably need to forbid multi-aggregation on s to tell the presolver that it 
should not remove s from the model.

Then, you can just branch on s as usual. If you declare s to be an integer variable (of 
course this is only valid if the slack of the constraint is always integer), then SCIP 
would even consider branching on s itself.


Tobias


More information about the Scip mailing list