Worst-case analysis of clique MIPs

• 成果类型: Article
• 署名作者: Naderi, Mohammad Javad; Buchanan, Austin; Walteros, Jose L.
• 署名单位: Oklahoma State University System; Oklahoma State University - Stillwater; State University of New York (SUNY) System; University at Buffalo, SUNY
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-021-01706-2
• 发表日期: 2022
• 页码: 517-551
• 关键词: maximum-clique; convex-hull; optimization; algorithm; graphs

摘要

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 just O(n + m) nonzeros for graphs with n vertices and m edges. Nevertheless, it ensures a root LP bound of at most d + 1, where d denotes the graph's degeneracy (a measure of density), and is solved in O(2(d)n) branch-and-bound nodes. Meanwhile, the strongest MIP that we propose visits fewer nodes, O(1.62(d)n). Further, when a best-bound node selection strategy is used, O(2(g)n) nodes are visited, where g = (d + 1) - omega is the clique-core gap. Often, g is so small that it can be treated as a constant in which case O (n) nodes are visited. Experiments are conducted to understand their performance in practice.