Branching in branch-and-price algorithms

Monday, July 25, 2005 - 3:15pm - 4:00pm
EE/CS 3-180
Francois Vanderbeck (Université de Bordeaux I)
In Branch-and-Price algorithms, implementing the branching scheme can be
challenging. Branching constraints may imply modifications to the pricing
problem. This is a main concern for the development of a generic
branch-and-price code that should run using only the pricing oracle
provided by the user. The issue has not stop people from using
Branch-and-Price. Firstly, branching is straightforward for many
applications (we shall
characterize the class of problem for which this is the
case). Then, Ryan and Foster (1981) proposed a scheme for applications
that can be reformulated as a set covering problem.
Beyond that, a general scheme was presented by Vanderbeck (2000) but
it may result in significant modifications to the pricing problem. An
alternative is the scheme of
Villeneuve et al. (2003) that consists in applying branching in the
original formulation, but this introduces symmetry in the
Dantzig-Wolfe reformulation when the problem structure involves
several identical blocks. The branching scheme presented here builds on
the aboves.
It can be can be implemented using only the oracle provided for the
original pricing problem.
Branching constraints are not dualized in a Lagrangian way but are
convexified in the