Assume that you have the LP problem: Max z = c'x - M Sum[ y_i ]
subject to Ax + y = b, b > 0, x > 0, y>0.
Assume that y is a vector of artificial variables. What is the smallest M to guarantee that, if the problem has an optimal solution, all y's are non-basic variables in the optimal solution?
Clearly, one does not want to use an arbitrarily large value for M because of rounding errors.
It will be better to use a value for M which is ateast 100 times larger than the largest value any of the variables in the specific LP problem.
A value for M must be at least 100 times larger than the largest value any of the variables in the specific LP problem.
Value of M should be such that it creates convex hull of the search space.
The suggestion that one selects M such that it is "at least 100 times larger than the largest value any of the variables" is not practical since there are many LP problems in which the feasible region is open and may not be an upper bound for all the decision variables.
I've always been told to set the M as large as necessary but no larger. If the M is too big it can cause problems solving sometimes.
@Michele, I am well aware of the pitfalls of the Big M method, but the question really is "If you are going to use a "big M" formulation, what is the smallest values of M that work in the context of the model" I would be very interested in the paper you wrote that addresses this question "(I once wrote a paper in which I analytically derived a sufficiently large but not horribly inflated value for M . There are tricks for doing so.)" This is mostly for teaching purposes since the Big M Method is discussed in almost every textbook. Thanks in advance.
@Paul, yes, I do not want a lower bound for M! (that would be an extremely large number) :-) ... The question is how to set up an upper bound (the smallest?) to guarantee that, if the problem has an optimal solution, all y's are non-basic variables in the optimal solution.
@Noel: sorry for the previous post, it was unclear,
The author of the link I posted before (http://orinanobworld.blogspot.fr/2011/07/perils-of-big-m.html) answered to a comment (by user Dewan, June 26, 2012) as follows:
"Dewan,
The paper is:
Rubin, P. A. (1990) Heuristic Solution Procedures for a Mixed-Integer Programming Discriminant Model. Managerial and Decision Economics 11, 255-266.
Calculation of the M values starts on the right side of page 257 and ends with equation (12). The calculations are quite specific to the particular application (discriminant analysis)."
Does this help?
Dear Noel,
please find below a numerical way to set M infinitely Big.
This assures that its value is always good:
Article The Big-M method with the numerical infinite M
This way, the big-m algorithm becomes parameter-less.
Of course, the I-Big-M method we have recently introduced is slower than the original Big-M method. This is the price to pay.
MC
- Badges
- Science topic
- Similar topics
- Books