Dantzig–Wolfe decomposition

Dantzig–Wolfe decomposition

Dantzig–Wolfe decomposition is an algorithm for solving linear programming problems with special structure. It was originally developed by George Dantzig and Phil Wolfe and initially published in 1960[1]. Many texts on linear programming have sections dedicated to discussing this decomposition algorithm.[2][3][4][5][6][7]

Dantzig–Wolfe decomposition relies on delayed column generation for improving the tractability of large-scale linear programs. For most linear programs solved via the revised simplex algorithm, at each step, most columns (variables) are not in the basis. In such a scheme, a master problem containing at least the currently active columns (the basis) uses a subproblem or subproblems to generate columns for entry into the basis such that their inclusion improves the objective function.

Contents

Required form

In order to use Dantzig–Wolfe decomposition, the constraint matrix of the linear program must have a specific form. A set of constraints must be identified as "connecting", "coupling", or "complicating" constraints wherein many of the variables contained in the constraints have non-zero coefficients. The remaining constraints need to be grouped into independent submatrices such that if a variable has a non-zero coefficient within one submatrix, it will not have a non-zero coefficient in another submatrix. This description is visualized below:

DW Block Angular Matrix.jpg

The D matrix represents the coupling constraints and each Fi represents the independent submatrices. Note that it is possible to run the algorithm when there is only one F submatrix.

Problem reformulation

After identifying the required form, the original problem is reformulated into a master program and n subprograms. This reformulation relies on the fact that a non-empty, bounded convex polyhedron can be represented as a convex combination of its extreme points (or, in the case of an unbounded polyhedron, a convex combination of its extreme points and a weighted combination of its extreme rays).

Each column in the new master program represents a solution to one of the subproblems. The master program enforces that the coupling constraints are satisfied given the set of subproblem solutions that are currently available. The master program then requests additional solutions from the subproblem such that the overall objective to the original linear program is improved.

The algorithm

While there are several variations regarding implementation, the Dantzig–Wolfe decomposition algorithm can be briefly described as follows:

  1. Starting with a feasible solution to the reduced master program, formulate new objective functions for each subproblem such that the subproblems will offer solutions that improve the current objective of the master program.
  2. Subproblems are re-solved given their new objective functions. An optimal value for each subproblem is offered to the master program.
  3. The master program incorporates one or all of the new columns generated by the solutions to the subproblems based on those columns' respective ability to improve the original problem's objective.
  4. Master program performs x iterations of the simplex algorithm, where x is the number of columns incorporated.
  5. If objective is improved, goto step 1. Else, continue.
  6. The master program cannot be further improved by any new columns from the subproblems, thus return.

Implementation

There are examples of the implementation of Dantzig–Wolfe decomposition available in the AMPL [8] and GAMS[citation needed] mathematical modeling languages. There is a general, parallel implementation available[9] that leverages the GNU Linear Programming Kit.

The algorithm can be implemented such that the subproblems are solved in parallel, since their solutions are completely independent. When this is the case, there are options for the master program as to how the columns should be integrated into the master. The master may wait until each subproblem has completed and then incorporate all columns that improve the objective or it may choose a smaller subset of those columns. Another option is that the master may take only the first available column and then stop and restart all of the subproblems with new objectives based upon the incorporation of the newest column.

Another design choice for implementation involves columns that exit the basis at each iteration of the algorithm. Those columns may be retained, immediately discarded, or discarded via some policy after future iterations (for example, remove all non-basic columns every 10 iterations).

A recent (2001) computational evaluation of Dantzig-Wolfe in general and Dantzig-Wolfe and parallel computation is the PhD thesis by J. R. Tebboth[10]

See also

References

  1. ^ George B. Dantzig and Philip Wolfe. Decomposition Principle for Linear Programs. Operations Research 8 (1960) pp 101–111
  2. ^ Dimitris Bertsimas and John N. Tsitsiklis. Linear Optimization. Athena Scientific. 1997.
  3. ^ George B. Dantzig and Mukund N. Thapa. Linear Programming 2: Theory and Extensions. Springer. 1997.
  4. ^ Vašek Chvátal. Linear Programming. Macmillan. 1983
  5. ^ Maros, István; Mitra, Gautam (1996). "Simplex algorithms". In J. E. Beasley. Advances in linear and integer programming. Oxford Science. pp. 1–46. MR1438309. 
  6. ^ Maros, István (2003). Computational techniques of the simplex method. International Series in Operations Research & Management Science. 61. Boston, MA: Kluwer Academic Publishers. pp. xx+325. ISBN 1-4020-7332-1. MR1960274. 
  7. ^ Lasdon, Leon S. (2002). Optimization theory for large systems (reprint of the 1970 Macmillan ed.). Mineola, New York: Dover Publications, Inc.. pp. xiii+523. MR1888251. 
  8. ^ AMPL code repository with Dantzig–Wolfe example., accessed 2008-12-26.
  9. ^ Open source Dantzig-Wolfe implementation., accessed 2010-10-15.
  10. ^ Tebboth, James Richard (2001). A computational study of Dantzig-Wolfe decomposition (PhD thesis). University of Buckingham, United Kingdom. http://www.blisworthhouse.co.uk/OR/Decomposition/tebboth.pdf. 

Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать реферат

Look at other dictionaries:

  • Décomposition de Benders — La Décomposition de Benders est une technique d optimisation qui permet de trouver des solutions à des problèmes d optimisation linéaire de très grande taille ayant une structure de blocs. On rencontre souvent cette structure dans les… …   Wikipédia en Français

  • Cutting-plane method — In mathematical optimization, the cutting plane method is an umbrella term for optimization methods which iteratively refine a feasible set or objective function by means of linear inequalities, termed cuts. Such procedures are popularly used to… …   Wikipedia

  • Optimisation linéaire — En optimisation, qui est une branche des mathématiques, un problème d optimisation linéaire est un problème d optimisation dans lequel on minimise une fonction linéaire sur un polyèdre convexe. La fonction coût et les contraintes peuvent donc… …   Wikipédia en Français

  • 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

  • Theory of two-level planning — The Theory of two level planning, better known in the West as the Kornai Liptak decomposition, is a method for the decomposition of large linear programs into sub problems so as to make the solution of the overall problem easier. It provides a… …   Wikipedia

  • Génération de colonnes — La génération de colonnes est une méthode pour résoudre efficacement les programmes linéaires de grande taille[1]. Elle repose sur la décomposition de Dantzig Wolfe (en), qui consiste à décomposer l ensemble des contraintes en deux sous… …   Wikipédia en Français

  • Delayed column-generation — is an efficient algorithm for solving larger linear programs. The overarching idea is that many linear programs are too large to consider all the variables explicitly. Since most of the variables will be non basic and assume a value of zero in… …   Wikipedia

  • List of mathematics articles (D) — NOTOC D D distribution D module D D Agostino s K squared test D Alembert Euler condition D Alembert operator D Alembert s formula D Alembert s paradox D Alembert s principle Dagger category Dagger compact category Dagger symmetric monoidal… …   Wikipedia

  • Delayed column generation — is an efficient algorithm for solving larger linear programs.The overarching idea is that many linear programs are too large to consider all the variables explicitly. Since most of the variables will be non basic and assume a value of zero in the …   Wikipedia

  • Episodios de Numb3rs — Anexo:Episodios de Numb3rs Saltar a navegación, búsqueda La siguiente es una lista de episodios de la serie norteamericana NUMB3RS. Contenido 1 Estrenos y Lanzamientos en DVD 2 Primera temporada (2005) 3 Segunda temporada ( …   Wikipedia Español

Share the article and excerpts

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