sci.op-research

Gordon Sande wrote:

>> 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

Yes, that's fairly well documented.

> in which he studied
> the computer game of LIFE. ;-)

I do remember the game, but I don't recall every playing it. (I did hack
the old Lunar Lander game to figure out an optimal control solution,
which of course eliminated any replay value.)

> 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.

Not to mention giving sysops something to do during idle time. Now if
you can find an educational value to the original (mainframe) Star Trek
game ...

> 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.

That pretty well sums it up.

Now, as to how I arrived there, the process was largely pattern
recognition/adaptation -- recognize a problem (constraining nonzeros to
adjacent variables, in the special case of binary variables), relate it
to similar things with which I'm familiar (in this case, I think I
flashed back to scheduling formulations in which you need to be sure a
machine is producing the same thing it did the previous period, or else
pay a change cost) and adapt the solution for the latter to the former.
A considerable amount of IP formulation, at least for me, comes from
seeing some trick in a formulation (perhaps in this group), having it
stick in my mind, and dredging it up (perhaps with a tweak or two) at an
opportune moment.

There is, however, a relatively modest degree to which one can
systematize the process, for the particular case of binary variables.
Using the term "adjacent" in the circular sense (so that y(1) and y(10)
are adjacent), you want exactly two binary variables to equal one, and
you want them adjacent. The first part is easy: constraining the sum
of all of them equal to one guarantees exactly two take value one. That
leaves the adjacency restriction. Any time I am faced with formulating
a constraint involving binary variables, I try first to frame it in
terms of predicate logic (if I'm using that term correctly -- my last
logic course was in a different millenium). So here we say

if [y(j) = 1] then [one of y(j)'s neighbors must be one]
<=>
if [y(j) = 1] then [y(j-1) = 1 or y(j+1) = 1]

(with index arithmetic being modulo 10 as it were). Here I pause to
note that I need not worry that the 'or' in the last clause is an
exclusive or; the first constraint (sum = 2) will take care of that.

The next step in my logic sequence is perhaps not quite so rigorous: I
stare at that constraint and, if I don't see an easy way to formulate
it, I try the contrapositive. (Using the contrapositive is rigorous --
doing it because I came up empty is perhaps not so rigorous.) That
brings me to

if [y(j-1) = 0 and y(j+1) = 0] then [y(j) = 0].

This type of logical constraint is easy to formulate. You just need an
upper bound on y(j) that is zero if the antecedent is true and at least
one if the antecedent is false. That brings us to the solution I posted
without further ado.

I have in the past recommended to students struggling with this type of
formulation that they write down a truth table, then try to write
conditions in terms of inequalities. Thus y(j) = 0 becomes y(j) <= 0,
relying on the {0, 1} domain restriction to avoid negative values, and
y(j) in {0, 1} (or unconstrained) becomes y(j) <= 1. From there, I
suggest they try to replace the RHS with something cleverly tied to the
antecedent. It's also worth noting that y(j) <= 0 can just as well be
y(j) <= a for any a in the interval [0, 1), and y(j) <= 1 can just as
well be y(j) <= a for any a in [1, infinity).

HTH,
Paul