Worst-case analysis of clique MIPs
Worst-case analysis of clique MIPs
复制标题
DOI：
10.1007/s10107-021-01706-2
复制
发表时间：
2021-09
影响因子：
2.7
通讯作者：
M. J. Naderi;Austin Buchanan;J. Walteros
中科院分区：
文献类型：
--
作者：
M. J. Naderi;Austin Buchanan;J. Walteros
针对最大团问题的整数规划存在的一些问题，包括弱线性规划松弛、稀疏图上的约束和非零约束的二次数以及解最大团问题所需的分枝定界节点数的保证性差等，本文提出了一种新的混合整数规划（MIPs），该规划具有更好的最坏情况性质，特别是对于稀疏图。我们提出的最小MIP对于n个顶点和中边的图只有非零。尽管如此，它确保了根LP界至多，其中d表示图的退化（密度的度量），并在分支定界节点中求解。同时，我们提出的最强MIP访问较少的节点。此外，当使用最佳边界节点选择策略时，节点被访问，其中是cnc-核心间隙。通常，gis是如此之小，以至于它可以被视为一个常数，在这种情况下，O（n）个节点被访问。进行实验以了解其在实践中的性能。
The usual integer programming formulation for the maximum clique problem has several undesirable properties, including a weak LP relaxation, a quadratic number of constraints and nonzeros when applied to sparse graphs, and poor guarantees on the number of branch-and-bound nodes needed to solve it. With this as motivation, we propose new mixed integer programs (MIPs) for the clique problem that have more desirable worst-case properties, especially for sparse graphs. The smallest MIP that we propose has justnonzeros for graphs withnvertices andmedges. Nevertheless, it ensures a root LP bound of at most, whereddenotes the graph’s degeneracy (a measure of density), and is solved inbranch-and-bound nodes. Meanwhile, the strongest MIP that we propose visits fewer nodes,. Further, when a best-bound node selection strategy is used,nodes are visited, whereis the clique-core gap. Often,gis so small that it can be treated as a constant in which caseO(n) nodes are visited. Experiments are conducted to understand their performance in practice.