sci.op-research

On 2008-03-15 23:15:51 -0300, Peter said:

> On Mar 15, 6:11 pm, Paul Rubin wrote:
>> Peter wrote:
>>> Hey Guys,
>>
>>> I have a set of binary variables y(i), where i= 1,2, ...,10. I wish to
>>> write a constraint to enforce that exactly two subsequent binary
>>> variables be equal to 1 and the rest be equal to zero (this might also
>>> include y(1) and y(10) ), i.e.:
>>
>>> y(i) and y(i+1) = 1 and the rest equl to zero, for some i, except
>>> 1
>>> or
>>> y(1) and y(10)= 1 and the rest equal to zero,
>>
>>> and exactly tow binary varialbes should be nonzero:
>>> sum(i, y (i) ) = 2
>>
>>> Is there any way to do this using linear constraints?
>>
>> If your solver supports SOS2 constraints, this is easy. Create one more
>> binary variable y(11) and put in the two constraints
>>
>> y(1) + ... + y(11) = 2
>> y(1) = y(11)
>>
>> and then declare y(1),...,y(11) to be a type 2 special ordered set (SOS2).
>>
>> If your solver does not understand SOS2, try this:
>>
>> y(1) + ... + y(10) = 2
>> y(1) <= y(10) + y(2)
>> y(2) <= y(1) + y(3)
>> y(3) <= y(2) + y(4)
>> ...
>> y(9) <= y(8) + y(10)
>> y(10) <= y(9) + y(1)
>>
>> /Paul- Hide quoted text -
>>
>> - Show quoted text -
>
> Thanks ! My solver doesn't know SOS2. But the constraints that you had
> suggested were pretty interesting. I am really interested to learn how
> you came up with this solution. Is there any special procedure in such
> these cases? Before posting the message on the forum, I thought about
> it for several hours but I couldn't find an effeicient set of
> constraints.
> Peter

One expects that Paul Rubin had a misspent youth in which he studied
the computer game of LIFE. ;-) It is a cellular automata where a cell
can only live if it has at least two neighbors. The objective was to
design patterns that had various interesting properties like moving,
emitting smaller paterns, growing forever, ... Who said abstract math
could not be fun. LIFE was an early game on Unix which served to
illustrate nonconventional applications of computers when graphics
was a new thing.

Here a variable can only be nonzero if it has a nonzero neighbor or
it will be zero if both neighbors are zero. And there must be exactly
two nonzeros, all under the assumption of bianary variables.