On Wed, 14 Oct 2009, Alexander Schnell wrote: > 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:
The addition of binary variables makes me dubious about the strength of the linear relaxation. That said, my formulation was pretty awful, i.e. wrong. My formulation wouldn't work because I somehow missed the possibility that c might be forced to zero. This one works and is simpler than my previous mess. Define four continuous auxillary variables: Q00, Q01, Q10, Q11 >= 0 Q00 + Q01 + Q10 + Q11 = 1 a = Q10 + Q11 b = Q01 + Q11 The integrality of a and b will force the Q's to be integral. c <= (1-Q00)*upper(c) c >= (1-Q00)*lower(c) c-d <= (1-Q01)*upper(c-d) c-d >= (1-Q01)*lower(c-d) c-e <= (1-Q10)*upper(c-e) c-e >= (1-Q10)*lower(c-e) c <= (1-Q11)*upper(c) c >= (1-Q11)*lower(c) I think this formulation will get you the convex hull, but I'm not sure. Since it works, it should also be easier to understand. -- Michael henne...@web.cs.ndsu.nodak.edu "Pessimist: The glass is half empty. Optimist: The glass is half full. Engineer: The glass is twice as big as it needs to be." _______________________________________________ Help-glpk mailing list Help-glpk@gnu.org http://lists.gnu.org/mailman/listinfo/help-glpk