Premium
Weighted Dantzig–Wolfe Decomposition for Linear Mixed‐integer Programming
Author(s) -
Wentges P.
Publication year - 1997
Publication title -
international transactions in operational research
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.032
H-Index - 52
eISSN - 1475-3995
pISSN - 0969-6016
DOI - 10.1111/j.1475-3995.1997.tb00071.x
Subject(s) - lagrangian relaxation , mathematics , mathematical optimization , decomposition , lagrangian , integer programming , linear programming , augmented lagrangian method , lagrange multiplier , relaxation (psychology) , convergence (economics) , decomposition method (queueing theory) , multiplier (economics) , discrete mathematics , ecology , biology , psychology , social psychology , macroeconomics , economics , economic growth
Dantzig–Wolfe decomposition can be used to solve the Lagrangian dual of a linear mixed‐integer programming problem ( MIP ) if the dual structure of the ( MIP ) is exploited via Lagrangian relaxation with respect to the complicating constraints. In the so‐called weighted Dantzig–Wolfe decomposition algorithm, instead of the optimal solution of the Dantzig–Wolfe master problem a specially weighted average of the previously constructed Lagrangian multipliers and the optimal solution of the master problem is used as Lagrangian multiplier for the next Lagrangian subproblem to be solved. A convergence proof of the weighted Dantzig–Wolfe decomposition algorithm is given, and some properties of this procedure together with computational results for the capacitated facility location problem are discussed.