Gupte, Akshay

Kalinowski, Thomas

Rigterink, Fabian

Waterer, Hamish

2020-05

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 a 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 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.

Discrete Optimization, v.36, p. 1-34

1873-636X

1572-5286

https://hdl.handle.net/1959.11/28554

Elsevier BV

Extended formulations for convex hulls of some bilinear functions

Journal Article

Publication