On Wed, Oct 14, 2009 at 1:45 AM, Alexander Schnell
<address@hidden> wrote:
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/