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 < > henne...@www.cs.ndsu.nodak.edu> 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 henne...@web.cs.ndsu.nodak.edu "Pessimist: The glass is half empty. Optimist: The glass is half full. Engineer: The glass is twice as big as it needs to be." _______________________________________________ Help-glpk mailing list Help-glpk@gnu.org http://lists.gnu.org/mailman/listinfo/help-glpk
