Volume computation for sparse Boolean quadric relaxations

DOI10.1016/j.dam.2018.10.038zbMath1433.90086arXiv1703.02444OpenAlexW2964046016MaRDI QIDQ2297660

Daphne E. Skipper, Jon Lee

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

volumecut polytopebounded treewidthcorrelation polytopeBoolean quadric polytopeorder polytopecounting linear extensionsmixed-integer non-linear optimization

Mathematics Subject Classification ID

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

Related Items

Gaining or losing perspective, Counting linear extensions of restricted posets

Uses Software

• Biq Mac

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A practical volume algorithm
• 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
• Solving Max-cut to optimality by intersecting semidefinite and polyhedral relaxations
• Approximating polyhedra with sparse inequalities
• Two poset polytopes
• The Boolean quadratic polytope: Some characteristics, facets and relatives
• Experiments in quadratic 0-1 programming
• Correlation polytopes: Their geometry and complexity
• Counting linear extensions
• On the Boolean-quadric packing uncapacitated facility-location polytope
• Geometric algorithms and combinatorial optimization.
• On computing the number of linear extensions of a tree
• A decomposition of 2-weak vertex-packing polytopes
• Geometric comparison of combinatorial polytopes
• The volume of relaxed Boolean-quadric and cut polytopes
• Globally solving nonconvex quadratic programming problems with box constraints via integer programming methods
• On branching-point selection for trilinear monomials in spatial branch-and-bound: the hull relaxation
• The cut polytope and the Boolean quadric polytope
• A simultaneous lifting strategy for identifying new classes of facets for the Boolean quadric polytope
• Experimental validation of volume-based comparison for double-McCormick relaxations
• A new separation algorithm for the Boolean quadric and cut polytopes
• A short proof that the extension complexity of the correlation polytope grows exponentially
• Incidence posets and cover graphs
• A note on the Boolean quadric polytope
• Exponential Lower Bounds for Polytopes in Combinatorial Optimization
• WEIGHTED DOMINATION NUMBER OF CACTUS GRAPHS
• A Survey of Alternating Permutations
• On Integer Recognition over Some Boolean Quadric Polytope Extension
• On the Complexity of Computing Prime Tables
• On the complexity of calculating factorials
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Quantifying Double McCormick
• Fast Computation of Bernoulli, Tangent and Secant Numbers
• Extended formulations in combinatorial optimization
• Geometry of cuts and metrics
• On the maximum number of cycles in outerplanar and series-parallel graphs
• On The Boolean Quadric Forest Polytope