Originally posted by: 88Simon88

Hello everybody

 

I want to linearize the following equations without using big m or upper bound. Note that I could linearize them with big m, but I don't like it.

1- L = X * G, where X is a binary variable and G and L are continuous variables. 

2- If K is between A and B, L = 1, otherwise L=0. If K is between B and C, M=1, otherwise M=0. and if K is between C and D, H=1, otherwise H=0. Note that L, M, and H are binary variables and A, B, C, and D are bounds. K is a continuous variable between A and D.

 

Best regards,

Siamak

 

#CPLEXOptimizers
#DecisionOptimization

Hi

have you had a look at

https://www.ibm.com/developerworks/community/forums/html/topic?id=aa9aa3db-4fbc-4209-a767-5b5e54902cbd&ps=25

?

regards

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: 88Simon88

There were three methods: in the third method, you used the upper bound of the x. What if I used the logical constraints? Should I expect that the runtime decrease? or there is no guarantee for that? 

I want to avoid big m in order to solve the model in a shorter runtime. As you know, the amount of the big m, can change the runtime that's why I want to remove the big m.

#CPLEXOptimizers
#DecisionOptimization

Hi

logical constraints are easier to write than big M IMHO

Have a look at http://www-01.ibm.com/support/docview.wss?uid=swg21400084

regards

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: EdKlotz

If you have to use large values of big M, indicator constraints like Alex recommended will almost certain run as fast or faster.    If you can use small values for big M because of small bounds on your variables,  the big M formulation will potentially be faster, but as long as CPLEX can deduce the bounds on the variables associated with the indicator constraints, CPLEX's presolve will recognize this and replace the big M constraints with indicator constraints.   The only drawback with using logical constraints like this is that CPLEX's translation of them may not be as precise as the one you could do, so sometimes the model size is larger.   But I suspect any performance challenge you face will come from the MIP branching, not the size of the node relaxations.

 

Given that indicator/logical constraints are easier to create, I suggest you try a few models with indicator constraints to assess performance.   Then, if performance falls short, and your can use reasonably small values of M without compromising the meaning of your constraints, you can always go back to that formulation.

 

If you have additional questions, please include the API or modeling tool you are using to call CPLEX.

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: 88Simon88

Thanks for your response, but when I am talking about removing big m, I mean to reformulate the abovementioned equations in order to have no more big M, even the upper bound. 

I also want to ask you a question, what do you mean by a small or large value of big M?

 

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: EdKlotz

Large values of big M can create numerical and performance issues.   See the technote at http://www-01.ibm.com/support/docview.wss?uid=swg21399984 for more details.   By large big M, I mean unnecessarily large relative to the meaning in the model.   For example, suppose you have continuous variables xj and a binary z with

 

c1: x1 - 1000000000 z <= 0

c2: x1 + x2 + ...+ xn <= 1000

xj >= 0

 

Here M = 1000000000 is large in the sense that it is larger than necessary and potentially creates the performance issues described in the above technote.   You could improve the formulation by noticing that constraint c2 implies an upper bound of 1000 on any xj, so you could change the first constraint to

c1better: x1 - 1000 z <= 0

 

M = 1000 is small in the sense that it won't have the tolerance issues described in the technote.   Furthermore, it is the smallest value you can use (at least based on the model info available so far) without compromising the meaning of the model.   

Fundamentally, a small value of M has two requirements:

 

1)   It's the smallest possible value you can use while preserving the meaning of the constraint in which it is used.

2)  It's smaller than 100000, as that is the threshold value for which the trickle flow issue in the above technote can strike given CPLEX's default integrality tolerance.

 

With this as background, let's return to your original goal of removing the big Ms.   If the big Ms are large, then indeed it is a good idea to try to remove the big Ms.   But if they are small, you don't need to.     Now, for the simple example of c1 and c2 above, CPLEX's presolve will deduce the upper bounds of 1000 on the xj and tighten the big M value from 1000000000 to 1000.   But not all examples are so simple; in some cases CPLEX may not be able to deduce tighter bounds, but you can use your model knowledge to do so.  

Getting back to your first example:

 

1- L = X * G, where X is a binary variable and G and L are continuous variables. 

you should determine the smallest legitimate value of M.   For example, suppose G and L have domains of [0,1000],  Then M = 1000 will be good enough, and you really don't need to worry about reformulating to get rid of the big Ms.   But if G and L have infinite upper bounds, and nothing else in the model implies significantly smaller upper bounds, then you would need a large big M value and really would be better off using indicators as Alex recommended.

 

Your second example is more complicated, but is essentially the same.   Figure out the smallest legitimate value of M that preserves the meaning of the constraint based on the various variable bounds.

You never did say why you wanted to get rid of the big Ms.   Was it due to the trickle flow issue discussed here, or something else?

 

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: 88Simon88

Thank you very much. 

#CPLEXOptimizers
#DecisionOptimization