[Scip] XOR constraints

[Tobias Achterberg]

Joerg,

if you want "at most one of a set of binary variables can be one", this is just a set 
packing constraint, see cons_setppc.h.

Tobias


Jörg Pfähler wrote:
> Hi Micha&  Stefan
>
> Thanks for the replies. I missunderstood what xor does for more than 2
> variables. I thought it would still mean "only zero or one variable is set to
> 1" for more than 2 variables. So an xor-constraint is actually not what I need
> for my model.
>
> Best Regards,
> Jörg
>
>> 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
>
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> http://listserv.zib.de/mailman/listinfo/scip