Optimization Online


Extended formulations for convex hulls of some bilinear functions

Akshay Gupte (agupte***at***clemson.edu)
Thomas Kalinowski (thomas.kalinowski***at***newcastle.edu.au)
Fabian Rigterink (fabian.rigterink***at***gmail.com)
Hamish Waterer (hamish.waterer***at***newcastle.edu.au)

Abstract: We consider the problem of characterizing the convex hull of the graph of a bilinear function $f$ on the $n$-dimensional unit cube $[0,1]^n$. Extended formulations for this convex hull are obtained by taking subsets of the facets of the Boolean Quadric Polytope (BQP). Extending existing results, we propose the systematic study of properties of $f$ that guarantee that certain classes of BQP facets are sufficient for an extended formulation. We use a modification of Zuckerberg's geometric method for proving convex characterizations [Geometric proofs for convex hull defining formulations, Operations Research Letters \textbf{44} (2016), 625--629] to prove some initial results in this direction. We complement our theoretical results with a computational study, in which we apply the BQP facets to random graphs and (quadratically constrained) quadratic programs to determine which of the inequalities are strongest in practice.

Keywords: extended formulation, convex hull, bilinear functions, boolean quadric polytope

Category 1: Integer Programming ((Mixed) Integer Nonlinear Programming )

Category 2: Combinatorial Optimization (Polyhedra )

Category 3: Global Optimization (Theory )

Citation: arXiv:1702.04813 [math.OC]

Download: [PDF]

Entry Submitted: 01/01/2018
Entry Accepted: 01/01/2018
Entry Last Modified: 04/18/2019

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society