Big M method

The simplex algorithm is the original and still one of the most widely used methods for solving linear maximization problems. It is obvious that the points with the optimal objective must be reached on a vertex of the simplex which is the shape of feasible region of an LP (linear program). Points on the vertex of the simplex are represented as a basis. So, to apply the simplex algorithm which aims improve the basis until a global optima is reached, one needs to find a feasible basis first.

The trivial basis (all problem variables equal to 0) is not always part of the simplex. It is feasible if and only if all the constraints (except non-negativity) are less-than constraints and with positive constant on the right-hand side. The Big M method introduces surplus and artificial variables to convert all inequalities into that form and there by extends the simplex in higher dimensions to be valid in the trivial basis. It is always a vertex due to the positivity constraint on the problem variables inherent in the standard formulation of LP. 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 s_i and artificial variables a_i (as shown below).
4. Choose a large positive Value 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 s_i 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 − s₁ + 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.

However, the a-priori selection of an appropriate value for M is not trivial. A way to overcome the need to specify the value of M is described in {{cite journal|title=The Big-M method with the numerical infinite M|journal=Optimization Letters|volume=15|issue=1

|pages=2455–2468|year=2021|doi=10.1007/s11590-020-01644-6|first1=Marco|last1=Cococcioni|first2=Lorenzo|last2=Fiaschi|url=https://link.springer.com/article/10.1007/s11590-020-01644-6|hdl=11568/1061259|hdl-access=free}}. Other ways to find an initial basis for the simplex algorithm involves solving another linear program in an initial phase.

When used in the objective function, the Big M method sometimes refers to formulations of linear optimization problems in which violations of a constraint or set of constraints are associated with a large positive penalty constant, M.

In Mixed integer linear optimization the term Big M can also refer to use of a large term in the constraints themselves. For example the logical constraint $z\; =\; 0\; \backslash iff\; x\; =\; y$ where z is binary variable (0 or 1) variable refers to ensuring equality of variables only when a certain binary variable takes on one value, but to leave the variables "open" if the binary variable takes on its opposite value. For a sufficiently large M and z binary variable (0 or 1), the constraints

: $x\; -\; y\; \backslash leq\; M\; z$

: $x\; -\; y\; \backslash geq\; -M\; z$

ensure that when $z\; =\; 0$ then $x\; =\; y$. Otherwise, when $z\; =\; 1$, then $-M\; \backslash leq\; x\; -\; y\; \backslash leq\; M$, indicating that the variables x and y can have any values so long as the absolute value of their difference is bounded by $M$ (hence the need for M to be "large enough.") Thus it is possible to "encode" the logical constraint into a MILP problem.

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

Bibliography

• {{cite book|last1=Griva|first1=Igor|last2=Nash|first2=Stephan G.|last3=Sofer|first3=Ariela|author3-link= Ariela Sofer |title=Linear and Nonlinear Optimization|date=26 March 2009|isbn=978-0-89871-661-0|publisher=Society for Industrial Mathematics|edition=2nd}}

Discussion

• [https://web.archive.org/web/20091122222848/http://www.computing.dcu.ie/~lkillen/teach/CA427Simplexbigmexample.pdf Simplex – Big M Method], Lynn Killen, Dublin City University.
• [http://businessmanagementcourses.org/Lesson09TheBigMMethod.pdf The Big M Method], businessmanagementcourses.org
• [http://hutchies.iconbar.com/bigm.html The Big M Method], Mark Hutchinson
• [https://link.springer.com/content/pdf/10.1007/s11590-020-01644-6.pdf The Big-M Method with the Numerical Infinite M], a recently introduced parameterless variant
• [http://www.scik.org/index.php/jmcs/article/viewFile/4387/2182.pdf A THREE-PHASE SIMPLEX METHOD FOR INFEASIBLE AND UNBOUNDED LINEAR PROGRAMMING PROBLEMS], Big M method for M=1

{{Reflist}}

{{Optimization algorithms}}

Category:Linear programming

Category:Linear algebra