From: jwg@sparcman.cray.com (John Gregory)
Subject: Re: math puzzle
Reply-To: jwg@sparcman.cray.com (John Gregory)
Organization: Cray Research, Inc.
Distribution: usa
Date: 15 Oct 92 10:59:04 CDT


Hi Mark!

I think your LP model has turned into a combinatorial model, which 
you are perhaps aware can be much harder to solve than the equivalent 
LP.  There are several ways you can go about it, either by formulating
it as a nonlinear programming model (with nonlinear constraints), or 
as an Integer LP.  In terms of computational complexity it may all
boil down to the same (difficult) thing.

First, let me restate what I *think* you want: you want the sum of the
Xi to equal 1, but only for the i where Xi is positive, and to ignore
the i's where Xi is negative. And then you want to compute the sum
over i of (ci*Xi) for only those positive Xi's.  (Hope I'm close on
this!)

I would model it as an Integer LP, with integer decision variables 
Yi that take the value 0 if Xi is negative, and 1 if Xi is positive. 
Then I'd add yet *more* variables Zi, to equal Xi if Yi is 1, and 0 
if Yi is 0.  The Zi can be thought of as the positive part of the Xi.
It may seem like sort of a Rube Goldberg scheme I'm proposing here, 
and maybe if I thought about it for a while something simpler would 
occur to me, but right now I don't see how to avoid getting about this 
level of complexity to cover what you want.

You would thus need 3 times as many variables as originally (X, Y, and
Z, instead of just X), and the following additional constraints for 
*each* original variable:
  
     - Xi      + Zi >= 0
     - Xi + Yi + Zi <= 1
          - Yi + Zi <= 0
                 Zi >= 0  (implicit in most LP codes, but I'll say it here)

with Zi being an ordinary non-negative LP variable, and Yi being
binary (0 or 1).  Then you need one more constraint that says
     Z1 +    Z2 + ... +    Zn = 1
and the sum you are interested in is represented
  c1 Z1 + c2 Z2 + ... + cn Zn

In case this kind of model is new to you, I'll step through the 
logic.  Each Yi can be either 0 or 1, so we'll separate the logic into 
two cases.  If Yi=0 for a given i, then the third and fourth constraints 
above imply that the corresponding Zi is also zero.  Plugging both those 
values in the first and second constraints, you get that Xi must be 
between -1 and 0, which is what you want it to be.  On the other hand, 
if Yi=1, then the first and second constraints imply that -Xi+Zi is both 
>=0, and <=0, hence Zi=Xi, and the third and fourth constraints say that 
Zi (and thus Xi) can be between 0 and 1, again, as you'd want.

Conversely, look at it from the perspective of the Xi variables.  If
Xi needs to be negative (from whatever other constraints there are in 
your model) the second constraint above forces Yi to be 0, since if it
were 1 Zi could not be different from Xi (re: constraint 1), yet Zi 
cannot be negative (by constraint 4). And with Yi being zero, constraint 
3 now forces Zi to be zero.  If on the other hand Xi needs to be positive, 
that forces Zi to be positive, else constraint 1 would be violated. That
means Yi must be positive, else constraint 3 would be violated.

For cases where Xi=0 exactly, this formulation lets Yi be either 
0 or 1, but in either case Zi is also zero, so it doesn't affect
the sum you are computing.

To solve such models, you need an LP code that can handle Branch-
and-Bound algorithms for Integer LP.  Let me know if this is something
you'd like more information on.

It's interesting you chose to crosspost this to rec.puzzles.  I take 
that as an indication of how LP is viewed by many people.  8v) 8v)

- John Gregory
  Applications Dept.
  Cray Research, Inc.
  jwg@cray.com