[Scip] branching on cutting plane slacks

[Timo Berthold]

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.

Cheers, Timo


> Hi all,
>
> I have written a constraint handler which, amongst other things,
> generates cutting planes. I have a hunch that branching on the slack
> variables associated with these cutting planes might be a good idea.
> What's the simplest way to do this?
>
> Thanks in advance,
>
> James
>
> --
> James Cussens	         ---- NEW CONTACT DETAILS ----
> Dept of Computer Science &
> York Centre for Complex Systems Analysis             jc at cs.york.ac.uk
> Room 326, The Hub, Deramore Lane              Tel  +44 (0)1904 325371
> University of York                            Fax  +44 (0)1904 500159
> York YO10 5GE, UK                        http://www.cs.york.ac.uk/~jc
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> http://listserv.zib.de/mailman/listinfo/scip
>