Volume computation for sparse Boolean quadric relaxations

DOI10.1016/J.DAM.2018.10.038MaRDI QIDQ2297660zbMATH OpenOpenAlexFDO

Authors Jon Lee, Daphne Skipper

Publication date 20 February 2020

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1703.02444

zbMATH Keywords

volumebounded treewidthcut polytopecorrelation polytopeBoolean quadric polytopeorder polytopecounting linear extensionsmixed-integer non-linear optimization

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Graph representations (geometric and intersection representations, etc.) (05C62) Boolean programming (90C09)

Abstract: 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 $mathscrQ(G)$ of the boolean quadric polytope (also known as the (full) correlation polytope) $mathscrP(G)$ of the complete graph $G=K_n$. We extend this work to structured sparse graphs, giving: (i) an efficient algorithm for $vol(mathscrQ(G))$ when $G$ has bounded tree width, (ii) closed-form expressions (and asymptotic behaviors) for $vol(mathscrQ(G))$ for all stars, paths, and cycles, and (iii) a closed-form expression for $vol(mathscrP(G))$ for all cycles. Further, we demonstrate that when $G$ is a cycle, the simple relaxation $mathscrQ(G)$ is a very close model for the much more complicated $mathscrP(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.

Recommendations

• Volume Computation for Boolean Combination of Linear Arithmetic Constraints
• Exploiting sparsity for semi-algebraic set volume computation
• The volume of relaxed Boolean-quadric and cut polytopes
• Gregory solid construction for polyhedral volume parameterization by sparse optimization
• Near-optimal deterministic algorithms for volume computation via M-ellipsoids
• Computational results of an \(O^{\ast }(n^{4})\) volume algorithm
• Algorithmic and modeling insights via volumetric comparison of polyhedral relaxations
• A sweep-plane algorithm for computing the volume of polyhedra represented in Boolean form
• The volume algorithm revisited: relation with bundle methods
• Bounds for sparse planar and volume arrays

Cites work

• scientific article; zbMATH DE number 6016068 (Why is no real title available?)
• scientific article; zbMATH DE number 3534524 (Why is no real title available?)
• scientific article; zbMATH DE number 1985302 (Why is no real title available?)
• scientific article; zbMATH DE number 2166874 (Why is no real title available?)
• scientific article; zbMATH DE number 2107839 (Why is no real title available?)
• scientific article; zbMATH DE number 854567 (Why is no real title available?)
• scientific article; zbMATH DE number 6157241 (Why is no real title available?)
• A decomposition of 2-weak vertex-packing polytopes
• A new separation algorithm for the Boolean quadric and cut polytopes
• A note on the Boolean quadric polytope
• A practical volume algorithm
• A short proof that the extension complexity of the correlation polytope grows exponentially
• A simultaneous lifting strategy for identifying new classes of facets for the Boolean quadric polytope
• A survey of alternating permutations
• Approximating polyhedra with sparse inequalities
• Correlation polytopes: Their geometry and complexity
• Counting linear extensions
• Experimental validation of volume-based comparison for double-McCormick relaxations
• Experiments in quadratic 0-1 programming
• Exponential lower bounds for polytopes in combinatorial optimization
• Extended formulations in combinatorial optimization
• Fast computation of Bernoulli, tangent and secant numbers
• Geometric algorithms and combinatorial optimization.
• Geometric comparison of combinatorial polytopes
• Geometry of cuts and metrics
• Globally solving nonconvex quadratic programming problems with box constraints via integer programming methods
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Incidence posets and cover graphs
• Mixed integer nonlinear programming. Selected papers based on the presentations at the IMA workshop mixed-integer nonlinear optimization: Algorithmic advances and applications, Minneapolis, MN, USA, November 17--21, 2008
• On The Boolean Quadric Forest Polytope
• On branching-point selection for trilinear monomials in spatial branch-and-bound: the hull relaxation
• On computing the number of linear extensions of a tree
• On integer recognition over some Boolean quadric polytope extension
• On the Boolean-quadric packing uncapacitated facility-location polytope
• On the complexity of calculating factorials
• On the complexity of computing prime tables
• On the maximum number of cycles in outerplanar and series-parallel graphs
• Quantifying double McCormick
• Solving Max-cut to optimality by intersecting semidefinite and polyhedral relaxations
• The Boolean quadratic polytope: Some characteristics, facets and relatives
• The cut polytope and the Boolean quadric polytope
• The tree- and clique-width of bipartite graphs in special classes
• The volume of relaxed Boolean-quadric and cut polytopes
• Two poset polytopes
• WEIGHTED DOMINATION NUMBER OF CACTUS GRAPHS

Cited in

(3)

• Gaining or losing perspective
• Counting linear extensions of restricted posets
• Algorithmic and modeling insights via volumetric comparison of polyhedral relaxations

Describes a project that uses

Uses Software

• Biq Mac

This page was built for publication: Volume computation for sparse Boolean quadric relaxations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2297660)