Bland's rule

Bland's rule

In applied mathematics, Bland's rule (also known as Bland's algorithm or Bland's anti-cycling rule) is a technique used in the simplex method for ensuring that a linear optimization problem always converges to an answer. cite book | title = Combinatorial Optimization: Algorithms and Complexity | publisher = Dover Publications | author = Christos H. Papadimitriou, Kenneth Steiglitz | date = 1998-01-29 | pages = 53-55 ] cite web | url = http://www.cs.brown.edu/courses/csci1490/notes/day9.pdf | title = Notes on the Simplex Algorithm| accessdate = 2007-12-17 | author = Brown University - Department of Computer Science |date = 2007-10-18 ] Whenever there is a degenerate corner in the LP (e.g., when "Ax" = 0), then the simplex algorithm may cycle forever. Bland's rule can break these cycles by using a simple heuristic to decide which column to pivot on. It was developed by Cornell University Engineering professor Robert Bland.

Algorithm

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

# Choose the lowest-numbered (i.e., leftmost) nonbasic column "t" with a positive cost.
# Now among the rows choose the one with the lowest ratio between the cost and the index in the matrix where the index is greater than zero. If several rows have the same minimum ratio, choose the first one (i.e., topmost) of them.

References


Wikimedia Foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Look at other dictionaries:

  • Criticisms of communist party rule — Part of the series on Communism …   Wikipedia

  • Michael Bland — Birth name Michael Bland Also known as Michael B. (with The New Power Generation) Born March 14, 1969 (1969 03 14) (age 42) Origin Minneapolis, Minnesot …   Wikipedia

  • Slide rule — For other uses, see Slide rule (disambiguation). A typical ten inch student slide rule (Pickett N902 T simplex trig). The slide rule, also known colloquially as a slipstick,[1] is a mechanical analog computer. The slide rule is used primarily for …   Wikipedia

  • The Rule — Infobox Musical artist Name = Img capt = Img size = Background = group or band Birth name = Alias = Born = Died = Origin = Minnesota, United States Instrument = Genre = pop, R B, reggae Occupation = Years active = Label = R, R, R Records… …   Wikipedia

  • The Rule — (antes Ry and the Rule) es una venda americana de pop/R B. El grupo lanzó su primer álbum, uno mismo titulado verano de 2006, bajo etiqueta del indie R, R, R Records. Michael Bland, Tommy Barbarella, y Stokley Williams también se han realizado… …   Wikipedia Español

  • Criss-cross algorithm — This article is about an algorithm for mathematical optimization. For the naming of chemicals, see crisscross method. The criss cross algorithm visits all 8 corners of the Klee–Minty cube in the worst case. It visits 3 additional… …   Wikipedia

  • Oriented matroid — theory allows a combinatorial approach to the max flow min cut theorem. A network with the value of flow equal to the capacity of an s t cut An oriented matroid is a mathematical structure that abstracts the properties of directed graphs and of… …   Wikipedia

  • List of numerical analysis topics — This is a list of numerical analysis topics, by Wikipedia page. Contents 1 General 2 Error 3 Elementary and special functions 4 Numerical linear algebra …   Wikipedia

  • List of mathematics articles (B) — NOTOC B B spline B* algebra B* search algorithm B,C,K,W system BA model Ba space Babuška Lax Milgram theorem Baby Monster group Baby step giant step Babylonian mathematics Babylonian numerals Bach tensor Bach s algorithm Bachmann–Howard ordinal… …   Wikipedia

  • Category:Optimization algorithms — An optimization algorithm is an algorithm for finding a value x such that f(x) is as small (or as large) as possible, for a given function f, possibly with some constraints on x. Here, x can be a scalar or vector of continuous or discrete values …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”