Dantzig-Wolfe and Lagrangian decompositions in integer linear programming

L. Létocart, A. Nagih and N. Touati-Moungla

International Journal of Mathematics in Operational Research, 2012, vol. 4, issue 3, 247-262

Abstract: We propose in this paper a new Dantzig-Wolfe master model based on Lagrangian Decomposition (LD). We establish the relationship with classical Dantzig-Wolfe decomposition master problem and propose an alternative proof of the dominance of LD on Lagrangian Relaxation (LR) dual bound. As illustration, we give the corresponding models and numerical results for two standard mathematical programs: the 0-1 bidimensional knapsack problem and the generalised assignment problem.

Keywords: Dantzig-Wolfe decomposition; column generation; Lagrangian relaxation; Lagrangian decomposition; 0-1 bidimensional knapsack problem; generalised assignment problem; modelling. (search for similar items in EconPapers)
Date: 2012
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.inderscience.com/link.php?id=46686 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:ids:ijmore:v:4:y:2012:i:3:p:247-262

Access Statistics for this article

More articles in International Journal of Mathematics in Operational Research from Inderscience Enterprises Ltd
Bibliographic data for series maintained by Sarah Parker ().