Robust branch-and-cut-and-price for the capacitated minimum spanning tree problem
E. Uchoa, R. Fukasawa, J. Lysgaard, M. Poggi de Aragão, and D. V. Andrade
IMA Special Workshop: Mixed Integer Programming, Minnesota, USA, July 2005.

Abstract: We propose a new formulation for the capacitated minimum spanning tree problem that leads to a robust branch-and- cut-and-price algorithm. The formulation allows the use of cuts expressed over a very large set of variables, without changing the pricing subproblem or increasing the size of LPs that are actually solved. Cuts over those variables can be quite strong, and generalize many previous know families of cuts, including capacity, root cutsets and multistars. Computation results on benchmark instances from the OR-Library show very significant improvements over previously known algorithms, specially on non-unitary weight instances.

[slides pdf]

Last Updated on January 3, 2006