The prize collecting Steiner tree problem: models and Lagrangian dual optimization approaches |
| |
Authors: | Mohamed Haouari Safa Bhar Layeb Hanif D. Sherali |
| |
Affiliation: | (1) Combinatorial Optimization Research Group, ROI, Ecole Polytechnique de Tunisie, BP 743, 2078 La Marsa, Tunisia;(2) Grado Department of Industrial and Systems Engineering, Virginia Polytechnic Institute and State University, Blacksburg, VA 24061, USA |
| |
Abstract: | We propose a generalized version of the Prize Collecting Steiner Tree Problem (PCSTP), which offers a fundamental unifying model for several well-known -hard tree optimization problems. The PCSTP also arises naturally in a variety of network design applications including cable television and local access networks. We reformulate the PCSTP as a minimum spanning tree problem with additional packing and knapsack constraints and we explore various nondifferentiable optimization algorithms for solving its Lagrangian dual. We report computational results for nine variants of deflected subgradient strategies, the volume algorithm (VA), and the variable target value method used in conjunction with the VA and with a generalized Polyak–Kelley cutting plane technique. The performance of these approaches is also compared with an exact stabilized constraint generation procedure. |
| |
Keywords: | Steiner tree Lagrangian decomposition Nondifferentiable optimization |
本文献已被 SpringerLink 等数据库收录! |
|