Big M method

In operations research, the Big M method is a method of solving linear programming problems using the simplex algorithm. The Big M method extends the power of the simplex algorithm to problems that contain "greater-than" constraints. It does so by associating the constraints with large negative constants which would not be part of any optimal solution, if it exists.

Algorithm

The simplex algorithm is the original and still one of the most widely used methods for solving linear maximization problems. However, to apply it, the origin (all variables equal to 0) must be a feasible point. This condition is satisfied only when all the constraints (except non-negativity) are less-than constraints with a positive constant on the right-hand side. The Big M method introduces surplus and artificial variables to convert all inequalities into that form. The "Big M" refers to a large number associated with the artificial variables, represented by the letter M.

The steps in the algorithm are as follows:

1. Multiply the inequality constraints to ensure that the right hand side is positive.
2. If the problem is of minimization, transform to maximization by multiplying the objective by -1
3. For any greater-than constraints, introduce surplus and artificial variables (as shown below)
4. Choose a large positive M and introduce a term in the objective of the form -M multiplying the artificial variables
5. For less-than or equal constraints, introduce slack variables so that all constraints are equalities
6. Solve the problem using the usual simplex method.

For example x + y ≤  100 becomes x + y + s₁ = 100, whilst x + y ≥ 100 becomes x + y − a₁ = 100. The artificial variables must be shown to be 0. The function to be maximised is rewritten to include the sum of all the artificial variables. Then row reductions are applied to gain a final solution.

The value of M must be chosen sufficiently large so that the artificial variable would not be part of any feasible solution.

For a sufficiently large M, the optimal solution contains any artificial variables in the basis (i.e. positive values) if and only if the problem is not feasible.

Other usage

The Big M method sometimes refers to any formulation of a linear optimization problem in which violations of a constraint are associated with a large positive penalty constant, M.

Another usage refers to using a large positive constant, M, to ensure that the constraint is not tight. For example, suppose x and y are ≥ 0. Then for a sufficiently large M and z binary variable (0 or 1), the following constraint ensures that when z=1, x=y:

See also

• Two phase method (linear programming) another approach for solving problems with >= constraints
• Karush–Kuhn–Tucker conditions, which apply to Non-Linear Optimization problems with inequality constraints.

References and external links

Bibliography

• Griva, Igor; Nash, Stephan G.; Sofer, Ariela. Linear and Nonlinear Optimization (2nd ed.). Society for Industrial Mathematics. ISBN 978-0-89871-661-0. 

Discussion

• Simplex – Big M Method, Lynn Killen, Dublin City University.
• The Big M Method, businessmanagementcourses.org
• The Big M Method, Mark Hutchinson

Optimization: Algorithms, methods, and heuristics   Unconstrained nonlinear: Methods calling … … functions Golden section search Interpolation methods Line search Nelder–Mead method Successive parabolic interpolation … and gradients Convergence Trust region Wolfe conditions Quasi–Newton BFGS and L-BFGS DFP Symmetric rank-one (SR1) Other methods Gauss–Newton Gradient Levenberg–Marquardt Conjugate gradient Truncated Newton … and Hessians Newton's method   Constrained nonlinear General Barrier methods Penalty methods Differentiable Augmented Lagrangian methods Sequential quadratic programming Successive linear programming   Convex optimization Convex minimization Cutting-plane method Reduced gradient (Frank–Wolfe) Subgradient method Linear and quadratic Interior point Affine scaling Ellipsoid algorithm of Khachiyan Projective algorithm of Karmarkar Basis-Exchange Simplex algorithm of Dantzig Revised simplex algorithm Criss-cross algorithm Principal pivoting algorithm of Lemke   Combinatorial Paradigms Approximation algorithm Dynamic programming Greedy algorithm Integer programming Branch & bound or cut Graph algorithms Minimum spanning tree Bellman–Ford Borůvka Dijkstra Floyd–Warshall Johnson Kruskal Network flows Dinic Edmonds–Karp Ford–Fulkerson Push–relabel maximum flow   Metaheuristics Evolutionary algorithm Hill climbing Local search Simulated annealing Tabu search Categories Algorithms and methods Heuristics Software