On imposing connectivity constraints in integer programs
On imposing connectivity constraints in integer programs
复制标题
关于在整数程序中施加连通性约束
DOI：
10.1007/s10107-017-1117-8
复制
发表时间：
2017
影响因子：
2.7
通讯作者：
S. Butenko
中科院分区：
文献类型：
--
作者：
Yiming Wang;Austin Buchanan;S. Butenko
在许多网络应用程序中，搜索显示其他理想属性的连接的顶点子集。为此，本文研究了图的连通子图多面体，即引出连通子图的顶点子集的凸包。我们的大部分工作都致力于研究两类非平凡的有效不等式。第一种是a， b分隔不等式，在以前的计算研究中已经成功地用于加强连通性。第二种是积分不等式，以前已经证明它可以引出树的所有非平凡面。我们确定了这些不等式产生切面的精确条件，以及每个类完全描述连通子图多面体的精确条件。这两类不等式都可以在多项式时间内分离，并允许紧扩展公式。然而，虽然a， b分隔符不等式可以在线性时间内解除，但要解除积分不等式是NP-hard的。
In many network applications, one searches for a connected subset of vertices that exhibits other desirable properties. To this end, this paper studies the connected subgraph polytope of a graph, which is the convex hull of subsets of vertices that induce a connected subgraph. Much of our work is devoted to the study of two nontrivial classes of valid inequalities. The first are the a, b-separator inequalities, which have been successfully used to enforce connectivity in previous computational studies. The second are the indegree inequalities, which have previously been shown to induce all nontrivial facets for trees. We determine the precise conditions under which these inequalities induce facets and when each class fully describes the connected subgraph polytope. Both classes of inequalities can be separated in polynomial time and admit compact extended formulations. However, while the a, b-separator inequalities can be lifted in linear time, it is NP-hard to lift the indegree inequalities.
影响因子：
14.9
作者：
Backes C;Rurainski A;Klau GW;Müller O;Stöckel D;Gerasch A;Küntzer J;Maisel D;Ludwig N;Hein M;Keller A;Burtscher H;Kaufmann M;Meese E;Lenhof HP
通讯作者：
Lenhof HP