Algorithmic and modeling insights via volumetric comparison of polyhedral relaxations

DOI10.1007/s10107-018-1272-6zbMath1394.52011OpenAlexW2798091936MaRDI QIDQ1650771

Jon Lee, Emily Speakman, Daphne E. Skipper

Publication date: 13 July 2018

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10107-018-1272-6

zbMATH Keywords

volumeglobal optimizationpolytopemonomialfacility locationfixed chargemixed-integer nonlinear optimizationvertex packingBoolean quadricspatial branch-and-bound

Mathematics Subject Classification ID

(n)-dimensional polytopes (52B11) Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Integer programming (90C10) Mixed integer programming (90C11) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Nonconvex programming, global optimization (90C26) Combinatorial optimization (90C27) Length, area, volume and convex sets (aspects of convex geometry) (52A38)

Related Items

Piecewise polyhedral formulations for a multilinear term, Counting linear extensions of restricted posets, Gaining or losing perspective for piecewise-linear under-estimators of convex univariate functions, Convex hull representations for bounded products of variables, Gaining or losing perspective for piecewise-linear under-estimators of convex univariate functions, Computing the volume of the convex hull of the graph of a trilinear monomial using mixed volumes, Extrapolating curvature lines in rough concept sketches using mixed-integer nonlinear optimization

Uses Software

• Sostools
• SCIP
• Bonmin
• ANTIGONE

Cites Work

• Unnamed Item
• An algorithmic framework for convex mixed integer nonlinear programs
• Nonlinear discrete optimization. An algorithmic theory
• Two poset polytopes
• The Boolean quadratic polytope: Some characteristics, facets and relatives
• Correlation polytopes: Their geometry and complexity
• Counting linear extensions
• A decomposition of 2-weak vertex-packing polytopes
• Geometric comparison of combinatorial polytopes
• The volume of relaxed Boolean-quadric and cut polytopes
• All-different polytopes
• Separating type-I odd-cycle inequalities for a binary-encoded edge-coloring formulation
• The cut polytope and the Boolean quadric polytope
• Convexification and global optimization in continuous and mixed-integer nonlinear programming. Theory, algorithms, software, and applications
• Threshold graphs and related topics
• On convex relaxations of quadrilinear terms
• Experimental validation of volume-based comparison for double-McCormick relaxations
• ANTIGONE: algorithms for coNTinuous/Integer global optimization of nonlinear equations
• Principles of combinatorics
• Parametric nonlinear discrete optimization over well-described sets and matroid intersections
• Polytope Volume Computation
• Branching and bounds tighteningtechniques for non-convex MINLP
• Quantifying Double McCormick
• SCIP: global optimization of mixed-integer nonlinear programs in a branch-and-cut framework
• Integer Polynomial Optimization in Fixed Dimension
• An enumeration of simplicial 4-polytopes with 8 vertices
• There Cannot be any Algorithm for Integer Programming with Quadratic Constraints