[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Help-glpk] More conditional variables fun
From: |
Michael Hennebry |
Subject: |
Re: [Help-glpk] More conditional variables fun |
Date: |
Wed, 14 Oct 2009 20:23:19 +0400 |
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."
- RE: [Help-glpk] More conditional variables fun, (continued)
- Re: [Help-glpk] More conditional variables fun, Andrew Makhorin, 2009/10/13
- Re: [Help-glpk] More conditional variables fun, Andrew Makhorin, 2009/10/13
- Re: [Help-glpk] More conditional variables fun, Michael Hennebry, 2009/10/12
- Re: [Help-glpk] More conditional variables fun, Michael Hennebry, 2009/10/12
- Re: [Help-glpk] More conditional variables fun, Michael Hennebry, 2009/10/13
- Re: [Help-glpk] More conditional variables fun, Michael Hennebry, 2009/10/14
- Re: [Help-glpk] More conditional variables fun, Alexander Schnell, 2009/10/14
- Re: [Help-glpk] More conditional variables fun,
Michael Hennebry <=