Please use this identifier to cite or link to this item:
https://hdl.handle.net/1959.11/26775
Title: | Bounding the gap between the McCormick relaxation and the convex hull for bilinear functions | Contributor(s): | Boland, Natashia (author); Dey, Santanu S (author); Kalinowski, Thomas (author) ; Molinaro, Marco (author); Rigterink, Fabian (author) | Publication Date: | 2017-03 | Early Online Version: | 2016-05-30 | DOI: | 10.1007/s10107-016-1031-5 | Handle Link: | https://hdl.handle.net/1959.11/26775 | Abstract: | We investigate how well the graph of a bilinear function : [0,1] ⁿ →R can be approximated by its McCormick relaxation. In particular, we are interested in the smallest number such that the difference between the concave upper bounding and convex lower bounding functions obtained from the McCormick relaxation approach is at most times the difference between the concave and convex envelopes. Answering a question of Luedtke, Namazifar and Linderoth, we show that this factor cannot be bounded by a constant independent of . More precisely, we show that for a random bilinear function we have asymptotically almost surely ≥ √/4. On the other hand, we prove that ≤ 600√, 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 for which the McCormick relaxation is equal to the convex hull. | Publication Type: | Journal Article | Grant Details: | ARC/LP110200524 | Source of Publication: | Mathematical Programming, 162(1–2), p. 523-535 | Publisher: | Springer | Place of Publication: | Germany | ISSN: | 1436-4646 0025-5610 |
Fields of Research (FoR) 2008: | 010303 Optimisation | Fields of Research (FoR) 2020: | 490304 Optimisation | Socio-Economic Objective (SEO) 2008: | 970101 Expanding Knowledge in the Mathematical Sciences | Socio-Economic Objective (SEO) 2020: | 280118 Expanding knowledge in the mathematical sciences | Peer Reviewed: | Yes | HERDC Category Description: | C1 Refereed Article in a Scholarly Journal |
---|---|
Appears in Collections: | Journal Article School of Science and Technology |
Files in This Item:
File | Size | Format |
---|
SCOPUSTM
Citations
20
checked on May 25, 2024
Page view(s)
1,502
checked on Jun 9, 2024
Download(s)
6
checked on Jun 9, 2024
Items in Research UNE are protected by copyright, with all rights reserved, unless otherwise indicated.