Exact solution approaches for the Multi-period Degree Constrained Minimum Spanning Tree Problem
| Autor: | Alexandre Salles da Cunha, Rosklin Juliano Chagas, Cristiano Arbex Valle |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
Mathematical optimization
021103 operations research Information Systems and Management General Computer Science Degree (graph theory) Computer science 0211 other engineering and technologies 0102 computer and information sciences 02 engineering and technology Management Science and Operations Research Minimum spanning tree 01 natural sciences Industrial and Manufacturing Engineering Degree-constrained spanning tree Vertex (geometry) symbols.namesake 010201 computation theory & mathematics Lagrangian relaxation Modeling and Simulation symbols Combinatorial optimization Relaxation (approximation) Branch and cut Integer programming |
| Zdroj: | European Journal of Operational Research. 271:57-71 |
| ISSN: | 0377-2217 |
| DOI: | 10.1016/j.ejor.2018.05.010 |
| Popis: | The Multi-period Degree Constrained Minimum Spanning Tree Problem (MP-DCMSTP) is defined in terms of a finite discretized planning horizon, an edge weighted undirected graph G, degree bounds and latest installation dates assigned to the vertices of G. Since vertices must be connected to a root node no later than their latest installation dates and edges’ weights are non-increasing over time, the problem asks for optimally choosing and scheduling edges’ installation over the planning horizon, enforcing connectivity of the solution at each time period, so that in the end of the planning horizon, a degree constrained spanning tree of G is found. We show that the decision version of a combinatorial relaxation for the problem, that of finding a Multi-period Minimum Spanning Tree Problem (MP-MSTP), is NP-Complete. We propose a new integer programming formulation for MP-DCMSTP that is at least as good as the multi-commodity flow formulation in the literature. We also introduce some new valid inequalities which allowed our strengthened formulation to produce the strongest known bounds to date. Two MP-DCMSTP exact algorithms exploring the strengthened formulation are introduced here. One of them, RCBC, is a hybrid method involving two phases, the first being a Lagrangian Relax-and-cut method that works as a pre-processor procedure to the second phase, a Branch-and-cut algorithm. The other approach, SRCBC, uses RCBC to solve a sequence of smaller MP-DCMSTP instances generated from the original one in the hope of solving the latter faster. Our computational results indicate that SRCBC solved more instances to proven optimality, generally in one fourth of the time taken by RCBC to solve similar instances. For those instances left unsolved by both, SRCBC also provided much better feasible solutions within the same CPU time limit. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect