Volume computation for sparse Boolean quadric relaxations

作     者：Lee, Jon Skipper, Daphne 

作者机构：Univ Michigan Dept I&OE Ann Arbor MI 48109 USA US Naval Acad Dept Math Annapolis MD 21402 USA 

出 版 物：《DISCRETE APPLIED MATHEMATICS》 (离散应用数学)

年 卷 期：2020年第275卷

页      面：79-94页

核心收录：

学科分类：07[理学] 0701[理学-数学] 070101[理学-基础数学] 

基　　金：ONR [N00014-18-W-X00709] 

主　　题：Volume Boolean quadric polytope Correlation polytope Mixed-integer non-linear optimization Order polytope Counting linear extensions Bounded treewidth Cut polytope 

摘      要：Motivated by understanding the quality of tractable convex relaxations of intractable polytopes, Ko et al. gave a closed-form expression for the volume of a standard relaxation L(G) of the Boolean quadric polytope (also known as the (full) correlation polytope) P(G) of the complete graph G = K-n. We extend this work to structured sparse graphs. In particular, we (i) demonstrate the existence of an efficient algorithm for vol(L(G)) when G has bounded treewidth, (ii) give closed-form expressions (and asymptotic behaviors) for vol(L(G)) for all stars, paths, and cycles, and (iii) give a closed-form expression for vol(P(G)) for all cycles. Further, we demonstrate that when G is a cycle, the simple relaxation L(G) is a very close model for the much more complicated P(G). Additionally, we give some computational results demonstrating that this behavior of the cycle seems to extend to more complicated graphs. Finally, we speculate on the possibility of extending some of our results to cactii or even series-parallel graphs. (C) 2018 Elsevier B.V. All rights reserved.