Experimental validation of volume-based comparison for double-McCormick relaxations

DOI10.1007/978-3-319-59776-8_19zbMATH Open1492.90140arXiv1608.02527OpenAlexW2521846913MaRDI QIDQ2011595FDOQ2011595

Authors: Emily Speakman, Han Yu, Jon Lee 

Publication date: 4 August 2017

Abstract: Volume is a natural geometric measure for comparing polyhedral relaxations of non-convex sets. Speakman and Lee gave volume formulae for comparing relaxations of trilinear monomials, quantifying the strength of various natural relaxations. Their work was motivated by the spatial branch-and-bound algorithm for factorable mathematical-programming formulations. They mathematically analyzed an important choice that needs to be made whenever three or more terms are multiplied in a formulation. We experimentally substantiate the relevance of their main results to the practice of global optimization, by applying it to difficult box cubic problems (boxcup). In doing so, we find that, using their volume formulae, we can accurately predict the quality of a relaxation for boxcups based on the (box) parameters defining the feasible region.

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

Recommendations

• Algorithmic and modeling insights via volumetric comparison of polyhedral relaxations
• scientific article; zbMATH DE number 512535
• Stability and Separation in Volume Comparison Problems
• Assessment of the finite volume method applied to thev²−fmodel
• Validated Linear Relaxations and Preprocessing: Some Experiments
• Volume-discrepancy estimates in one and two dimensions
• Comparison of densities obtained with competing density functional molecular codes
• Numerical validation of the volume penalization method in three-dimensional pseudo-spectral simulations
• Convergence analysis of multivariate McCormick relaxations
• Volume comparison and its generalizations

zbMATH Keywords

global optimizationmixed integer nonlinear optimizationMcCormick inequalitiesspatial branch-and-boundtrilinear monomials

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Nonconvex programming, global optimization (90C26)

Cites Work

• Benchmarking optimization software with performance profiles.
• Two poset polytopes
• A random polynomial-time algorithm for approximating the volume of convex bodies
• ANTIGONE: algorithms for coNTinuous/Integer global optimization of nonlinear equations
• Computability of global solutions to factorable nonconvex programs: Part I — Convex underestimating problems
• Matroid polytopes and their volumes
• A convex envelope formula for multilinear functions
• A branch-and-reduce approach to global optimization
• Branching and bounds tighteningtechniques for non-convex MINLP
• Trilinear monomials with mixed sign domains: Facets of the convex and concave envelopes
• On convex relaxations of quadrilinear terms
• Title not available (Why is that?)
• SCIP: global optimization of mixed-integer nonlinear programs in a branch-and-cut framework
• Approximating polyhedra with sparse inequalities
• A decomposition of 2-weak vertex-packing polytopes
• Geometric comparison of combinatorial polytopes
• The volume of relaxed Boolean-quadric and cut polytopes
• On volumes of permutation polytopes
• Quantifying double McCormick

Cited In (5)

• Gaining or losing perspective
• Volume computation for sparse Boolean quadric relaxations
• On branching-point selection for trilinear monomials in spatial branch-and-bound: the hull relaxation
• Quantifying double McCormick
• Algorithmic and modeling insights via volumetric comparison of polyhedral relaxations

Uses Software

• BARON
• SCIP
• ANTIGONE

This page was built for publication: Experimental validation of volume-based comparison for double-McCormick relaxations

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