Concave extensions for nonlinear 0-1 maximization problems

DOI10.1007/BF01582138zbMath0796.90040OpenAlexW2032797941MaRDI QIDQ689146

Yves Cramer

Publication date: 26 September 1994

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

Full work available at URL: https://doi.org/10.1007/bf01582138

zbMATH Keywords

linearizationconcave envelopebalanced matrixLP relaxationbinary hypercubeconcave extensionintegral polyhedronnonlinear 0-1 optimization

Mathematics Subject Classification ID

Nonlinear programming (90C30) Boolean programming (90C09)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unimodular functions
• Recognition problems for special classes of polynomials in 0-1 variables
• Alpha-balanced graphs and matrices and GF(3)-representability of matroids
• On the equivalence of paved-duality and standard linearization in nonlinear 0-1 optimization
• On the equivalence between roof duality and Lagrangian duality for unconstrained \(0\)-\(1\) quadratic programming problems
• The basic algorithm for pseudo-Boolean programming revisited
• Nonlinear 0–1 programming: I. Linearization techniques
• Extensions of functions of 0-1 variables and applications to combinatorial optimization
• Roof duality, complementation and persistency in quadratic 0–1 optimization
• Roof duality for polynomial 0–1 optimization
• Methods of Nonlinear 0-1 Programming
• Technical Note—Generalized Covering Relaxation for 0-1 Programs
• A Successive Underestimation Method for Concave Minimization Problems
• Technical Note—Converting the 0-1 Polynomial Programming Problem to a 0-1 Linear Program
• Convex Analysis

Related Items (31)

Graph, clique and facet of Boolean logical polytope ⋮ Non polyhedral convex envelopes for 1-convex functions ⋮ On decomposability of multilinear sets ⋮ Some results on the strength of relaxations of multilinear functions ⋮ Dynamically generated cutting planes for mixed-integer quadratically constrained quadratic programs and their incorporation into GloMIQO 2 ⋮ Error bounds for monomial convexification in polynomial optimization ⋮ On the impact of running intersection inequalities for globally solving polynomial optimization problems ⋮ On the strength of recursive McCormick relaxations for binary polynomial optimization ⋮ On the complexity of binary polynomial optimization over acyclic hypergraphs ⋮ Balanced matrices ⋮ Explicit convex and concave envelopes through polyhedral subdivisions ⋮ Optimization of Tree Ensembles ⋮ The Multilinear Polytope for Acyclic Hypergraphs ⋮ Existence and sum decomposition of vertex polyhedral convex envelopes ⋮ A polynomial-size extended formulation for the multilinear polytope of beta-acyclic hypergraphs ⋮ Two new reformulation convexification based hierarchies for 0-1 MIPs ⋮ Relaxations and discretizations for the pooling problem ⋮ Berge-acyclic multilinear 0-1 optimization problems ⋮ Bounding the gap between the McCormick relaxation and the convex hull for bilinear functions ⋮ A class of valid inequalities for multilinear 0-1 optimization problems ⋮ A technique to derive the analytical form of convex envelopes for some bivariate functions ⋮ Convex envelopes of bivariate functions through the solution of KKT systems ⋮ Pseudo-Boolean optimization ⋮ A multi-term, polyhedral relaxation of a 0-1 multilinear function for Boolean logical pattern generation ⋮ Convex envelopes for edge-concave functions ⋮ \(0\text{-}1\) multilinear programming as a unifying theory for LAD pattern generation ⋮ The Running Intersection Relaxation of the Multilinear Polytope ⋮ Piecewise polyhedral relaxations of multilinear optimization ⋮ Convex hull representations of special monomials of binary variables ⋮ Multilinear sets with two monomials and cardinality constraints ⋮ Global optimization of nonconvex problems with multilinear intermediates

This page was built for publication: Concave extensions for nonlinear 0-1 maximization problems