On integer programming models for the maximum 2-club problem and its robust generalizations in sparse graphs
On integer programming models for the maximum 2-club problem and its robust generalizations in sparse graphs
复制标题
DOI：
10.1016/j.ejor.2021.05.010
复制
发表时间：
2021-05
期刊：
影响因子：
--
通讯作者：
Alexander Veremyev;V. Boginski;E. Pasiliao;O. Prokopyev
中科院分区：
文献类型：
--
作者：
Alexander Veremyev;V. Boginski;E. Pasiliao;O. Prokopyev
研究了最大2-俱乐部问题，该问题的目标是找到一个最大基数的导出子图，其直径不超过2。这样的子图源于一个流行的基于直径的团松弛概念，因为子图是团当且仅当它的直径是1。在2-俱乐部中，每对不相邻的顶点都有一个共同的邻居;这种“2-hop”性质自然会出现在各种应用中。在本文中，通过利用有点不同的解释的问题，我们提供了两个新的混合整数规划（MIP）模型找到最大2俱乐部。我们的MIP提供了更紧密的线性规划（LP）松弛足够稀疏的图形，并有更少的限制比标准的整数规划（IP）模型的代价是有更多的连续变量。我们还考虑我们的MIP的可行性版本，验证是否存在一些指定大小的2-俱乐部。然后，我们将它们纳入一个简单的实现“可行性检查”算法，迭代解决每个可能的2俱乐部大小在一些已知的下限和上限的可行性MIP之一。上限是从LP松弛我们的新的MIP，并被证明是尖锐的。此外，我们将展示如何扩展我们的方法来解决一些“强大的”（攻击和故障容忍）概括的最大2俱乐部问题。最后，我们进行了广泛的计算研究，随机生成的和现实生活中的图形，以支持我们的理论结果，并提供一些经验的观察和见解。
We consider the maximum 2-club problem, which aims at finding an induced subgraph of maximum cardinality with the diameter at most two. Such subgraphs arise from a popular diameter-based clique relaxation concept, as a subgraph is a clique if and only if its diameter is one. In a 2-club every pair of non-adjacent vertices has a common neighbor; this “2-hop” property naturally arises in a variety of applications. In this paper, by exploiting a somewhat different interpretation of the problem, we provide two new mixed-integer programming (MIP) models for finding maximum 2-clubs. Our MIPs provide much tighter linear programming (LP) relaxations for sufficiently sparse graphs and have fewer constraints than the standard integer programming (IP) model at the expense of having slightly more continuous variables. We also consider feasibility versions of our MIPs that verify whether there exists a 2-club of some specified size. Then we incorporate them into a simple-to-implement “feasibility-check” algorithm that iteratively solves one of the feasibility MIPs for each possible 2-club size within some known lower and upper bounds. The upper bound is obtained from an LP relaxation of our new MIPs and is shown to be sharp. Furthermore, we show how to extend our approaches for solving some “robust” (attack- and failure-tolerant) generalizations of the maximum 2-club problem. Finally, we perform an extensive computational study with randomly generated and real-life graphs to support our theoretical results and to provide some empirical observations and insights.