help-glpk
[Top][All Lists]

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

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),
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 <
>
>> 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

--
"Pessimist: The glass is half empty.
Optimist:   The glass is half full.
Engineer:   The glass is twice as big as it needs to be."

```