Valid inequalities and convex hulls for multilinear functions. (English) Zbl 1274.90499

Haouari, M. (ed.) et al., ISCO 2010. International symposium on combinatorial optimization. Papers based on the presentations at the symposium, Hammamet, Tunesia, March 24–26, 2010. Amsterdam: Elsevier. Electronic Notes in Discrete Mathematics 36, 805-812 (2010).
Summary: We study the convex hull of the bounded, nonconvex set \(M_n=\{(x_1,\ldots,x_n,x_{n+1})\in\mathbb{R}^{n+1}:x_{n+1}=\prod_{i=1}^nx_i;\ell_i\leq x_i\leq u_i, i=1,\ldots,n+1\}\) for any \(n\geq 2\). We seek to derive strong valid linear inequalities for \(M_n\); this is motivated by the fact that many exact solvers for nonconvex problems use polyhedral relaxations so as to compute a lower bound via linear programming solvers.
We present a class of linear inequalities that, together with the well-known McCormick inequalities, defines the convex hull of \(M_2\). This class of inequalities, which we call lifted tangent inequalities, is uncountably infinite, which is not surprising given that the convex hull of \(M_2\) is not a polyhedron. This class of inequalities generalizes directly to \(M_n\) for \(n>2\), allowing us to define strengthened relaxations for these higher dimensional sets as well.
For the entire collection see [Zbl 1236.90011].


90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
90C27 Combinatorial optimization
Full Text: Link


[1] Adjiman, C. S.; Androulakis, I. P.; Maranas, C. D.; Floudas, C. A.: A global optimization method, \({\alpha}\)bb, for process design. Computers & chemical engineering 20, S419-S424 (1996)
[2] Al-Khayyal, F. A.; Falk, J. E.: Jointly constrained biconvex programming. Math. oper. Res. 8, 273-286 (1983) · Zbl 0521.90087
[3] Jach, M.; Michaels, D.; Weismantel, R.: The convex envelope of n-1 convex functions. SIAM journal on discrete optimization 19, No. 3, 1451-1466 (2008) · Zbl 1176.90467
[4] Karp, R. M.; Papadimitrou, C. H.: On linear characterizations of combinatorial optimization problems. SIAM journal on computing 11, 620-632 (1982) · Zbl 0505.65020
[5] Mccormick, G. P.: Nonlinear programming: theory, algorithms and applications. (1983) · Zbl 0563.90068
[6] Meyer, C. A.; Floudas, C. A.: Trilinear monomials with mixed sign domains: facets of the convex and concave envelopes. Journal of global optimization 29, No. 2 (2004) · Zbl 1085.90047
[7] Meyer, C. A.; Floudas, C. A.: Convex envelopes for edge-concave functions. Mathematical programming 103, 207-224 (2005) · Zbl 1099.90045
[8] Rikun, A. D.: A convex envelope formula for multilinear functions. Journal of global optimization 10, 425-437 (1997) · Zbl 0881.90099
[9] Tawarmalani, M.; Sahinidis, N. V.: Semidefinite relaxations of fractional programs via novel convexification techniques. Journal of global optimization 20, 137-158 (2001) · Zbl 1001.90064
[10] Tawarmalani, M.; Sahinidis, N. V.: Global optimization of mixed-integer nonlinear programs: A theoretical and computational study. Mathematical programming 99, No. 3, 563-591 (2004) · Zbl 1062.90041
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.