Re: [Help-glpk] More conditional variables fun

[Michael Hennebry]

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."