- Title
- Extended formulations for convex hulls of some bilinear functions
- Creator
- Gupte, Akshay; Kalinowski, Thomas; Rigterink, Fabian; Waterer, Hamish
- Relation
- ARC.LP110200524 http://purl.org/au-research/grants/arc/LP110200524
- Relation
- Discrete Optimization Vol. 36, Issue May 2020, no. 100569
- Publisher Link
- http://dx.doi.org/10.1016/j.disopt.2020.100569
- Publisher
- Elsevier
- Resource Type
- journal article
- Date
- 2020
- Description
- 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.
- Subject
- extended formulation; convex hull; bilinear; quadratic; boolean quadric polytope
- Identifier
- http://hdl.handle.net/1959.13/1420442
- Identifier
- uon:37591
- Identifier
- ISSN:1572-5286
- Language
- eng
- Reviewed
- Hits: 1834
- Visitors: 1832
- Downloads: 0
| Thumbnail | File | Description | Size | Format |
|---|