Convex hull representations for bounded products of variables

Kurt M. Anstreicher (), Samuel Burer () and Kyungchan Park ()
Additional contact information
Kurt M. Anstreicher: University of Iowa
Samuel Burer: University of Iowa
Kyungchan Park: University of Iowa

Journal of Global Optimization, 2021, vol. 80, issue 4, No 2, 757-778

Abstract: Abstract It is well known that the convex hull of $$\{{(x,y,xy)}\}$$ { ( x , y , x y ) } , where (x, y) is constrained to lie in a box, is given by the reformulation-linearization technique (RLT) constraints. Belotti et al. (Electron Notes Discrete Math 36:805–812, 2010) and Miller et al. (SIAG/OPT Views News 22(1):1–8, 2011) showed that if there are additional upper and/or lower bounds on the product $$z=xy$$ z = x y , then the convex hull can be represented by adding an infinite family of inequalities, requiring a separation algorithm to implement. Nguyen et al. (Math Progr 169(2):377–415, 2018) derived convex hulls for $$\{(x,y,z)\}$$ { ( x , y , z ) } with bounds on $$z=xy^b$$ z = x y b , $$b\ge 1$$ b ≥ 1 . We focus on the case where $$b=1$$ b = 1 and show that the convex hull with either an upper bound or lower bound on the product is given by RLT constraints, the bound on z and a single second-order cone (SOC) constraint. With both upper and lower bounds on the product, the convex hull can be represented using no more than three SOC constraints, each applicable on a subset of (x, y) values. In addition to the convex hull characterizations, volumes of the convex hulls with either an upper or lower bound on z are calculated and compared to the relaxation that imposes only the RLT constraints. As an application of these volume results, we show how spatial branching can be applied to the product variable so as to minimize the sum of the volumes for the two resulting subproblems.

Keywords: Convex hull; Second-order cone; Bilinear product; Global optimization; 90C11; 90C20; 90C22; 90C25; 90C26 (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10898-021-01046-7 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jglopt:v:80:y:2021:i:4:d:10.1007_s10898-021-01046-7

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10898

DOI: 10.1007/s10898-021-01046-7

Access Statistics for this article

Journal of Global Optimization is currently edited by Sergiy Butenko

More articles in Journal of Global Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().