Bland's rule

Last updated

In mathematical optimization, Bland's rule (also known as Bland's algorithm, Bland's anti-cycling rule or Bland's pivot rule) is an algorithmic refinement of the simplex method for linear optimization.

Contents

With Bland's rule, the simplex algorithm solves feasible linear optimization problems without cycling. [1] [2] [3]

The original simplex algorithm starts with an arbitrary basic feasible solution, and then changes the basis in order to decrease the minimization target and find an optimal solution. Usually, the target indeed decreases in every step, and thus after a bounded number of steps an optimal solution is found. However, there are examples of degenerate linear programs, on which the original simplex algorithm cycles forever. It gets stuck at a basic feasible solution (a corner of the feasible polytope) and changes bases in a cyclic way without decreasing the minimization target.

Such cycles are avoided by Bland's rule for choosing a column to enter and a column to leave the basis.

Bland's rule was developed by Robert G. Bland, now an Emeritus Professor of operations research at Cornell University, while he was a research fellow at the Center for Operations Research and Econometrics in Belgium. [1]

Algorithm

One uses Bland's rule during an iteration of the simplex method to decide first what column (known as the entering variable) and then row (known as the leaving variable) in the tableau to pivot on. Assuming that the problem is to minimize the objective function, the algorithm is loosely defined as follows:

  1. Choose the lowest-numbered (i.e., leftmost) nonbasic column with a negative (reduced) cost.
  2. Now among the rows, choose the one with the lowest ratio between the (transformed) right hand side and the coefficient in the pivot tableau where the coefficient is greater than zero. If the minimum ratio is shared by several rows, choose the row with the lowest-numbered column (variable) basic in it.

It can be formally proved that, with Bland's selection rule, the simplex algorithm never cycles, so it is guaranteed to terminate in a bounded time.

While Bland's pivot rule is theoretically important, from a practical perspective it is quite inefficient and takes a long time to converge. In practice, other pivot rules are used, and cycling almost never happens. [4] : 72–76 

Extensions to oriented matroids

In the abstract setting of oriented matroids, Bland's rule cycles on some examples. A restricted class of oriented matroids on which Bland's rule avoids cycling has been termed "Bland oriented matroids" by Jack Edmonds. Another pivoting rule, the criss-cross algorithm, avoids cycles on all oriented-matroid linear-programs. [5]

Notes

  1. 1 2 Bland (1977).
  2. ↑ Christos H. Papadimitriou, Kenneth Steiglitz (1998-01-29). Combinatorial Optimization: Algorithms and Complexity . Dover Publications. pp.  53–55. ISBN   9780486402581.
  3. ↑ Brown University - Department of Computer Science (2007-10-18). "Notes on the Simplex Algorithm" (PDF). Retrieved 2007-12-17.
  4. ↑ Gärtner, Bernd; Matoušek, Jiří (2006). Understanding and Using Linear Programming. Berlin: Springer. ISBN   3-540-30697-8.: 44–48 
  5. ↑ Fukuda, Komei; Terlaky, Tamás (1997). Thomas M. Liebling; Dominique de Werra (eds.). "Criss-cross methods: A fresh view on pivot algorithms" (PDF). Mathematical Programming, Series B. Amsterdam: North-Holland Publishing Co. 79 (1–3): 369–395. doi:10.1007/BF02614325. MR   1464775. S2CID   2794181.

Further reading

Related Research Articles

Linear programming Method to solve some optimization problems

Linear programming is a method to achieve the best outcome in a mathematical model whose requirements are represented by linear relationships. Linear programming is a special case of mathematical programming.

Mathematical optimization Study of mathematical algorithms for optimization problems

Mathematical optimization or mathematical programming is the selection of a best element, with regard to some criterion, from some set of available alternatives. Optimization problems of sorts arise in all quantitative disciplines from computer science and engineering to operations research and economics, and the development of solution methods has been of interest in mathematics for centuries.

Greedy algorithm Sequence of locally optimal choices

A greedy algorithm is any algorithm that follows the problem-solving heuristic of making the locally optimal choice at each stage. In many problems, a greedy strategy does not produce an optimal solution, but a greedy heuristic can yield locally optimal solutions that approximate a globally optimal solution in a reasonable amount of time.

In mathematical optimization, Dantzig's simplex algorithm is a popular algorithm for linear programming.

An integer programming problem is a mathematical optimization or feasibility program in which some or all of the variables are restricted to be integers. In many settings the term refers to integer linear programming (ILP), in which the objective function and the constraints are linear.

Combinatorial optimization Subfield of mathematical optimization

