Alex,Michael,Andrew,Larry- Thanks a lot for all the help and the great discussion. I'll summarize the different approaches in a separate email for future reference.
Regards Kretch. On Wed, Oct 14, 2009 at 1:45 AM, Alexander Schnell <[email protected]> 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/ > > > > > > > _______________________________________________ > Help-glpk mailing list > [email protected] > http://lists.gnu.org/mailman/listinfo/help-glpk >
_______________________________________________ Help-glpk mailing list [email protected] http://lists.gnu.org/mailman/listinfo/help-glpk
