[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 12:42:35 +0400 |
On Tue, 13 Oct 2009, Yaron Kretchmer wrote:
> Michael,
> I'm sorry, but I didn't understand your explanation below- This is due to my
> limited LP/MIP understanding- sigh..
You might want to look up convex hull and facet.
> But, looking at the examples on
> http://www.aimms.com/aimms/download/manuals/AIMMS3OM_IntegerProgrammingTricks.pdfand
> doing some math led me to the following formulation:
> Is this close to what you were suggesting?
No. You have binary auxillary variables and big-Ms.
Note that big-Ms are bad news.
Doing logic with linear constraints on
binary variables isn't very good news.
Define continuous auxillary variable c_e = c - e .
The points in the feasible set are in
the convex hull of seven extreme points:
A: (0, 0, min(c_e, given a=b=0))
B: (0, 0, max(c_e, given a=b=0))
C: (0, 1, min(c_e, given a=0, b=1))
D: (0, 1, max(c_e, given a=0, b=1))
E: (1, 0, 0)
F: (1, 1, min(c_e, given a=b=1))
G: (1, 1, max(c_e, given a=b=1))
The mins could all be min(c) - max(e)
and similarly for the maxes,
but it's probably worth the efort to get narrower limits.
GLPK can help you with this.
1 2 3
(a,b,c_e) is a point in 3-space.
In 3-space the boundary of the set of points
that satisfy a linear constraint is a plane.
A plane is determined by 3 points not in a line.
Apparently you are interested in constraints that are tight at E.
You want a constraint of the form:
alpha*a + beta*b + gamma*c_e <= rhs .
You will need to solve for alpha, beta, gamma and rhs.
Tight at E implies
alpha*1 + beta*0 + gamma*0 = rhs
Picking two more extreme points will
give you three equations in four variables.
If the constraint will not be tight at (0, 0, 0),
add the constraint rhs=1.
If the constraint will be tight at (0, 0, 0),
try making alpha, beta or gamma =1.
Solve.
GLPK can do it, but doing it algebraically is probably better.
Find alpha*a + beta*b + gamma*c_e - rhs for all extreme points.
If they are all nonpositive, you have a valid constraint.
If they are all nonnegative, negate the results for a valid constraint.
If some are negative and some positive,
the points picked do not correspond to a valid constraint.
Note that at the tight points, rounding may produce nonzero values.
The others need testing.
I think the constraints you want are defined by
E, A, F and E, B, G.
> On Tue, Oct 13, 2009 at 10:16 AM, Michael Hennebry <
> address@hidden> 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).
>>>
>>
>> First, I made a mistake:
>> 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
--
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 <=
- Re: [Help-glpk] More conditional variables fun, Alexander Schnell, 2009/10/14
- Re: [Help-glpk] More conditional variables fun, Michael Hennebry, 2009/10/14