New Benchmark Instances for the Steiner Problem in Graphs

Isabel Rosseti (rossetiinf.puc-rio.br)
Marcus Poggi de Aragão (poggiinf.puc-rio.br)
Celso Ribeiro (celsoinf.puc-rio.br)
Eduardo Uchoa (uchoainf.puc-rio.br)
Renato Werneck (rwerneckprinceton.edu)

Abstract: We propose in this work 50 new test instances for the Steiner problem in graphs. These instances are characterized by large integrality gaps and symmetry aspects which make them harder to both exact methods and heuristics than the test problems currently in use for the evaluation and comparison of existing and newly developed algorithms. Our computational results indicate that these new instances are not amenable to reductions by current preprocessing techniques and that not only do the linear programming lower bounds show large gaps, but they are also hard to be computed. State-of-the-art heuristics, which found optimal solutions for almost all test instances currently in use, faced much more difficulties for the new instances. Fewer optimal solutions were found and the numerical results are more discriminant, allowing a better assessment of the effectiveness and the relative behavior of different heuristics.

Keywords: Steiner problem in graphs, benchmark instances, test instances, algorithms

Category 1: Combinatorial Optimization

Category 2: Combinatorial Optimization (Meta Heuristics )

Category 3: Combinatorial Optimization (Graphs and Matroids )

Citation: Research report, Catholic University of Rio de Janeiro, Department of Computer Science, August 2001.

Download: [Compressed Postscript]

Entry Submitted: 09/26/2001
Entry Accepted: 09/26/2001
Entry Last Modified: 09/26/2001

Modify/Update this entry