P. Samer, D. Haugland
Given a graph G=(V,E) and a set of conflicting edge pairs C ⊆ E×E, a conflict-free spanning tree in G is a set of edges T inducing a spanning tree in G, such that for each (e,f) ∈ C, at most one of the edges e and f is in T. The existing work on Lagrangean algorithms to the NP-hard problem of finding minimum spanning trees under conflict constraints is limited to the most basic approach: using relaxations with the integrality property, and computing bounds with a standard subgradient algorithm.
We have recently initiated the combinatorial and polyhedral study of fixed cardinality stable sets, which motivates a new formulation for conflict-free spanning trees based on Lagrangean Decomposition. By optimizing over the forest polytope of G and the fixed cardinality stable set polytope of the conflict graph H=(E,C) in the subproblems, we are able to derive 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 leads to more sophisticated dual algorithms, requiring the fewest iterations possible, such as customized dual ascent, and the volume algorithm.
Keywords: Lagrangean decomposition, fixed cardinality, stable sets, spanning trees, conflict constraints, integer programming, combinatorial optimization
Scheduled
FB1 Graphs and Networks 2
June 11, 2021 10:45 AM
1 - GB Dantzig
