[Scip] scip_xor.c

[Marc Pfetsch]

Hi Victor,

as far as I know, there is no complete documentation of cons_xor.c. 
Parts are explained in the Ph.D. thesis of Tobias Achterberg, which is 
available here:

http://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/1112

In particular, he explains the special case of xor with two variables 
("bitwise xor" on Page 241). Watched literals are explained in Section 
7.4 (Set Covering Constraints) and indeed work as known from SAT solving.

The current implementation of cons_xor.c only generates the linear 
equation you mentioned below, with the exception of the case with three 
variables in which more inequalities are generated (see function 
createRelaxation()).

Thus, it would be interesting to have an implementation of the 
separation procedure you mentioned below, provided that you have 
instances for which such a separation procedure would help. Can you 
explain a bit about the background in which you want to apply this?

Best

Marc



On Jan 17, 2013 21:50, Victor Miller wrote:
> 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
>
>
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> http://listserv.zib.de/mailman/listinfo/scip
>