Skip to content
This repository has been archived by the owner on Aug 11, 2019. It is now read-only.

1 Home

Jump to bottom
edxu96 edited this page May 27, 2019 · 7 revisions

1, Introduction

Originally presented in (Dantzig and Wolfe, 1960), Dantzig-Wolfe decomposition can speed up and parallelize the solution of linear programs. With more and more advanced algorithms developed to solve linear programs, DW-decomp becomes less and less competitive. However, the adaptation of DW-decomp in Branch and Price algorithms has proven to be useful to solve MILP problems.

DW-decomp is composed of two parts:

  1. Dantzig-Wolfe Reformulation
  2. Dantzig-Wolfe Column Generation

Because there are usually too many variables in Dantzig Wolfe relaxation, it is usually solved using column generation.

According to the PhD thesis by James Richard Tebboth A Computational Study of Dantzig-Wolfe Decomposition:

Dantzig-Wolfe decomposition is an optimisation technique for solving large scale, block structured, linear programming (LP) problems. Problems from many different fields such as production planning, refinery optimisation, and resource allocation may be formulated as LP problems. Where there is some structure arising from repeated components in the problem, such as the handling of multi-periods, multi-locations, or multi-products, the problem may potentially be solved using Dantzig-Wolfe decomposition.

Dantzig-Wolfe decomposition will not rival mainstream techniques as an optimisation method for all LP problems. But we do show that Dantzig-Wolfe decomposition has some niche areas of application: certain large scale classes of primal block angular structured problems, and in particular where the context demands rapid results using parallel optimisation, or near optimal solutions with a guaranteed quality.

LP optimisation software use two main classes of methods. The simplex method is a gradient descent method that moves along the edge of the feasible region [Chv83, Dan63]. Interior point methods (IPM) move through the interior of the feasible region [Wri97].

2, Algorithm Description

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

  • 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.
  • Subproblems are re-solved given their new objective functions. An optimal value for each subproblem is offered to the master program.
  • 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.
  • Master program performs x iterations of the simplex algorithm, where x is the number of columns incorporated.
  • If objective is improved, goto step 1. Else, continue.
  • The master program cannot be further improved by any new columns from the subproblems, thus return.

3, References

  1. Tebboth, J.R., 2001. A computational study of Dantzig-Wolfe decomposition. University of Buckingham.
  1. Wikipedia: Dantzig–Wolfe Decomposition
Clone this wiki locally