Dual heuristics on the exact solution of large Steiner problems
M. Poggi de Arag&o, E. Uchoa, R. Werneck, D. V. Andrade
Abstract in Proceedings of the 17th International Symposium on Mathematical Programming (ISMP 2000), Georgia Institute of Technology, USA, 2000.

Abstract: One of the best exact algorithms for the Steiner problem in graphsis Koch and Martin's branch-and-cut procedure (1998). The directed cut linear relaxation it employs generally yields lower bounds so close to the optimal IP value that the algorithm's bottleneck is solving the first LP, with exponentially many constraints. This paper presents a dual heuristic for the directed cut linear relaxation, consisting of a dual ascent procedure (similar to Wong's (1984)) followed by several dual adjustment methods and a scheme for actively fixing variables by reduced cost. We report detailed experiments with OR-Lib and SteinLib instances. Solutions are usually within 1% of the optimal value, with some instances (a few of which formerly open) being solved to optimality. Even when not optimal, dual solutions provide advanced bases for branch-and-cut procedures, leading to an exact algorithm one order of magnitude faster than Koch and Martin's for large instances.

[slides pdf]

Last Updated on January 3, 2006