MISC: I want to understand Big M method with thorough explanation with examples
asked
Upendra Rawat Mark ♦ |

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.
answered
Mark ♦ |

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 :-)
answered
Bo Jensen ♦ |