Combinatorial optimization is a subfield of mathematical optimization that consists of finding an optimal object from a finite set of objects, where the set of feasible solutions is discrete or can be reduced to a discrete set. Typical combinatorial optimization problems are the travelling salesman problem ("TSP"), the minimum spanning tree problem ("MST"), and the knapsack problem. In many such problems, such as the ones previously mentioned, exhaustive search is not tractable, and so specialized algorithms that quickly rule out large parts of the search space or approximation algorithms must be resorted to instead.

The Fulkerson Prize for outstanding papers in the area of discrete mathematics is sponsored jointly by the Mathematical Optimization Society (MOS) and the American Mathematical Society (AMS). Up to three awards of $1,500 each are presented at each (triennial) International Symposium of the MOS. Originally, the prizes were paid out of a memorial fund administered by the AMS that was established by friends of the late Delbert Ray Fulkerson to encourage mathematical excellence in the fields of research exemplified by his work. The prizes are now funded by an endowment administered by MPS.

In mathematical optimization theory, the linear complementarity problem (LCP) arises frequently in computational mechanics and encompasses the well-known quadratic programming as a special case. It was proposed by Cottle and Dantzig in 1968.

Cutting-plane method Optimization technique for solving (mixed) integer linear programs

In mathematical optimization, the cutting-plane method is any of a variety of optimization methods that iteratively refine a feasible set or objective function by means of linear inequalities, termed cuts. Such procedures are commonly used to find integer solutions to mixed integer linear programming (MILP) problems, as well as to solve general, not necessarily differentiable convex optimization problems. The use of cutting planes to solve MILP was introduced by Ralph E. Gomory.

In mathematical optimization theory, duality or the duality principle is the principle that optimization problems may be viewed from either of two perspectives, the primal problem or the dual problem. If the primal is a minimization problem then the dual is a maximization problem. Any feasible solution to the primal (minimization) problem is at least as large as any feasible solution to the dual (maximization) problem. Therefore, the solution to the primal is an upper bound to the solution of the dual, and the solution of the dual is a lower bound to the solution of the primal. This fact is called weak duality.

Ellipsoid method

In mathematical optimization, the ellipsoid method is an iterative method for minimizing convex functions. When specialized to solving feasible linear optimization problems with rational data, the ellipsoid method is an algorithm which finds an optimal solution in a number of steps that is polynomial in the input size.

In mathematical optimization, linear-fractional programming (LFP) is a generalization of linear programming (LP). Whereas the objective function in a linear program is a linear function, the objective function in a linear-fractional program is a ratio of two linear functions. A linear program can be regarded as a special case of a linear-fractional program in which the denominator is the constant function one.

Oriented matroid

An oriented matroid is a mathematical structure that abstracts the properties of directed graphs, vector arrangements over ordered fields, and hyperplane arrangements over ordered fields. In comparison, an ordinary matroid abstracts the dependence properties that are common both to graphs, which are not necessarily directed, and to arrangements of vectors over fields, which are not necessarily ordered.

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 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.

Criss-cross algorithm

In mathematical optimization, the criss-cross algorithm is any of a family of algorithms for linear programming. Variants of the criss-cross algorithm also solve more general problems with linear inequality constraints and nonlinear objective functions; there are criss-cross algorithms for linear-fractional programming problems, quadratic-programming problems, and linear complementarity problems.

Klee–Minty cube

The Klee–Minty cube or Klee–Minty polytope is a unit hypercube of variable dimension whose corners have been perturbed. Klee and Minty demonstrated that George Dantzig's simplex algorithm has poor worst-case performance when initialized at one corner of their "squashed cube". On the three-dimensional version, the simplex algorithm and the criss-cross algorithm visit all 8 corners in the worst case.

Robert Gary Bland is an American mathematician and operations researcher, a professor of operations research and information engineering at Cornell University. He was born in New York City.

In mathematical optimization, the revised simplex method is a variant of George Dantzig's simplex method for linear programming.

Tamás Terlaky Hungarian mathematician (born 1955)

Tamás Terlaky is a Hungarian-Canadian-American professor of Industrial and Systems Engineering at Lehigh University. He is especially well known for his work on criss-cross algorithms, interior-point methods, Klee-Minty examples for path following algorithms, and optimization.

Komei Fukuda is a Japanese mathematician known for his contributions to optimization, polyhedral computation and oriented matroid theory. Fukuda is a professor in optimization and computational geometry in the Department of Mathematics and in the Institute of Theoretical Computer Science at ETH Zurich.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.