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.
Citation
Research report, Catholic University of Rio de Janeiro, Department of Computer Science, August 2001.
Article
View New Benchmark Instances for the Steiner Problem in Graphs