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

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.
Type de document :
Article dans une revue
Operations Research, INFORMS, 2000, 48 (1), pp.111-128
Liste complète des métadonnées

Contributeur : François Vanderbeck <>
Soumis le : jeudi 27 novembre 2008 - 19:32:40
Dernière modification le : jeudi 11 janvier 2018 - 06:21:22


  • HAL Id : inria-00342641, version 1




François Vanderbeck. On Dantzig-Wolfe Decomposition in Integer Programming and ways to Perform Branching in a Branch-and-Price Algorithm. Operations Research, INFORMS, 2000, 48 (1), pp.111-128. 〈inria-00342641〉



Consultations de la notice