[Scip] XOR constraints

michael.winkler@zib.de michael.winkler at zib.de
Tue Oct 18 10:38:17 MEST 2011


Hi Jörg,

moreover you can decide whether an odd or even number of (binary)
variables needs to be set to true, to fulfill an XOR constraint. This is
done by either setting the right hand side to one or zero.
If you have only two variables SCIP will aggregate these two variables and
delete your constraint, since it is redundant.

Best, Micha

> Hi Jörg,
>
> an xor(x_1, ..., x_n) is usually not equivalent to x_1 + x_2 + ... + x_n
> <= 1. This is only the case for n = 2. An xor is satisfied if an odd
> number of the variables is set to true. I just check the code. even in
> the special case of n = 2, SCIP does not upgrade the xor constraint into
> an (linear) variable bound constraint (cons_varbound.c). That is
> something we could thing about.
>
> Best Stefan
>
> On 10/17/11 22:16, Jörg Pfähler wrote:
>> Hi,
>>
>> does SCIP somehow take advantage of an xor-constraint (only one of the
>> binary
>> variables x_1, ..., x_k is 1) created with SCIPcreateConsXor instead of
>> creating an equivalent constraint (x_1 + ... + x_k<= 1) with
>> SCIPcreateConsLinear?
>>
>> Best Regards,
>> Jörg
>>
>> _______________________________________________
>> Scip mailing list
>> Scip at zib.de
>> http://listserv.zib.de/mailman/listinfo/scip
>
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> http://listserv.zib.de/mailman/listinfo/scip
>



More information about the Scip mailing list