A hybrid Lagrangian genetic algorithm for the prize collecting Steiner tree problem |
| |
Authors: | Mohamed Haouari Jouhaina Chaouachi Siala |
| |
Affiliation: | 1. CORG—Laboratory of Mathematical Engineering, Ecole Polytechnique de Tunisie, BP 743, 2078 La Marsa, Tunisia;2. Institut des Hautes Etudes Commerciales Carthage |
| |
Abstract: | We consider the version of prize collecting Steiner tree problem (PCSTP) where each node of a given weighted graph is associated with a prize and where the objective is to find a minimum weight tree spanning a subset of nodes and collecting a total prize not less that a given quota Q. We present a lower bound and a genetic algorithm for the PCSTP. The lower bound is based on a Lagrangian decomposition of a minimum spanning tree formulation of the problem. The volume algorithm is used to solve the Lagrangian dual. The genetic algorithm incorporates several enhancements. In particular, it fully exploits both primal and dual information produced by Lagrangian decomposition. The proposed lower and upper bounds are assessed through computational experiments on randomly generated instances with up to 500 nodes and 5000 edges. For these instances, the proposed lower and upper bounds exhibit consistently a tight gap: in 76% of the cases the gap is strictly less than 2%. |
| |
Keywords: | Prize collecting Steiner tree Lagrangian decomposition Volume algorithm Genetic algorithm |
本文献已被 ScienceDirect 等数据库收录! |