|
|||||
|
|
Lower bounds for the Quadratic Minimum Spanning Tree Problem based on reduced cost computation |
|
| Affiliation: | 1. Fakultät für Mathematik, TU Dortmund, Germany;2. Dipartimento di Elettronica, Informazione e Bioingegneria, Politecnico di Milano, Milan, Italy;1. Yale University, New Haven, CT, USA;2. École Polytechnique Fédérale de Lausanne (EPFL), Lausanne, Switzerland;1. Facultad de Ciencias Económicas y Empresariales, Universidad de Valladolid, Avenida Valle Esgueva, 6, 47011 Valladolid, Spain;2. Facultad de Ciencias Sociales, Jurídicas y de la Comunicación, Universidad de Valladolid, Plaza de la Universidad, 1, 40005 Segovia, Spain;1. MOLTECH-Anjou, CNRS, UMR 6200, Université de Nantes, 2 rue de la Houssinière, BP 92208, Nantes Cedex 3, F-44322, France;2. Institut des Matériaux Jean Rouxel (IMN), CNRS, UMR 6502, 2 rue de la Houssinière, BP 32229, 44322, Nantes Cedex 3, France;3. Unité de Physique des Dispositifs à Semi-conducteurs, Université El Manar Faculté des Sciences de Tunis, Campus Universitaire, Tunis, 2092, Tunisia;4. IM2NP, CNRS, UMR 7334, Université d’Aix-Marseille, Domaine Universitaire de Saint-Jérôme, Service 231, 13 397, Marseille Cedex 20, France;5. LMVR, FST, Université Abdelmalek Essaidi, Tanger, Ancienne Route de l’Aéroport, Km 10, Ziaten, BP: 416, Morocco;6. Université Félix Houphouet-Boigny, Abidjan, Cote d''Ivoire |
| Abstract: | The Minimum Spanning Tree Problem (MSTP) is one of the most known combinatorial optimization problems. It concerns the determination of a minimum edge-cost subgraph spanning all the vertices of a given connected graph. The Quadratic Minimum Spanning Tree Problem (QMSTP) is a variant of the MSTP whose cost considers also the interaction between every pair of edges of the tree. In this paper we review different strategies found in the literature to compute a lower bound for the QMSTP and develop new bounds based on a reformulation scheme and some new mixed 0–1 linear formulations that result from a reformulation–linearization technique (RLT). The new bounds take advantage of an efficient way to retrieve dual information from the MSTP reduced cost computation. We compare the new bounds with the other bounding procedures in terms of both overall strength and computational effort. Computational experiments indicate that the dual-ascent procedure applied to the new RLT formulation provides the best bounds at the price of increased computational effort, while the bound obtained using the reformulation scheme seems to reasonably tradeoff between the bound tightness and computational effort. |
| Keywords: | Quadratic minimum spanning tree problem Lagrangian relaxation Reformulation–linearization technique Lower bound Dual-ascent approach Reduced costs |
| 本文献已被 ScienceDirect 等数据库收录！ | |