help-glpk
[Top][All Lists]

## Re: [Help-glpk] More conditional variables fun

 From: Yaron Kretchmer Subject: Re: [Help-glpk] More conditional variables fun Date: Tue, 13 Oct 2009 11:50:33 -0700

Michael,
I'm sorry, but I didn't understand your explanation below- This is due to my limited LP/MIP understanding- sigh..

But, looking at the examples on http://www.aimms.com/aimms/download/manuals/AIMMS3OM_IntegerProgrammingTricks.pdf and doing some math led me to the following formulation:

---------------------------begin formulation--------------------------------------------------
not_a_and_b <= (1-a)
not_a_and_b <= b
not_a_and_b >= b-a

not_b_and_a <= (1-b)
not_b_and_a <= a
not_b_and_a >= a-b

d_if_not_a_and_b <= U*not_a_and_b
d_if_not_a_and_b <= d
d_if_not_a_and_b >= d -U*(1-not_a_and_b)
d_if_not_a_and_b >= 0

e_if_not_b_and_a <= U*not_b_and_a
e_if_not_b_and_a <= e
e_if_not_b_and_a >= e-U*(1-not_b_and_a)
e_if_not_b_and_a >= 0

d_if_not_a_and_b_or_e_if_not_b_and_a = d_if_not_a_and_b+e_if_not_b_and_a
-----------------------------end formulation--------------------------------------------------

Is this close to what you were suggesting?

Thanks
Kretch

On Tue, Oct 13, 2009 at 10:16 AM, Michael Hennebry wrote:
On Mon, 12 Oct 2009, Yaron Kretchmer wrote:

Thanks Michael
Yes, the differences (and the variables themselves) are bounded. We can
denote the the upper/lower limit for each variable/difference by the
constants l(x) and u(x).

The sets have seven extreme points each,
one for one value of (a,b) and two each for the others.

What would the formulation be in that case?

I think I'll let you do the math.
Each constraint will be tight at three of the extreme points.
That gives you three equations in four variables.
Scaling is allowed, so one of the variables may be fixed.
Check to make sure that the other extreme points satisfy the constraint.
If some slacks are positive and others negative,
the "facet" you have been deriving is invalid.
If all are nonpositive and three are zero, then the direction is wrong.

Note that you do not have to use constant bounds.
If the bounds depend on (a,b) that is just fine.
The narrower the bounds, the tighter the linear relaxation will be.
Narrowing bounds might be worth considerable effort.

][Michael Hennebry wrote:]

the feasible sets of (a,b,c-d) and (a,b,c-e)
have four extreme points.
Their convex hulls are tetrahedra.

]Yaron Kretchmer wrote:
Now I'd like to be able to model conditional non-binary variables. Does

]]][Yaron Kretchmer wrote:]

anybody know how to formulate this in mathprog?

----------Begin Description -------------------
*) a,b are binary
*) c,d,e is continuous.
*) I'd like c to be
- 0 if a=b=0
- d if a=0,b=1
- e if a=1,b=0
- 0 if a=b=1
----------End Description

--