Re: [Help-glpk] More conditional variables fun

[Michael Hennebry]

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   address@hidden
"Pessimist: The glass is half empty.
Optimist:   The glass is half full.
Engineer:   The glass is twice as big as it needs to be."