[Scip] scip_xor.c

[Victor Miller]

Is there a writeup (besides the comments in the file) of some of the ideas
used in scip_xor.c?  In particular what's the logic behind the watched
variables?  I assume that this is something like the watched variables that
are used in a number of branching SAT solvers.

I'm interested in writing an alternative to this using an observation of
Siegel and Taghavi: Suppose that you have an xor constraint like:

x_1 + .. + x_n = r (the right hand side is 0 or 1).

Imagine writing out all 2^(n-1) linear constraints (the facets of the
polytope which is the convex hull of 0/1 solutions).  Then Siegel and
Taghavi showed that if x_i in [0,1] (not just integral) that at most one of
these constraints is violated, and, if so, one can find the violated
constraint in time proportional to n.  So the idea would be in the
constraint enforcing callback to find and add this constraint to the linear
relaxation as a cut.

Victor
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://listserv.zib.de/mailman/private/scip/attachments/20130117/81d0e22e/attachment.html