On Dantzig-Wolfe Decomposition in Integer Programming and ways to Perform Branching in a Branch-and-Price Algorithm
Author:
- 1 February 2000
- journal article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Operations Research
- Vol. 48 (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
This publication has 15 references indexed in Scilit:
- Optimal Placement of Add/Drop Multiplexers: Heuristic and Exact AlgorithmsOperations Research, 1998
- A Unified Framework for Deterministic Time Constrained Vehicle Routing and Crew Scheduling Problems1998
- A Branch-and-Price Algorithm for the Generalized Assignment ProblemOperations Research, 1997
- An exact algorithm for IP column generationOperations Research Letters, 1996
- Solving binary cutting stock problems by column generation and branch-and-boundComputational Optimization and Applications, 1994
- Min-cut clusteringMathematical Programming, 1993
- Using separation algorithms to generate mixed integer model reformulationsOperations Research Letters, 1991
- OR-Library: Distributing Test Problems by Electronic MailJournal of the Operational Research Society, 1990
- The cutting stock problem and integer roundingMathematical Programming, 1985
- Lagrangean relaxation for integer programming1974