A hybrid Lagrangian genetic algorithm for the prize collecting Steiner tree problem

DOI10.1016/j.cor.2004.09.017zbMath1104.90057MaRDI QIDQ2496025

Mohamed Haouari, Jouhaina Chaouachi Siala

Publication date: 30 June 2006

Published in: Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.cor.2004.09.017

zbMATH Keywords

genetic algorithm; Lagrangian decomposition; volume algorithm; prize collecting Steiner tree

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

05C05: Trees

90C59: Approximation methods and heuristics in mathematical programming

Related Items

Stabilizing branch‐and‐price for constrained tree problems, Decomposition based hybrid metaheuristics, A hybridized Lagrangian relaxation and simulated annealing method for the course timetabling problem, A relax-and-cut algorithm for the prize-collecting Steiner problem in graphs, Algorithmic expedients for the prize collecting Steiner tree problem, Exact approaches for solving robust prize-collecting Steiner tree problems, The prize collecting Steiner tree problem: models and Lagrangian dual optimization approaches, Strength of Three MIP Formulations for the Prize Collecting Steiner Tree Problem with a Quota Constraint, Combining (Integer) Linear Programming Techniques and Metaheuristics for Combinatorial Optimization

Uses Software

• Knapsack

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on the prize collecting traveling salesman problem
• A Lagrangian heuristic for the Prize Collecting Travelling Salesman Problem
• A minimal algorithm for the multiple-choice knapsack problem
• Solving Steiner tree problems in graphs with Lagrangian relaxation
• The volume algorithm: Producing primal solutions with a subgradient method
• Strong lower bounds for the prize collecting Steiner problem in graphs
• Local search with perturbations for the prize-collecting Steiner tree problem in graphs
• An SST-based algorithm for the steiner problem in graphs
• The prize collecting traveling salesman problem
• New Approximation Guarantees for Minimum-Weight k-Trees and Prize-Collecting Salesmen
• The prize collecting traveling salesman problem: II. Polyhedral results
• Computing near‐optimal solutions to the steiner problem in a graph using a genetic algorithm
• Solving the Graphical Steiner Tree Problem Using Genetic Algorithms
• The Traveling-Salesman Problem and Minimum Spanning Trees