- Title
- Bounding the gap between the McCormick relaxation and the convex hull for bilinear functions
- Creator
- Boland, Natashia; Dey, Santanu S.; Kalinowski, Thomas; Molinaro, Marco; Rigterink, Fabian
- Relation
- Funding BodyARCGrant NumberLP110200524 http://purl.org/au-research/grants/arc/LP110200524
- Relation
- Mathematical Programming Vol. 162, Issue 1-2, p. 523-535
- Publisher Link
- http://dx.doi.org/10.1007/s10107-016-1031-5
- Publisher
- Springer
- Resource Type
- journal article
- Date
- 2017
- Description
- We investigate how well the graph of a bilinear function b:[0,1]n → ℝ can be approximated by its McCormick relaxation. In particular, we are interested in the smallest number c such that the difference between the concave upper bounding and convex lower bounding functions obtained from the McCormick relaxation approach is at most c times the difference between the concave and convex envelopes. Answering a question of Luedtke, Namazifar and Linderoth, we show that this factor c cannot be bounded by a constant independent of n. More precisely, we show that for a random bilinear function b we have asymptotically almost surely c ⩾ √n/4. On the other hand, we prove that c ⩽ 600√n, which improves the linear upper bound proved by Luedtke, Namazifar and Linderoth. In addition, we present an alternative proof for a result of Misener, Smadbeck and Floudas characterizing functions b for which the McCormick relaxation is equal to the convex hull.
- Subject
- global optimization; bilinear function; convex hull
- Identifier
- http://hdl.handle.net/1959.13/1387314
- Identifier
- uon:32580
- Identifier
- ISSN:0025-5610
- Rights
- This is a post-peer-review, pre-copyedit version of an article published in Mathematical Programming. The final authenticated version is available online at: http://dx.doi.org/ 10.1007/s10107-016-1031-5.
- Language
- eng
- Full Text
- Reviewed
- Hits: 2997
- Visitors: 3450
- Downloads: 514
| Thumbnail | File | Description | Size | Format | |||
|---|---|---|---|---|---|---|---|
| View Details Download | ATTACHMENT02 | Author final version | 233 KB | Adobe Acrobat PDF | View Details Download |