Extended formulations for convex hulls of some bilinear functions
From MaRDI portal
Publication:783025
DOI10.1016/j.disopt.2020.100569zbMath1474.90525arXiv1702.04813OpenAlexW3101108256MaRDI QIDQ783025
Fabian Rigterink, Hamish Waterer, Akshay Gupte, Thomas Kalinowski
Publication date: 30 July 2020
Published in: Discrete Optimization (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1702.04813
Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Nonconvex programming, global optimization (90C26)
Related Items (8)
Tractable Relaxations of Composite Functions ⋮ Convexifications of rank-one-based substructures in QCQPs and applications to the pooling problem ⋮ \(2 \times 2\)-convexifications for convex quadratic optimization with indicator variables ⋮ The Bipartite Boolean Quadric Polytope with Multiple-Choice Constraints ⋮ The Convex Hull of a Quadratic Constraint over a Polytope ⋮ A new framework to relax composite functions in nonlinear programs ⋮ New SOCP relaxation and branching rule for bipartite bilinear programs ⋮ Set characterizations and convex extensions for geometric convex-hull proofs
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Extended formulations for convex envelopes
- Relaxations and discretizations for the pooling problem
- Bounding the gap between the McCormick relaxation and the convex hull for bilinear functions
- On the extension complexity of combinatorial polytopes
- The Boolean quadratic polytope: Some characteristics, facets and relatives
- A convex envelope formula for multilinear functions
- Convex envelopes of multilinear functions over a unit hypercube and over special discrete sets
- Globally solving nonconvex quadratic programming problems with box constraints via integer programming methods
- Geometric proofs for convex hull defining formulations
- The cut polytope and the Boolean quadric polytope
- Some results on the strength of relaxations of multilinear functions
- Explicit convex and concave envelopes through polyhedral subdivisions
- A new separation algorithm for the Boolean quadric and cut polytopes
- A lift-and-project cutting plane algorithm for mixed 0-1 programs
- Computing convex hulls and counting integer points with \texttt{polymake}
- Solving Mixed Integer Bilinear Problems Using MILP Formulations
- Dynamically generated cutting planes for mixed-integer quadratically constrained quadratic programs and their incorporation into GloMIQO 2
- A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
- Analysis of MILP Techniques for the Pooling Problem
- On Nonconvex Quadratic Programming with Box Constraints
- Chvátal Cuts and Odd Cycle Inequalities in Quadratic 0–1 Optimization
- Computability of global solutions to factorable nonconvex programs: Part I — Convex underestimating problems
- Subset Algebra Lift Operators for 0-1 Integer Programming
- On the cut polytope
- Extended formulations in combinatorial optimization
- Geometry of cuts and metrics
This page was built for publication: Extended formulations for convex hulls of some bilinear functions
