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.
Type de document :
Article dans une revue
Mathematical Programming, Series A, Springer, 2011, 130, pp.249-294. 〈10.1007/s10107-009-0334-1〉
Liste complète des métadonnées

Littérature citée [24 références]  Voir  Masquer  Télécharger
Contributeur : François Vanderbeck <>
Soumis le : lundi 23 novembre 2009 - 16:43:12
Dernière modification le : jeudi 11 janvier 2018 - 06:22:12
Document(s) archivé(s) le : jeudi 23 septembre 2010 - 10:56:54


Fichiers produits par l'(les) auteur(s)




François Vanderbeck. Branching in Branch-and-Price: a Generic Scheme. Mathematical Programming, Series A, Springer, 2011, 130, pp.249-294. 〈10.1007/s10107-009-0334-1〉. 〈inria-00311274v2〉



Consultations de la notice


Téléchargements de fichiers