×

zbMATH — the first resource for mathematics

Reformulations for utilizing separability when solving convex MINLP problems. (English) Zbl 1402.90098
Summary: Several deterministic methods for convex mixed integer nonlinear programming generate a polyhedral approximation of the feasible region, and utilize this approximation to obtain trial solutions. Such methods are, e.g., outer approximation, the extended cutting plane method and the extended supporting hyperplane method. In order to obtain the optimal solution and verify global optimality, these methods often require a quite accurate polyhedral approximation. In case the nonlinear functions are convex and separable to some extent, it is possible to obtain a tighter approximation by using a lifted polyhedral approximation, which can be achieved by reformulating the problem. We prove that under mild assumptions, it is possible to obtain tighter linear approximations for a type of functions referred to as almost additively separable. Here it is also shown that solvers, by a simple reformulation, can benefit from the tighter approximation, and a numerical comparison demonstrates the potential of the reformulation. The reformulation technique can also be combined with other known transformations to make it applicable to some nonseparable convex functions. By using a power transform and a logarithmic transform the reformulation technique can for example be applied to \(p\)-norms and some convex signomial functions, and the benefits of combining these transforms with the reformulation technique are illustrated with some numerical examples.

MSC:
90C11 Mixed integer programming
90C25 Convex programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Balas, E, Projection, lifting and extended formulation in integer and combinatorial optimization, Ann. Oper. Res., 140, 125-161, (2005) · Zbl 1091.90041
[2] Berenguel, JL; Casado, L; García, I; Hendrix, EM; Messine, F, On interval branch-and-bound for additively separable functions with common variables, J. Glob. Optim., 56, 1101-1121, (2013) · Zbl 1272.90056
[3] Bonami, P; Biegler, LT; Conn, AR; Cornuéjols, G; Grossmann, IE; Laird, CD; Lee, J; Lodi, A; Margot, F; Sawaya, N; etal., An algorithmic framework for convex mixed integer nonlinear programs, Discrete Optim., 5, 186-204, (2008) · Zbl 1151.90028
[4] Boyd, S; Kim, SJ; Vandenberghe, L; Hassibi, A, A tutorial on geometric programming, Optim. Eng., 8, 67, (2007) · Zbl 1178.90270
[5] Boyd, S., Vandenberghe, L.: Convex Optimization. Cambridge University Press, Cambridge (2004) · Zbl 1058.90049
[6] Bussieck, M.R., Vigerske, S.: MINLP solver software. Wiley Encyclopedia of Operations Research and Management Science (2010)
[7] Candes, E., Romberg, J.: l1-Magic: Recovery of Sparse Signals Via Convex Programming. www.acm.caltech.edu/l1magic/downloads/l1magic.pdf (2005). Accessed 1 Dec 2016 · Zbl 0856.90104
[8] Conforti, M; Cornuéjols, G; Zambelli, G, Extended formulations in combinatorial optimization, 4OR, 8, 1-48, (2010) · Zbl 1219.90193
[9] Dakin, RJ, A tree-search algorithm for mixed integer programming problems, Comput. J., 8, 250-255, (1965) · Zbl 0154.42004
[10] Duran, MA; Grossmann, IE, An outer-approximation algorithm for a class of mixed-integer nonlinear programs, Math. Program., 36, 307-339, (1986) · Zbl 0619.90052
[11] Fletcher, R; Leyffer, S, Solving mixed integer nonlinear programs by outer approximation, Math. Program., 66, 327-349, (1994) · Zbl 0833.90088
[12] Floudas, C.A.: Deterministic global optimization: theory, methods and applications, vol. 37. Springer Science & Business Media (2013). http://www.springer.com/la/book/9780792360148
[13] Floudas, CA; Gounaris, CE, A review of recent advances in global optimization, J. Glob. Optim., 45, 3-38, (2009) · Zbl 1180.90245
[14] GAMSWorld: Mixed-Integer Nonlinear Programming Library (2016). http://www.gamsworld.org/minlp/minlplib2/html/. Accessed 24 Nov 2016
[15] Geoffrion, AM, Generalized benders decomposition, J. Optim. Theory Appl., 10, 237-260, (1972) · Zbl 0229.90024
[16] Griewank, A; Toint, PL, On the unconstrained optimization of partially separable functions, Nonlinear Optim., 1982, 247-265, (1981) · Zbl 0563.90085
[17] Grossmann, I., Viswanathan, J., Vecchietti, A., Raman, R., Kalvelagen, E.: DICOPT. Engineering Research Design Center. GAMS Development Corporation, Pittsburgh (2009) · Zbl 1339.90247
[18] Grossmann, IE, Review of nonlinear mixed-integer and disjunctive programming techniques, Optim. Eng., 3, 227-252, (2002) · Zbl 1035.90050
[19] Grossmann, I.E., Kravanja, Z.: Mixed-integer nonlinear programming: a survey of algorithms and applications. In: Biegler, L.T., Coleman, T.F., Conn, A.R., Santosa, F.N. (eds.) Large-Scale Optimization with Applications, pp. 73-100. Springer (1997). https://link.springer.com/chapter/10.1007/978-1-4612-1960-6_5 · Zbl 0884.65058
[20] Gurobi: Gurobi 6.5 Performance Benchmarks (2015). http://www.gurobi.com/pdfs/benchmarks.pdf
[21] Hijazi, H., Bonami, P., Ouorou, A.: An outer-inner approximation for separable MINLPs. LIF, Faculté des Sciences de Luminy, Université de Marseille, Technical Report (2010) · Zbl 1356.90091
[22] Kronqvist, J; Lundell, A; Westerlund, T, The extended supporting hyperplane algorithm for convex mixed-integer nonlinear programming, J. Glob. Optim., 64, 249-272, (2016) · Zbl 1339.90247
[23] Kronqvist, J., Lundell, A., Westerlund, T.: Lifted polyhedral approximations in convex mixed integer nonlinear programming. In: XIII Global Optimization Workshop GOW16 4-8 Sept 2016, vol. 16, pp. 117-120 (2016) · Zbl 1339.90247
[24] Lastusilta, T; Bussieck, MR; Westerlund, T, An experimental study of the GAMS/alphaecp MINLP solver, Ind. Eng. Chem. Res., 48, 7337-7345, (2009)
[25] Lee, J., Leyffer, S. (eds.): Mixed Integer Nonlinear Programming, vol. 154. Springer, Berlin (2011)
[26] Li, HL; Tsai, JF; Floudas, CA, Convex underestimation for posynomial functions of positive variables, Optim. Lett., 2, 333-340, (2008) · Zbl 1152.90610
[27] Lubin, M., Yamangil, E., Bent, R., Vielma, J.P.: Extended formulations in mixed-integer convex programming. In: International Conference on Integer Programming and Combinatorial Optimization, pp. 102-113. Springer (2016) · Zbl 1419.90078
[28] Lundell, A.: Transformation Techniques for Signomial Functions in Global Optimization. Ph.D. thesis, Åbo Akademi University (2009) · Zbl 0833.90088
[29] Lundell, A; Skjäl, A; Westerlund, T, A reformulation framework for global optimization, J. Glob. Optim., 57, 115-141, (2013) · Zbl 1277.90102
[30] Nowak, I.: Relaxation and Decomposition Methods for Mixed Integer Nonlinear Programming, vol. 152. Springer, Berlin (2006)
[31] Rockafellar, R.T.: Convex Analysis. Princeton University Press, Princeton (1970) · Zbl 0193.18401
[32] Sahinidis, NV, BARON: a general purpose global optimization software package, J. Glob. Optim., 8, 201-205, (1996) · Zbl 0856.90104
[33] Tawarmalani, M., Sahinidis, N.V.: Convexification and Global Optimization in Continuous and Mixed-Integer Nonlinear Programming: Theory, Algorithms, Software, and Applications, vol. 65. Springer, Berlin (2002) · Zbl 1031.90022
[34] Tawarmalani, M; Sahinidis, NV, A polyhedral branch-and-cut approach to global optimization, Math. Program., 103, 225-249, (2005) · Zbl 1099.90047
[35] Vielma, J.P., Dunning, I., Huchette, J., Lubin, M.: Extended formulations in mixed integer conic quadratic programming. arXiv preprint arXiv:1505.07857 (2015) · Zbl 1387.90165
[36] Vinel, A; Krokhmal, PA, Polyhedral approximations in \(p\)-order cone programming, Optim. Methods Softw., 29, 1210-1237, (2014) · Zbl 1306.90155
[37] Westerlund, T; Petterson, F, An extended cutting plane method for solving convex MINLP problems, Comput. Chem. Eng., 19, s131-s136, (1995)
[38] Westerlund, T; Pörn, R, Solving pseudo-convex mixed integer optimization problems by cutting plane techniques, Optim. Eng., 3, 253-280, (2002) · Zbl 1035.90051
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.