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)orcid ; 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:
1 files
File SizeFormat 
Show full item record

SCOPUSTM   
Citations

19
checked on Mar 9, 2024

Page view(s)

1,378
checked on May 7, 2023

Download(s)

4
checked on May 7, 2023
Google Media

Google ScholarTM

Check

Altmetric


Items in Research UNE are protected by copyright, with all rights reserved, unless otherwise indicated.