Extended formulations for convex hulls of some bilinear functions

Akshay Gupte, Thomas Kalinowski, Fabian Rigterink, Hamish Waterer

Research output: Contribution to journalArticlepeer-review

Abstract

We consider the problem of characterizing the convex hull of the graph of a bilinear function on the -dimensional unit cube . 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 a systematic study of properties of 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 hull characterizations (Zuckerberg, 2016) to prove some initial results in this direction. In particular, we provide small-sized extended formulations for bilinear functions whose corresponding graph is either a cycle with arbitrary edge weights or a clique or an almost clique with unit edge weights.
Original languageEnglish
Article number100569
Number of pages34
JournalDiscrete Optimization
Volume36
Early online date15 Feb 2020
DOIs
Publication statusPublished - 31 May 2020

Fingerprint

Dive into the research topics of 'Extended formulations for convex hulls of some bilinear functions'. Together they form a unique fingerprint.

Cite this