Some results on the strength of relaxations of multilinear functions

DOI10.1007/s10107-012-0606-zzbMath1286.90117MaRDI QIDQ1925788

Mahdi Namazifar, Jeff Linderoth, James R. Luedtke

Publication date: 19 December 2012

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

Full work available at URL: http://digital.library.wisc.edu/1793/60714

zbMATH Keywords

global optimization; relaxation; convex envelopes; multilinear functions

Mathematics Subject Classification ID

90C26: Nonconvex programming, global optimization

Related Items

The Multilinear Polytope for Acyclic Hypergraphs, A Combinatorial Approach for Small and Strong Formulations of Disjunctive Constraints, On the Composition of Convex Envelopes for Quadrilinear Terms, Simultaneous Convexification of Bilinear Functions over Polytopes with Application to Network Interdiction, Convexification of Permutation-Invariant Sets and an Application to Sparse Principal Component Analysis, Solving multiplicative programs by binary-encoding the multiplication operation, (Global) optimization: historical notes and recent developments, On the strength of recursive McCormick relaxations for binary polynomial optimization, An effective global algorithm for worst-case linear optimization under polyhedral uncertainty, Global optimization advances in mixed-integer nonlinear programming, MINLP, and constrained derivative-free optimization, CDFO, Generalized decision rule approximations for stochastic programming via liftings, Relaxations and discretizations for the pooling problem, Bounding the gap between the McCormick relaxation and the convex hull for bilinear functions, Extended formulations for convex hulls of some bilinear functions, Deriving convex hulls through lifting and projection, Strong formulations for quadratic optimization with M-matrices and indicator variables, On linear programming relaxations for solving polynomial programming problems, On decomposability of multilinear sets, Convex and concave envelopes: revisited and new perspectives, A class of valid inequalities for multilinear 0-1 optimization problems, A note on solving DiDi's driver-order matching problem, Convex envelopes for ray-concave functions, Exact and approximate results for convex envelopes of special structured functions over simplices, Outer-product-free sets for polynomial optimization and oracle-based cuts, A new framework to relax composite functions in nonlinear programs, A branch and bound method for the solution of multiparametric mixed integer linear programming problems, An adaptive, multivariate partitioning algorithm for global optimization of nonconvex programs, New SOCP relaxation and branching rule for bipartite bilinear programs, Global optimization of nonconvex problems with multilinear intermediates, Error bounds for monomial convexification in polynomial optimization, Electricity swing option pricing by stochastic bilevel optimization: a survey and new approaches, Piecewise polyhedral formulations for a multilinear term, Perspective Reformulations of the CTA Problem with L₂ Distances, Dynamically generated cutting planes for mixed-integer quadratically constrained quadratic programs and their incorporation into GloMIQO 2

Uses Software

• BARON

Cites Work

• Unnamed Item
• Concave extensions for nonlinear 0-1 maximization problems
• The Boolean quadratic polytope: Some characteristics, facets and relatives
• Tight bounds and 2-approximation algorithms for integer programs with two variables per inequality
• A convex envelope formula for multilinear functions
• Convex envelopes of multilinear functions over a unit hypercube and over special discrete sets
• Convex envelopes for edge-concave functions
• A polyhedral branch-and-cut approach to global optimization
• BARON: A general purpose global optimization software package
• Multiterm polyhedral relaxations for nonconvex, quadratically constrained quadratic programs
• Branching and bounds tighteningtechniques for non-convex MINLP
• Jointly Constrained Biconvex Programming
• Computability of global solutions to factorable nonconvex programs: Part I — Convex underestimating problems
• A Successive Underestimation Method for Concave Minimization Problems
• Analysis of bounds for multilinear functions