×

zbMATH — the first resource for mathematics

Convexifications of rank-one-based substructures in QCQPs and applications to the pooling problem. (English) Zbl 07195873
Summary: We study sets defined as the intersection of a rank-one constraint with different choices of linear side constraints. We identify different conditions on the linear side constraints, under which the convex hull of the rank-one set is polyhedral or second-order cone representable. In all these cases, we also show that a linear objective can be optimized in polynomial time over these sets. Towards the application side, we show how these sets relate to commonly occurring substructures of a general quadratically constrained quadratic program. To further illustrate the benefit of studying quadratically constrained quadratic programs from a rank-one perspective, we propose new rank-one formulations for the generalized pooling problem and use our convexification results to obtain several new convex relaxations for the pooling problem. Finally, we run a comprehensive set of computational experiments and show that our convexification results together with discretization significantly help in improving dual bounds for the generalized pooling problem.

MSC:
90C20 Quadratic programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Sherali, HD; Adams, WP, A Reformulation-Linearization Technique for Solving Discrete and Continuous Nonconvex Problems (2013), Berlin: Springer Science & Business Media, Berlin
[2] Lasserre, JB, Global optimization with polynomials and the problem of moments, SIAM J. Optim., 11, 3, 796-817 (2001) · Zbl 1010.90061
[3] Ahmadi, A.A., Majumdar, A.: DSOS and SDSOS optimization: LP and SOCP-based alternatives to sum of squares optimization. In 2014 48th Annual Conference on Information Sciences and Systems (CISS), pp. 1-5. IEEE (2014)
[4] Al-Khayyal, FA; Falk, JE, Jointly constrained biconvex programming, Math. Op. Res., 8, 2, 273-286 (1983) · Zbl 0521.90087
[5] Ryoo, HS; Sahinidis, NV, Analysis of bounds for multilinear functions., J. Global Optim., 19, 4, 403-424 (2001) · Zbl 0982.90054
[6] Liberti, L.; Pantelides, CC, Convex envelopes of monomials of odd degree, J. Global Optim., 25, 2, 157-168 (2003) · Zbl 1030.90117
[7] Benson, HP, Concave envelopes of monomial functions over rectangles, Naval Res. Logist. (NRL), 51, 4, 467-476 (2004) · Zbl 1054.90056
[8] Meyer, CA; Floudas, CA, Trilinear monomials with mixed sign domains: Facets of the convex and concave envelopes, J. Global Optim., 29, 2, 125-155 (2004) · Zbl 1085.90047
[9] Belotti, P.; Miller, AJ; Namazifar, M., Valid inequalities and convex hulls for multilinear functions, Electron. Notes Discret. Math., 36, 805-812 (2010) · Zbl 1274.90499
[10] Bao, X.; Khajavirad, A.; Sahinidis, NV; Tawarmalani, M., Global optimization of nonconvex problems with multilinear intermediates, Math. Program. Comput., 7, 1, 1-37 (2015) · Zbl 1317.90243
[11] 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, 1, 215-249 (2015) · Zbl 1325.90071
[12] Del Pia, A.; Khajavirad, A., A polyhedral study of binary polynomial programs, Math. Op. Res., 42, 2, 389-410 (2016) · Zbl 1364.90225
[13] Sherali, HD, Convex envelopes of multilinear functions over a unit hypercube and over special discrete sets, Acta Mathematica Vietnamica, 22, 1, 245-270 (1997) · Zbl 0914.90205
[14] Rikun, AD, A convex envelope formula for multilinear functions, J. Global Optim., 10, 4, 425-437 (1997) · Zbl 0881.90099
[15] Meyer, CA; Floudas, CA, Convex envelopes for edge-concave functions, Math. Program., 103, 2, 207-224 (2005) · Zbl 1099.90045
[16] Tawarmalani, M.; Sahinidis, NV, Convexification and Global Optimization in Continuous and Mixed-Integer Nonlinear Programming: Theory, Algorithms, Software, and Applications (2002), Berlin: Springer Science & Business Media, Berlin · Zbl 1031.90022
[17] Tawarmalani, M.; Richard, JPP; Xiong, C., Explicit convex and concave envelopes through polyhedral subdivisions, Math. Program., 138, 1-47 (2013) · Zbl 1273.90165
[18] Tuy, H., Convex Analysis and Global Optimization (2016), Berlin: Springer, Berlin · Zbl 1362.90001
[19] Buchheim, C.; D’Ambrosio, C., Monomial-wise optimal separable underestimators for mixed-integer polynomial optimization, J. Global Optim., 67, 4, 759-786 (2017) · Zbl 1370.90153
[20] Crama, Y.; Rodríguez-Heck, E., A class of valid inequalities for multilinear 0-1 optimization problems, Discret. Optim., 25, 28-47 (2017) · Zbl 1387.90125
[21] Adams, W.; Gupte, A.; Xu, Y., Error bounds for monomial convexification in polynomial optimization, Math. Program., 175, 355-393 (2018) · Zbl 1412.90119
[22] Gupte, A., Kalinowski, T., Rigterink, F., Waterer, H.: Extended formulations for convex hulls of graphs of bilinear functions. arXiv preprint arXiv:1702.04813 (2017)
[23] Nguyen, T.T., Richard, J.-P.P., Tawarmalani, M.: Deriving the convex hull of a polynomial partitioning set through lifting and projection. Technical report, working paper (2013)
[24] Nguyen, T.T., Tawarmalani, M., Richard, J.-P.P.: Convexification techniques for linear complementarity constraints. In IPCO, volume 6655, pp. 336-348. Springer (2011) · Zbl 1341.90130
[25] Tawarmalani, M.; Richard, J-PP; Chung, K., Strong valid inequalities for orthogonal disjunctions and bilinear covering sets, Math. Program., 124, 1, 481-512 (2010) · Zbl 1198.90298
[26] Gupte, Akshay: Mixed integer bilinear programming with applications to the pooling problem. Ph.D. thesis, Georgia Institute of Technology (2011)
[27] Kocuk, B.; Dey, SS; Sun, XA, Matrix minor reformulation and SOCP-based spatial branch-and-cut method for the AC optimal power flow problem, Math. Program. Comput., 10, 4, 557-596 (2018) · Zbl 1411.90249
[28] Rahman, H., Mahajan, A.: Facets of a mixed-integer bilinear covering set with bounds on variables. arXiv preprint arXiv:1707.06712 (2017) · Zbl 1426.90192
[29] Davarnia, D.; Richard, J-PP; Tawarmalani, M., Simultaneous convexification of bilinear functions over polytopes with application to network interdiction, SIAM J. Optim., 27, 3, 1801-1833 (2017) · Zbl 1377.90066
[30] Li, O.; Vittal, V., Convex hull of the quadratic branch AC power flow equations and its application in radial distribution networks, IEEE Trans. Power Syst., 33, 1, 839-850 (2018)
[31] Burer S., Kılınç-Karzan, F.: How to convexify the intersection of a second order cone and a nonconvex quadratic. Math. Program. 162(1):393-429 (2017). 10.1007/s10107-016-1045-z · Zbl 1358.90095
[32] Modaresi, S.; Vielma, JP, Convex hull of two quadratic or a conic quadratic and a quadratic inequality, Math. Program., 164, 1-2, 383-409 (2017) · Zbl 1393.90074
[33] Dey, SS; Santana, A.; Wang, Y., New SOCP relaxation and branching rule for bipartite bilinear programs, Optim. Eng., 20, 307-336 (2018) · Zbl 1431.90148
[34] Burer, S.; Letchford, AN, On nonconvex quadratic programming with box constraints, SIAM J. Optim., 20, 2, 1073-1089 (2009) · Zbl 1201.90146
[35] Padberg, M., The boolean quadric polytope: some characteristics, facets and relatives, Math. Program., 45, 1-3, 139-172 (1989) · Zbl 0675.90056
[36] McCormick, GP, Computability of global solutions to factorable nonconvex programs: Part-convex underestimating problems, Math. Program., 10, 1, 147-175 (1976) · Zbl 0349.90100
[37] Bonami, P., Günlük, O., Linderoth, J.: Globally solving nonconvex quadratic programming problems with box constraints via integer programming methods. Math. Program. Comput., 10(3), 333-382 (2018). ISSN 1867-2957. 10.1007/s12532-018-0133-x · Zbl 1400.90239
[38] Bienstock, D., Chen, C., Munoz, G.: Outer-product-free sets for polynomial optimization and oracle-based cuts. arXiv preprint arXiv:1610.04604 (2016)
[39] Haverly, CA, Studies of the behavior of recursion for the pooling problem, ACM sigmap Bull., 25, 19-28 (1978)
[40] Gupte, A., Ahmed, Shabbir, D., Santanu S., Cheon, M.S.: Relaxations and discretizations for the pooling problem. J. Global Optim. 67(3), 631-669 (2017). ISSN 1573-2916. 10.1007/s10898-016-0434-4 · Zbl 1392.90117
[41] Ben-Tal, A., Nemirovski, A.: Lectures on modern convex optimization: analysis, algorithms, and engineering applications. SIAM (2001) · Zbl 0986.90032
[42] Santana, A., Dey, S.S.: The convex hull of a quadratic constraint over a polytope. arXiv preprint arXiv:1812.10160 (2018)
[43] Misener, R., Thompson, J.P., Floudas, C.A.: Apogee: global optimization of standard, generalized, and extended pooling problems via linear and logarithmic partitioning schemes. Computers and Chemical Engineering, 35(5), 876-892, 2011. ISSN 0098-1354. 10.1016/j.compchemeng.2011.01.026. http://www.sciencedirect.com/science/article/pii/S0098135411000366. Selected Papers from ESCAPE-20 (European Symposium of Computer Aided Process Engineering - 20), 6-9 June (2010), Ischia, Italy
[44] Dey, SS; Gupte, A., Analysis of MILP techniques for the pooling problem, Oper. Res., 63, 2, 412-427 (2015) · Zbl 1327.90351
[45] Alfaki, M.; Haugland, D., A multi-commodity flow formulation for the generalized pooling problem, J. Global Optim., 56, 3, 917-937 (2013) · Zbl 1272.90103
[46] Alfaki, M.; Haugland, D., Strong formulations for the pooling problem, J. Global Optim., 56, 3, 897-916 (2013) · Zbl 1272.90054
[47] Haugland, D., The computational complexity of the pooling problem, J. Global Optim., 64, 2, 199-215 (2016) · Zbl 1360.90258
[48] Luedtke, J., D’Ambrosio, C., Linderoth, J., Schweiger, J.: Strong convex nonlinear relaxations of the pooling problem. arXiv preprint arXiv:1803.02955 (2018)
[49] Haugland, D.; Hendrix, EMT, Pooling problems with polynomial-time algorithms, J. Optim. Theory Appl., 170, 2, 591-615 (2016) · Zbl 1346.90681
[50] Boland, N.; Kalinowski, T.; Rigterink, F., A polynomially solvable case of the pooling problem, J. Global Optim., 67, 3, 621-630 (2017) · Zbl 1365.90212
[51] Baltean-Lugojan, R.; Misener, R., Piecewise parametric structure in the pooling problem: from sparse strongly-polynomial solutions to NP-hardness, J. Global Optim., 71, 4, 655-690 (2018) · Zbl 1405.90103
[52] Adhya, N.; Tawarmalani, M.; Sahinidis, NV, A Lagrangian approach to the pooling problem, Ind. Eng. Chem. Res., 38, 5, 1956-1972 (1999)
[53] Boland, N.; Kalinowski, T.; Rigterink, F., New multi-commodity flow formulations for the pooling problem, J. Global Optim., 66, 4, 669-710 (2016) · Zbl 1369.90132
[54] Boland, N., Kalinowski, T., Rigterink, F., Savelsbergh, M.: A special case of the generalized pooling problem arising in the mining industry. Preprint at http://www.optimization-online.org/DB_HTML/2015/07/5025.html (2015)
[55] Marandi, A.; Dahl, J.; de Klerk, E., A numerical evaluation of the bounded degree sum-of-squares hierarchy of lasserre, toh, and yang on the pooling problem, Ann. Oper. Res., 265, 1, 67-92 (2018) · Zbl 1422.90039
[56] Misener, R., Floudas, C.A.: GloMIQO 2.2 test suite (ares.tamu.edu/glomiqo/test_suite.html) (2015)
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.