Bounding the gap between the McCormick relaxation and the convex hull for bilinear functions. (English) Zbl 1384.90073

Summary: We investigate how well the graph of a bilinear function \(b:\;[0,1]^n\rightarrow \mathbb {R}\) 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 J. Luedtke et al. [ibid. 136, No. 2 (B), 325–351 (2012; Zbl 1286.90117)], 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\geqslant \sqrt{n}/4\). On the other hand, we prove that \(c\leqslant 600\sqrt{n}\), which improves the linear upper bound proved by Luedtke, Namazifar and Linderoth [loc. cit.]. In addition, we present an alternative proof for a result of R. Misener et al. [Optim. Methods Softw. 30, No. 1, 215–249 (2015; Zbl 1325.90071)] characterizing functions \(b\) for which the McCormick relaxation is equal to the convex hull.


90C26 Nonconvex programming, global optimization
90C20 Quadratic programming


Full Text: DOI arXiv


[1] Al-Khayyal, FA; Falk, JE, Jointly constrained biconvex programming, Math. Oper. Res., 8, 273-286, (1983) · Zbl 0521.90087
[2] Belotti, P; Lee, J; Liberti, L; Margot, F; Wächter, A, Branching and bounds tightening techniques for non-convex MINLP, Optim. Methods Softw., 24, 597-634, (2009) · Zbl 1179.90237
[3] Bollobás, B., Scott, A.D.: Discrepancy in graphs and hypergraphs. In: Györy, E., Katona, G.O.H., Lovász, L. (eds.) Bolyai Society Mathematical Studies, pp. 33-56. Springer, Berlin (2006) · Zbl 0881.90099
[4] Chazelle, B.: The Discrepancy Method. Randomness and Complexity. Cambridge University Press, Cambridge (2000) · Zbl 0960.65149
[5] Crama, Y, Concave extensions for nonlinear \(0-1\) maximization problems, Math. Program., 61, 53-60, (1993) · Zbl 0796.90040
[6] Erdős, P; Spencer, J, Imbalances in k-colorations, Networks, 1, 379-385, (1971) · Zbl 0248.05114
[7] Erdős, P; Goldberg, M; Pach, J; Spencer, J, Cutting a graph into two dissimilar halves, J. Graph Theory, 12, 121-131, (1988) · Zbl 0655.05059
[8] Haagerup, U, The best constants in the Khintchine inequality, Stud. Math., 70, 231-283, (1981) · Zbl 0501.46015
[9] Horst, R., Tuy, H.: Global Optimization: Deterministic Approaches, 3rd edn. Springer, Berlin (2013) · Zbl 0704.90057
[10] Luedtke, J; Namazifar, M; Linderoth, J, Some results on the strength of relaxations of multilinear functions, Math. Program., 136, 325-351, (2012) · Zbl 1286.90117
[11] McCormick, GP, Computability of global solutions to factorable nonconvex programs: part I—convex underestimating problems, Math. Program., 10, 147-175, (1976) · Zbl 0349.90100
[12] Misener, R; Smadbeck, JB; Floudas, CA, Dynamically generated cutting planes for mixed-integer quadratically constrained quadratic programs and their incorporation into glomiqo 2, Optim. Methods Softw., 30, 215-249, (2014) · Zbl 1325.90071
[13] Nazarov, F.L., Podkorytov, A.N.: Ball, Haagerup, and distribution functions. In: Havin, V.P., Nikolski, N.K. (eds.) Complex Analysis, Operators, and Related Topics, pp. 247-267. Springer, Berlin (2000) · Zbl 0969.46014
[14] Nikolov, A.: Combinatorial discrepancy of the system of all cuts. Theoretical Computer Science Stack Exchange. http://cstheory.stackexchange.com/q/32072cstheory.stackexchange.com/q/32072 (version: July 26, 2015) · Zbl 0521.90087
[15] Rikun, AD, A convex envelope formula for multilinear functions, J. Glob. Optim., 10, 425-437, (1997) · Zbl 0881.90099
[16] Sahinidis, NV, BARON: a general purpose global optimization software package, J. Glob. Optim., 8, 201-205, (1996) · Zbl 0856.90104
[17] Sherali, HD, Convex envelopes of multilinear functions over a unit hypercube and over special discrete sets, Acta Math. Vietnam., 22, 245-270, (1997) · Zbl 0914.90205
[18] Smith, E; Pantelides, C, A symbolic reformulation/spatial branch-and-bound algorithm for the global optimisation of nonconvex minlps, Comput. Chem. Eng., 23, 457-478, (1999)
[19] Tawarmalani, M; Richard, J-P; Xiong, C, Explicit convex and concave envelopes through polyhedral subdivisions, Math. Program., 138, 531-577, (2012) · Zbl 1273.90165
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.