Branching in Branch-and-Price: a Generic Scheme

François Vanderbeck 1, 2
2 Realopt - Reformulations based algorithms for Combinatorial Optimization
LaBRI - Laboratoire Bordelais de Recherche en Informatique, IMB - Institut de Mathématiques de Bordeaux, Inria Bordeaux - Sud-Ouest
Abstract : Developing a branching scheme that is compatible with the column generation procedure can be challenging. Application specific and generic schemes have been proposed in the literature, but they have their drawbacks. One generic scheme is to implement standard branching in the space of the compact formulation to which the Dantzig-Wolfe reformulation was applied. However, in the presence of multiple identical subsystems, the mapping to the original variable space typically induces symmetries. An alternative, in an application specific context, can be to expand the compact formulation to offer a wider choice of branching variables. Other existing generic schemes for use in branch-and-price imply modifications to the pricing problem. This is a concern because the pricing oracle on which the method relies might become obsolete beyond the root node. This paper presents a generic branching scheme in which the pricing oracle of the root node remains of use after branching (assuming that the pricing oracle can handle bounds on the subproblem variables). The scheme does not require the use of an extended formulation of the original problem. It proceeds by recursively partitioning the subproblem solution set. Branching constraints are enforced in the pricing problem instead of being dualized via Lagrangian relaxation, and the pricing problem is solved by a limited number of calls to the pricing oracle. This generic scheme builds on previously proposed approaches and unifies them. We illustrate its use on the cutting stock and bin packing problems. This is the first branch-and-price algorithm capable of solving such problems to integrality without modifying the subproblem or expanding its variable space.
Complete list of metadatas

https://hal.inria.fr/inria-00311274
Contributor : François Vanderbeck <>
Submitted on : Thursday, June 18, 2009 - 2:31:04 PM
Last modification on : Thursday, January 11, 2018 - 6:22:12 AM
Long-term archiving on : Tuesday, June 15, 2010 - 5:38:28 PM

File

gbrsRRInria0031274V3.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00311274, version 1

Citation

François Vanderbeck. Branching in Branch-and-Price: a Generic Scheme. Mathematical Programming, Series A, Springer, 2009, pp.48. ⟨inria-00311274v1⟩

Share

Metrics

Record views

12

Files downloads

548