Branching in branch-and-price: a generic scheme

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. How-ever, in the presence of multiple identical subsystems, the mapping to the original variable space typically induces symmetries. An alternative, but in 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 main concern because the pricing oracle on which the method relies might become obsolete beyond the root node. This paper presents a generic branching scheme with 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 proceeds by recursively partitioning the subproblem solution set. Branching constraints are enforced in the pricing problem instead of being dualized in a Lagrangian way. 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. For illustration, it is applied to cutting stock and bin packing problems: solving them to integrality without modifying the subproblem or expanding its variable space is a first