Robust branch-and-cut-and-price for the capacitated minimum spanning tree problem

Wednesday, July 27, 2005 - 4:00pm - 4:45pm
EE/CS 3-180
Eduardo Uchoa (Fluminense Federal University)
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.

Joint work with D.Andrade, R.Fukasawa, J.Lysgaard and M.Poggi de Aragao.