Polyhedral results and stronger Lagrangean bounds for stable spanning trees
| Autor: | Phillippe Samer, Dag Haugland |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2022 |
| Předmět: |
FOS: Computer and information sciences
Control and Optimization Discrete Mathematics (cs.DM) Optimization and Control (math.OC) 90C27 90C57 (Primary) 90C10 52B05 52B12 (Secondary) FOS: Mathematics Mathematics - Combinatorics Business Management and Accounting (miscellaneous) Combinatorics (math.CO) G.2.2 Mathematics - Optimization and Control Computer Science - Discrete Mathematics |
| Zdroj: | Optimization Letters |
| Popis: | 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 $\left\lbrace e_i, e_j \right\rbrace \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 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 MILP 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. Comment: 24 pages |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|