Exact solution approaches for the Multi-period Degree Constrained Minimum Spanning Tree Problem

Rosklin Juliano Chagas, Cristiano Arbex Valle and Alexandre Salles da Cunha

European Journal of Operational Research, 2018, vol. 271, issue 1, 57-71

Abstract: 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.

Keywords: Combinatorial optimization; Lagrangian relaxation; Branch and cut; Multi-period spanning trees (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221718303886
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:271:y:2018:i:1:p:57-71

DOI: 10.1016/j.ejor.2018.05.010

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().