MISC: I want to understand Big M method with thorough explanation with examples

asked 18 Jul '10, 08:49

Upendra%20Rawat's gravatar image

Upendra Rawat
21112
accept rate: 0%

edited 18 Jul '10, 09:29

Mark's gravatar image

Mark ♦
3.6k22350


Big M method can be several things, most likely you refer to a penalty based approach. In LP it can be used as a feasibility trick i.e if you know a certain variable x_j should be fixed at is lower bound, then you can put a large penalty on it M > "large number". If M is chosen large enough, then x_j will be at lower bound in optimum. If M is not large enough, then M is increased and the optimizer is called again and so forth. Choosing "the best" is often an cumbersome process, since too large can cause numerical instability and too low can lead into too many re-optimizations. The described procedure is more or less the one used in lagrange relaxation methods. On the other hand big M methods can also mean different things, dependent on what context it is used in. If the question is asked in the modeling area, then I suggest reading the following book :

http://www.amazon.com/Model-Building-Mathematical-Programming-4th/dp/0471997889

Though it is old still good insight.

Google should also provide you with good information :-)

link

answered 18 Jul '10, 09:37

Bo%20Jensen's gravatar image

Bo Jensen ♦
5.0k2919
accept rate: 14%

There are two Big-M methods when it comes to linear programming. One is a method to solve the linear model with simplex (for finding an initial basic feasible solution) the other Big M method is a mathematical modeling technique for modeling linear and mixed integer problems. It allows you to include complex cases in your mathematical model. With this method you can model, "IF/ELSE", "OR" "AND" conditions. It is considered a bad practice because in commercial solvers your performance depends on how small your big-M really is.

References: The best book for learning this technique is "Introduction to Linear Optimization" by Dimitris Bertsimas and John N. Tsitsiklis they are both professors at MIT and I have been told that when they teach even other professors sit in their class. What I am saying is that it is a very famous and trustworthy book. (There is also a solution manual circling around the web, I have seen students using the solution manual but I have heard that solutions to some of the problems are incorrect so be careful). For the first Big-M method see pages 117-119. For the other one see chapter 10.

link

answered 18 Jul '10, 09:26

Mark's gravatar image

Mark ♦
3.6k22350
accept rate: 9%

Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • image?![alt text](/path/img.jpg "Title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported

Tags:

×231
×34

Asked: 18 Jul '10, 08:49

Seen: 10,287 times

Last updated: 18 Jul '10, 09:37

OR-Exchange! Your site for questions, answers, and announcements about operations research.