论文标题
多面体结果和稳定跨越树的拉格朗日界限
Polyhedral results and stronger Lagrangean bounds for stable spanning trees
论文作者
论文摘要
给定图形$ g =（v，e）$和一组$ c $的未订购的边缘对被认为处于冲突的边缘，$ g $中的一棵稳定的跨越树是一组$ t $ t $，以$ g $诱导一跨树，以至于每个$ \ weft \ weft \ lbrace e_i_i，e_jj \ rigges $ y y $ e $ $ e $ e $ e $ e c $ n c $ in con $ in con in con $ in con in con $在$ t $中。 Lagrangean算法的现有工作是发现最小重量稳定树木的最小重量问题的问题仅限于具有完整性属性的放松。我们利用了此问题的新放松：固定的基数稳定集合在基础冲突图中$ h =（e，c）$。我们发现相应多层的有趣属性，并确定拉格朗日分解框架中更强的双重界限，在$ g $的生成树polytope上进行优化，并在子副标中的固定基数稳定性稳定的集合$ h $。这相当于指数化许多子二级消除限制，同时将双重问题中的乘数数量限制为$ | e | $。它也是将拉格朗日放松与汇总物求解器的力量相结合的概念证明。我们使用双重方法来提出令人鼓舞的计算结果，该方法包括由Lagrangean Dual-AscentS确定的乘数初始化的体积算法。特别是，在200个基准实例中，约有146个最佳的限制；它实际上与75个情况下的最佳相匹配。所有实现都可以在免费的开源存储库中提供。
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.
