×

zbMATH — the first resource for mathematics

RLT-POS: reformulation-linearization technique-based optimization software for solving polynomial programming problems. (English) Zbl 1353.65052
Summary: In this paper, we introduce a reformulation-linearization technique-based open-source optimization software for solving polynomial programming problems (RLT-POS). We present algorithms and mechanisms that form the backbone of RLT-POS, including constraint filtering techniques, reduced RLT representations, and semidefinite cuts. When implemented individually, each model enhancement has been shown in previous papers to significantly improve the performance of the standard RLT procedure. However, the coordination between different model enhancement techniques becomes critical for an improved overall performance since special structures in the original formulation that work in favor of a particular technique might be lost after implementing some other model enhancement. More specifically, we discuss the coordination between (1) constraint elimination via filtering techniques and reduced RLT representations, and (2) semidefinite cuts for sparse problems. We present computational results using instances from the literature as well as randomly generated problems to demonstrate the improvement over a standard RLT implementation and to compare the performances of the software packages BARON, COUENNE, and SparsePOP with RLT-POS.

MSC:
65K05 Numerical mathematical programming methods
90C26 Nonconvex programming, global optimization
65Y15 Packaged methods for numerical algorithms
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Androulakis, IP; Maranas, CD; Floudas, CA, \(α \)BB: a global optimization method for general constrained nonconvex problems, J. Global Optim., 7, 337-363, (1995) · Zbl 0846.90087
[2] Anstreicher, KM, Semidefinite programming versus the reformulation-linearization technique for nonconvex quadratically constrained quadratic programming, J. Global Optim., 43, 471-484, (2009) · Zbl 1169.90425
[3] Anstreicher, KM, On convex relaxations for quadratically constrained quadratic programming, Math. Program., 136, 233-251, (2012) · Zbl 1267.90103
[4] Balas, E., Ceria, S., Cornuejols, G.: Mixed 0-1 programming by lift-and-project in a branch-and-cut framework (1996) · Zbl 0880.90105
[5] Bazaraa, M.S., Sherali, H.D., Shetty, C.M.: Nonlinear Programming: Theory and Algorithms, 3rd edn. Wiley, New York (2006) · Zbl 1140.90040
[6] 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
[7] Cafieri, S; Hansen, P; Létocart, L; Liberti, L; Messine, F; Klasing, R (ed.), Compact relaxations for polynomial programming problems, No. 7276, 75-86, (2012), Berlin
[8] Dalkiran, E; Sherali, H, Theoretical filtering of RLT bound-factor constraints for solving polynomial programming problems to global optimality, J. Global Optim., 57, 1147-1172, (2013) · Zbl 1282.90134
[9] Gill, PE; Murray, W; Saunders, MA, SNOPT: an SQP algorithm for large-scale constrained optimization, SIAM Rev., 47, 99-131, (2005) · Zbl 1210.90176
[10] Hock, W., Schittkowski, K.: Test Examples for Nonlinear Programming Codes, Lecture Notes in Economics and Mathematical Systems. Springer-Verlag, Berlin Heidelberg, New York (1981) · Zbl 0452.90038
[11] Ibm, ILOG CPLEX Optimization Studio. http://www.ilog.com/products/cplex
[12] Lasserre, JB, Semidefinite programming vs. LP relaxations for polynomial programming, Math. Operations Res., 27, 347-360, (2002) · Zbl 1082.90554
[13] Lasserre, JB, Convergent SDP-relaxations in polynomial optimization with sparsity, SIAM J. Optim., 17, 822-843, (2006) · Zbl 1119.90036
[14] Laurent, M; Rendl, F; Aardal, K (ed.); Nemhauser, G (ed.); Weismantel, R (ed.), Semidefinite programming and integer programming, 393-514, (2005), Amsterdam · Zbl 1194.90066
[15] Liberti, L, Linearity embedded in nonconvex programs, J. Global Optim., 33, 157-196, (2005) · Zbl 1124.90026
[16] Liberti, L; Pantelides, CC, An exact reformulation algorithm for large nonconvex NLPs involving bilinear terms, J. Global Optim., 36, 161-189, (2006) · Zbl 1131.90045
[17] MATLAB: version 7.12.0 (R2011a). The MathWorks Inc., Natick, Massachusetts (2011) · Zbl 1131.90045
[18] Ryoo, HS; Sahinidis, NV, A branch-and-reduce approach to global optimization, J. Global Optim., 8, 107-138, (1996) · Zbl 0856.90103
[19] Sherali, H.D., Adams, W.P.: A Reformulation-Linearization Technique for Solving Discrete and Continuous Nonconvex Problems. Kluwer Academic Publishers, Boston (1999) · Zbl 0926.90078
[20] Sherali, HD; Adams, WP, A reformulation-linearization technique (RLT) for semi-infinite and convex programs under mixed 0-1 and general discrete restrictions, Discrete Appl. Math., 157, 1319-1333, (2009) · Zbl 1176.90430
[21] Sherali, HD; Dalkiran, E, Combined bound-grid-factor constraints for enhancing RLT relaxations for polynomial programs, J. Global Optim., 51, 377-393, (2011) · Zbl 1229.90145
[22] Sherali, HD; Dalkiran, E; Desai, J, Enhancing RLT-based relaxations for polynomial programming problems via a new class of \(v\)-semidefinite cuts, Comput. Optim. Appl., 52, 483-506, (2012) · Zbl 1250.90092
[23] Sherali, HD; Dalkiran, E; Liberti, L, Reduced RLT representations for nonconvex polynomial programs, J. Global Optim., 52, 447-469, (2012) · Zbl 1244.90185
[24] Sherali, HD; Fraticelli, BMP, Enhancing RLT relaxations via a new class of semidefinite cuts, J. Global Optim., 22, 233-261, (2002) · Zbl 1045.90044
[25] Sherali, HD; Tuncbilek, CH, A global optimization algorithm for polynomial programming problems using a reformulation-linearization technique, J. Global Optim., 2, 101-112, (1992) · Zbl 0787.90088
[26] Sherali, HD; Tuncbilek, CH, New reformulation linearization/convexification relaxations for univariate and multivariate polynomial programming problems, Operations Res. Lett., 21, 1-9, (1997) · Zbl 0885.90105
[27] Sherali, HD; Wang, H, Global optimization of nonconvex factorable programming problems, Math. Program., 89, 459-478, (2001) · Zbl 0985.90073
[28] Sturm, JF, Using sedumi 1.02, a Matlab toolbox for optimization over symmetric cones, Optimiz. Methods Softw., 11, 625-653, (1999) · Zbl 0973.90526
[29] Tawarmalani, M; Sahinidis, NV, A polyhedral branch-and-cut approach to global optimization, Math. Program., 103, 225-249, (2005) · Zbl 1099.90047
[30] Waki, H; Kim, S; Kojima, M; Muramatsu, M, Sums of squares and semidefinite program relaxations for polynomial optimization problems with structured sparsity, SIAM J. Optim., 17, 218-242, (2006) · Zbl 1109.65058
[31] Waki, H; Kim, S; Kojima, M; Muramatsu, M; Sugimoto, H, Sparsepop—a sparse semidefinite programming relaxation of polynomial optimization problems, ACM Trans. Math. Softw., 35, 15:1-15:13, (2008)
[32] Zorn, K; Sahinidis, NV, Global optimization of general nonconvex problems with intermediate polynomial structures, J. Global Optim., 59, 673-693, (2014) · Zbl 1301.90066
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.