On Dantzig-Wolfe Decomposition in Integer Programming and ways to Perform Branching in a Branch-and-Price Algorithm

François Vanderbeck ()
Additional contact information
François Vanderbeck: Mathématiques Appliquées Bordeaux, Université Bordeaux 1, 351, Cours de la Liberation, 33405 Talence Cedex, France

Operations Research, 2000, vol. 48, issue 1, 111-128

Abstract: Dantzig-Wolfe decomposition as applied to an integer program is a specific form of problem reformulation that aims at providing a tighter linear programming relaxation bound. The reformulation gives rise to an integer master problem, whose typically large number of variables is dealt with implicitly by using an integer programming column generation procedure, also known as branch-and-price algorithm. There is a large class of integer programs that are well suited for this solution technique. In this paper, we propose to base the Dantzig-Wolfe decomposition of an integer program on the discretization of the integer polyhedron associated with a subsystem of constraints (as opposed to its convexification). This allows us to formulate the integrality restriction directly on the master variables and sets a theoretical framework for dealing with specific issues such as branching or the introduction of cutting planes in the master. We discuss specific branching schemes and their effect on the structure of the column generation subproblem. We give theoretical bounds on the complexity of the separation process and the extent of the modifications to the column generation subproblem. Our computational tests on the cutting stock problem and a generalisation---the cutting strip problem---show that, in practice, all fractional solutions can be eliminated using branching rules that preserve the tractability of the subproblem, but there is a trade-off between branching efficiency and subproblem tractability.

Keywords: Integer programming algorithms: decomposition; column generation; branch-and-price; Production/scheduling: cutting stock/trim (search for similar items in EconPapers)
Date: 2000
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (76)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.48.1.111.12453 (application/pdf)

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:inm:oropre:v:48:y:2000:i:1:p:111-128

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().