Component Bound Branching in a Branch-and-Price Framework

This paper integrates the component bound branching rule, originally proposed by Vanderbeck et al. [6, 7] and later reformulated by Desrosiers et al. [1], into the branch-price-and-cut solver GCG [2]. This rule, like Vanderbeck’s generic branching scheme [5], operates solely within the Dantzig-Wolfe reformulated problem, where branching decisions often lack corresponding actions in the original formulation. The current GCG framework requires modifications to accommodate such branching rules, particularly within the pricing loop. This paper’s significant contribution is enhancing the GCG architecture to seamlessly integrate new branching rules that operate exclusively on the reformulated problem. This enhancement allows these rules to benefit from current and future improvements in the branch-price-and-cut framework, including dual value stabilization, without necessitating changes to the branching rule itself. We propose an interface to manage such constraints in the master problem that lack counterparts in the original formulation. The generic mastercut interface, integrated into the GCG solver, spans the pricing loop, column generation, and dual value stabilization. The paper concludes with an evaluation, comparing the performance of the component bound branching rule to Vanderbeck’s generic branching scheme, as well as the impact of dual value stabilization on the component bound branching rule’s performance.