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

DOI10.1016/J.COR.2004.09.017zbMath1104.90057OpenAlexW2026880805MaRDI QIDQ2496025

Jouhaina Chaouachi Siala, Mohamed Haouari

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 algorithmLagrangian decompositionvolume algorithmprize collecting Steiner tree

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Trees (05C05) Approximation methods and heuristics in mathematical programming (90C59)

Related Items (12)

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

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

This page was built for publication: A hybrid Lagrangian genetic algorithm for the prize collecting Steiner tree problem