dc.contributor.author | Samer, Phillippe | |
dc.contributor.author | Haugland, Dag | |
dc.date.accessioned | 2022-12-19T12:05:54Z | |
dc.date.available | 2022-12-19T12:05:54Z | |
dc.date.created | 2022-11-28T11:49:21Z | |
dc.date.issued | 2023 | |
dc.identifier.issn | 1862-4472 | |
dc.identifier.uri | https://hdl.handle.net/11250/3038498 | |
dc.description.abstract | Given a graph G=(V,E) and a set C of unordered pairs of edges regarded as being in conflict, a stable spanning tree in G is a set of edges T inducing a spanning tree in G, such that for each {ei,ej}∈C, at most one of the edges ei and ej is in T. The existing work on Lagrangean algorithms to the NP-hard problem of finding minimum weight stable spanning trees is limited to relaxations with the integrality property. We exploit a new relaxation of this problem: fixed cardinality stable sets in the underlying conflict graph H=(E,C). We find interesting properties of the corresponding polytope, and determine stronger dual bounds in a Lagrangean decomposition framework, optimizing over the spanning tree polytope of G and the fixed cardinality stable set polytope of H in the subproblems. This is equivalent to dualizing exponentially many subtour elimination constraints, while limiting the number of multipliers in the dual problem to |E|. It is also a proof of concept for combining Lagrangean relaxation with the power of integer programming solvers over strongly NP-hard subproblems. We present encouraging computational results using a dual method that comprises the Volume Algorithm, initialized with multipliers determined by Lagrangean dual-ascent. In particular, the bound is within 5.5% of the optimum in 146 out of 200 benchmark instances; it actually matches the optimum in 75 cases. All of the implementation is made available in a free, open-source repository. | en_US |
dc.language.iso | eng | en_US |
dc.publisher | Springer | en_US |
dc.rights | Navngivelse 4.0 Internasjonal | * |
dc.rights.uri | http://creativecommons.org/licenses/by/4.0/deed.no | * |
dc.title | Polyhedral results and stronger Lagrangean bounds for stable spanning trees | en_US |
dc.type | Journal article | en_US |
dc.type | Peer reviewed | en_US |
dc.description.version | publishedVersion | en_US |
dc.rights.holder | Copyright 2022 The Author(s) | en_US |
cristin.ispublished | true | |
cristin.fulltext | original | |
cristin.qualitycode | 1 | |
dc.identifier.doi | 10.1007/s11590-022-01949-8 | |
dc.identifier.cristin | 2082416 | |
dc.source.journal | Optimization Letters | en_US |
dc.source.pagenumber | 1317-1335 | |
dc.identifier.citation | Optimization Letters. 2023, 17, 1317-1335. | en_US |
dc.source.volume | 17 | |