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.
Citation
arXiv:1702.04813 [math.OC]
Article
View Extended formulations for convex hulls of some bilinear functions