help-glpk
[Top][All Lists]

## Re: [Help-glpk] More conditional variables fun

 From: Alexander Schnell Subject: Re: [Help-glpk] More conditional variables fun Date: Wed, 14 Oct 2009 12:45:51 +0400

```Hi there,

i have found out a formulation for your problem but the linear formulation is
quite long:

the nonlinear formulation is quite short:
c = d*b*(b-a)+ e*a*(a-b).

So now you can substitute the term  d*b*(b-a) by the variable x and the term
e*a*(a-b) by the variable y.
b*(b-a) is the produkt of the binary variable b and the variable (b-a) in
{-1,0,1} and substituted by z. (z is binary)
a*(a-b) is also the product of the binary variable a and the variable (a-b) in
{-1,0,1} and substituted by w. (w is binary)
so we yield the following equations:

1) c = x + y
2) x = d * z
3) y = e * w
4) z = b*(b-a)
5) w = a*(a-b)

Now you can reformulate 2)- 5) to yield linear equations:

2a) x <= M1 *z           where M1 is an upper bound for the variable x
2b) x - d <= M2 * (1-z)  where M2 is an upper bound for the difference x - d
2c) d - x <= M3 *  (1-z)  where M3 is an upper bound  for the difference d - x

this reformulation of 2) can only be done as z is binary. Now 3) can be
reformulated equivalently as w is binary:

3a) y <= M4 *w           where M4 is an upper bound for the variable y
3b) y - e <= M5 * (1-w)  where M5 is an upper bound for the difference y - e
3c) e -y <= M6 *  (1-w)  where M6 is an upper bound  for the difference e - y

As b is  a binary variable, you can formulate 4) and 5) as follows:

4a) z <= b
4b) z - b + a <= 2 * (1 - b)  2 is an upper bound for z - (b-a)
4c) b - a - z <=  1 * (1 - b)  1 is an upper bound for (b - a) - z

and analogly 5)

5a) w <= a
5b) w - a + b <= 2 * (1 - a)  2 is an upper bound for w - (a-b)
5c) a - b - w <=  1 * (1 - a)  1 is an upper bound for (a - b) - w

So by contraints 1), 2a)-c), 3a)-c), 4a)- c) and 5a)- c) and forcing z and w to
be binary you can formulate a model in mathprog for your problem.

Best Regards,

Alex

_______________________________________________________________
Neu: WEB.DE DSL bis 50.000 kBit/s und 200,- Euro Startguthaben!
http://produkte.web.de/go/02/

```