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

DOI10.1007/978-3-319-59776-8_19MaRDI QIDQ2011595zbMATH OpenOpenAlexFDO

Authors Emily Speakman, Han Yu, Jon Lee

Publication date 4 August 2017

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

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)

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.

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

Cites work

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

Cited in

(5)

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

Describes a project that uses

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)