[Scip] scip_xor.c
Marc Pfetsch
pfetsch at mathematik.tu-darmstadt.de
Fri Jan 18 11:09:59 MET 2013
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
>
More information about the Scip
mailing list