Stable set reformulations for the degree preserving spanning tree problem

Abílio Lucena and Alexandre Salles da Cunha

European Journal of Operational Research, 2024, vol. 319, issue 1, 50-61

Abstract: Let G=(V,E) be a connected undirected graph and assume that a spanning tree is available for it. Any vertex in this tree is called degree preserving if it has the same degree in the graph and in the tree. Building upon this concept, the Degree Preserving Spanning Tree Problem (DPSTP) asks for a spanning tree of G with as many degree preserving vertices as possible. DPSTP is very much intertwined with the most important application for it, so far, i.e., the online monitoring of arc flows in a water distribution network, what serves us as an additional motivation for our investigation. We show that degree preserving vertices correspond to a stable set of a properly defined DPSTP conflict graph. This, in turn, allows us to use valid inequalities for the Stable Set Polytope (SSP) and thus strengthen the DPSTP formulations previously suggested in the literature. In doing so, the Branch-and-cut and Benders Decomposition algorithms suggested for these formulations are greatly enhanced. Additionally, as a further contribution, we also introduce a new and very challenging set of DPSTP test instances, given by graphs that closely resemble water distribution networks. For these instances, the new algorithms very clearly outperform all previous DPSTP algorithms. They not only run faster than their competitors but are also less dependent on good initial DPSTP primal bounds. For previous DPSTP test sets, the new algorithms lag behind the best existing algorithm for them, which is based on Lagrangian relaxation. However, as compared to additional DPSTP previous algorithms that do not benefit from SSP inequalities, the new ones come much closer to the Lagrangian relaxation one.

Keywords: Combinatorial optimization; Degree preserving spanning trees; Stable set; Branch-and-cut algorithms; Combinatorial benders decomposition (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221724005113
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:319:y:2024:i:1:p:50-61

DOI: 10.1016/j.ejor.2024.06.031

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 ().