  


Extended formulations for convex hulls of some bilinear functions
Akshay Gupte (agupteclemson.edu) 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), 625629] 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 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  