Towards stronger Lagrangean bounds for stable spanning trees

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 {e_i, e_j} in C, at most one of the edges e_i and e_j 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 have recently initiated the combinatorial and polyhedral study of fixed cardinality stable sets [see https://doi.org/10.1016/j.dam.2021.01. 019], which motivates a new formulation for stable spanning trees based on Lagrangean Decomposition. By optimizing over the spanning tree polytope of G and the fixed cardinality stable set polytope of the conflict graph H=(E,C) in the subproblems, we are able to determine stronger Lagrangean bounds (equivalent to dualizing exponentially-many subtour elimination constraints), while limiting the number of multipliers in the dual problem to |E|. This naturally asks for more sophisticated dual algorithms, requiring the fewest iterations possible, and we derive a collection of Lagrangean dual ascent directions to this end.