steiner problem in graphs

New Benchmark Instances for the Steiner Problem in Graphs

  • Marcus Poggi de Aragão
  • Celso C. Ribeiro
  • Isabel Rosseti
  • Eduardo Uchoa
  • Renato F. Werneck
    • Categories Combinatorial Optimization, Graphs and Matroids, Meta Heuristics Tags , ,

    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 … Read more

    A Hybrid GRASP with Perturbations for the Steiner Problem in Graphs

  • Celso C. Ribeiro
  • Eduardo Uchoa
  • Renato F. Werneck
    • Categories Meta Heuristics, Telecommunications, VLSI layout Tags , , , ,

    We propose and describe a hybrid GRASP with weight perturbations and adaptive path-relinking heuristic (HGP+PR) for the Steiner problem in graphs. In this multi-start approach, the greedy randomized construction phase of a GRASP is replaced by the use of several construction heuristics with a weight perturbation strategy that combines intensification and diversification elements, as in … Read more