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


FB1 Graphs and Networks 2
June 11, 2021  10:45 AM
1 - GB Dantzig

Latest news

  • 6/5/21
    Conference abstract book

Cookie policy

We use cookies in order to be able to identify and authenticate you on the website. They are necessary for the correct functioning of it, and therefore they can not be disabled. If you continue browsing the website, you are agreeing with their acceptance, as well as our Privacy Policy.

Additionally, we use Google Analytics in order to analyze the website traffic. They also use cookies and you can accept or refuse them with the buttons below.

You can read more details about our Cookie Policy and our Privacy Policy.