×

Linearization-based algorithms for mixed-integer nonlinear programs with convex continuous relaxation. (English) Zbl 1298.90059

Summary: We present two linearization-based algorithms for mixed-integer nonlinear programs (MINLPs) having a convex continuous relaxation. The key feature of these algorithms is that, in contrast to most existing linearization-based algorithms for convex MINLPs, they do not require the continuous relaxation to be defined by convex nonlinear functions. For example, these algorithms can solve to global optimality MINLPs with constraints defined by quasiconvex functions. The first algorithm is a slightly modified version of the LP/NLP-based branch-and-bouund LP/NLP-BB algorithm of Quesada and Grossmann, and is closely related to an algorithm recently proposed by P. Bonami et al. [Math. Program. 119, No. 2 (A), 331–352 (2009; Zbl 1163.90013)]. The second algorithm is a hybrid between this algorithm and nonlinear programming based branch-and-bound. Computational experiments indicate that the modified LP/NLP-BB method has comparable performance to LP/NLP-BB on instances defined by convex functions. Thus, this algorithm has the potential to solve a wider class of MINLP instances without sacrificing performance.

MSC:

90C11 Mixed integer programming
90C26 Nonconvex programming, global optimization

Citations:

Zbl 1163.90013
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Abhishek, K., Leyffer, S., Linderoth, J.: FilMINT: an outer-approximation-based solver for convex mixed-integer nonlinear programs. INFORMS J. Comput. 22(4), 555-567 (2010) · Zbl 1243.90142
[2] Androulakis, I.P., Maranas, C.D., Floudas, C.A.: \[ \alpha\] αBB: a global optimization method for general constrained nonconvex problems. J. Glob. Optim. 7, 337-363 (1995) · Zbl 0846.90087
[3] Bazaraa, M., Sherali, H., Shetty, C.: Nonlinear Programming: Theory and Algorithms. Wiley, New York (2006) · Zbl 1140.90040
[4] Bertsekas, D., Gallager, R.: Data Networks. Prentice-Hall, Endlewood Cliffs, NJ (1987) · Zbl 0734.68006
[5] Bertsekas, D., Nedić, A., Ozdaglar, A.: Convex Analysis and Optimization. Athena Scientific, Belmont (2003)
[6] Bonami, P., Biegler, L.T., Conn, A.R., Cornuéjols, G., Grossmann, I.E., Laird, C.D., Lee, J., Lodi, A., Margot, F., Sawaya, N., Wächter, A.: An algorithmic framework for convex mixed integer nonlinear programs. Discret. Optim. 5, 186-204 (2008) · Zbl 1151.90028
[7] Bonami, P., Cornuéjols, G., Lodi, A., Margot, F.: A feasibility pump for mixed integer nonlinear programs. Math. Program. 119, 331-352 (2009) · Zbl 1163.90013
[8] Bonami, P.; Kilinç, M.; Linderoth, J.; Lee, J. (ed.); Leyffer, S. (ed.), Algorithms and software for convex mixed integer nonlinear programs, No. 154, 1-40 (2012), Berlin · Zbl 1242.90121
[9] Boorstyn, R., Frank, H.: Large-scale network topological optimization. IEEE Trans. Commun. 25, 29-47 (1977) · Zbl 0361.94044
[10] Borchers, B., Mitchell, J.E.: An improved branch and bound algorithm for mixed integer nonlinear programs. Comput. Oper. Res. 21, 359-368 (1994) · Zbl 0797.90069
[11] Burer, S., Letchford, A.N.: Non-convex mixed-integer nonlinear programming: a survey. Sur. Oper. Res. Manag. Sci. 17, 97-106 (2012)
[12] Bussieck, M.R., Drud, A.: SBB: a new solver for mixed integer nonlinear programming. In: OR 2001, Section: Continuous, Optimization (2001)
[13] Bussieck, M.R., Drud, A.S., A.Meeraus: MINLPLib—a collection of test models for mixed-integer nonlinear programming. INFORMS J. Comput. 15(1), 114-119 (2003) · Zbl 1238.90104
[14] Castillo, I., Westerlund, J., Emet, S., Westerlund, T.: Optimization of block layout design problems with unequal areas: a comparison of milp and minlp optimization methods. Comput. Chem. Eng. 30, 54-69 (2005)
[15] CMU/IBM MINLP Project. http://egon.cheme.cmu.edu/ibm/page.htm
[16] CPLEX Optimization Inc, Incline Village, NV: Using the CPLEX Callable Library, Version 9 (2005)
[17] Dakin, R.J.: A tree search algorithm for mixed integer programming problems. Comput. J. 8, 250-255 (1965) · Zbl 0154.42004
[18] Dolan, E., Moré, J.: Benchmarking optimization software with performance profiles. Math. Program. 91, 201-212 (2002) · Zbl 1049.90004
[19] Duran, M.A., Grossman, I.E.: An outer-approximation algorithm for a class of mixed-integer nonlinear programs. Math. Program. 36, 307-339 (1986) · Zbl 0619.90052
[20] Elhedhli, S.: Service system design with Immobile servers, stochastic demand, and congestion. Manuf. Serv. Oper. Manag. 8(1), 92-97 (2006)
[21] Fletcher, R., Leyffer, S.: Solving mixed integer nonlinear programs by outer approximation. Math. Program. 66, 327-349 (1994) · Zbl 0833.90088
[22] Fletcher, R., Leyffer, S.: User Manual for FilterSQP (1998). University of Dundee Numerical Analysis, Report NA-181
[23] Flores-Tlacuahuac, A., Biegler, L.T.: Simultaneous mixed-integer dynamic optimization for integrated design and control. Comput. Chem. Eng. 31, 588-600 (2007)
[24] Floudas, C.A.: Deterministic Global Optimization: Theory, Algorithms and Applications. Kluwer, Dordrecht (2000)
[25] Garey, M.R., Johnson, D.S. (eds.): Computers and Interactability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, New York (1979) · Zbl 0411.68039
[26] Geoffrion, A.: Generalized benders decomposition. J. Optim. Theory Appl. 10(4), 237-260 (1972) · Zbl 0229.90024
[27] Grossmann, I.E.: Review of nonlinear mixed-integer and disjunctive programming techniques. Optim. Eng. 3, 227-252 (2002) · Zbl 1035.90050
[28] Grossmann, I.E., Sargent, R.W.H.: Optimal design of multipurpose chemical plant. Ind. Eng. Chem. Process. Des. Dev. 18, 343-348 (1979)
[29] Grossmann, I.E., Viswanathan, J., Raman, A., Kalvelagen, E.: GAMS/DICOPT: a discrete continuous optimization package. Math. Models Methods Appl. Sci. 11, 649-664 (2001)
[30] Günlük, O., Lee, J., Weismantel, R.: MINLP Strengthening for Separable Convex Quadratic Transportation-Cost ufl. Tech. rep, IBM Research Division (2007) · Zbl 1163.90013
[31] Günlük, O., Linderoth, J.: Perspective relaxation of mixed integer nonlinear programs with indicator variables. Math. Program. Ser. B 104, 186-203 (2010) · Zbl 1229.90106
[32] Günlük, O.; Linderoth, J.; Lee, J. (ed.); Leyffer, S. (ed.), Perspective reformulation and applications, No. 154, 61-92 (2012), Berlin · Zbl 1242.90134
[33] Harjunkoski, I., Pörn, R., Westerlund, T.: MINLP: trim-loss problem. In: Floudas, C.A., Pardalos, P.M. (Eds.) Encyclopedia of Optimization, pp. 2190-2198. Springer, Berlin (2009)
[34] Jain, V., Grossmann, I.E.: Cyclic scheduling of continuous parallel-process units with decaying performance. AIChE 44, 1623-1636 (1998) · Zbl 0989.90045
[35] Laird, C.D., Biegler, L.T., van Bloemen Waanders, B.: A mixed integer approach for obtaining unique solutions in source inversion of drinking water networks. J. Water Resour. Plan. Manag. 132, 242-251 (2006). Sprecial Issue on Drinking Water Distribution Systems Security · Zbl 1035.90050
[36] Leyffer, S.: User Manual for MINLP-BB. University of Dundee (1998)
[37] Leyffer, S.: MacMINLP: Test Problems for Mixed Integer Nonlinear Programming (2003). http://www.mcs.anl.gov/ leyffer/macminlp · Zbl 0833.90088
[38] Mahajan, A., Leyffer, S., Kirches, C.: Solving Mixed-Integer Nonlinear Programs by QP-Diving. Tech. Rep. Preprint ANL/MCS-2004-0112, Argonne National Laboratory, Mathematics and Computer Science Division (March 2012) · Zbl 0797.90069
[39] Mahajan, A., Leyffer, S., Linderoth, J., Luedtke, J., Munson, T.: MINOTAUR: A Toolkit for Solving Mixed-Integer Nonlinear Optimization. wiki-page (2011). http://wiki.mcs.anl.gov/minotaur/index.php/Main_Page · Zbl 1476.65099
[40] Mangasarian, O.L.: Nonlinear Programming. In: Classics in Applied Mathematics, 10. Society for Industrial and Applied Mathematics (1994). Originally published 1969 by McGraw-Hill, New York · Zbl 0833.90108
[41] McCormick, G.P.: Computability of global solutions to factorable nonconvex programs: part I-convex underestimating problems. Math. Program. 10, 147-175 (1976) · Zbl 0349.90100
[42] Pörn, R., Westerlund, T.: A cutting plane method for minimizing pseudo-convex functions in the mixed integer case. Comput. Chem. Eng. 24, 2655-2665 (2000)
[43] Quesada, I., Grossmann, I.E.: An LP/NLP based branch and bound algorithm for convex MINLP optimization problems. Comput. Chem. Eng. 16, 937-947 (1992)
[44] Ravemark, D.E., Rippin, D.W.T.: Optimal design of a multi-product batch plant. Comput. Chem. Eng. 22(1-2), 177-183 (1998)
[45] Sawaya, N.: Reformulations, Relaxations and Cutting Planes for Generalized Disjunctive Programming. Ph.D. thesis, Chemical Engineering Department, Carnegie Mellon University (2006) · Zbl 0154.42004
[46] Still, C.; Westerlund, T.; Floudas, C. (ed.); Pardalos, P. (ed.), Extended cutting plane algorithm, 53-61 (2001), Dordrecht
[47] Tawarmalani, M., Sahinidis, N.V.: Convexification and Global Optimization in Continuous and Mixed-Integer Nonlinear Programming: Theory, Algorithms, Software, and Applications. Kluwer, Boston, MA (2002) · Zbl 1031.90022
[48] Tawarmalani, M., Sahinidis, N.V.: Global optimization of mixed integer nonlinear programs: a theoretical and computational study. Math. Program. 99, 563-591 (2004) · Zbl 1062.90041
[49] Türkay, M., Grossmann, I.E.: Logic-based MINLP algorithms for the optimal synthesis of process networks. Comput. Chem. Eng. 20(8), 959-978 (1996)
[50] Vecchietti, A., Grossmann, I.E.: LOGMIP: a disjunctive 0-1 non-linear optimizer for process system models. Comput. Chem. Eng. 23(4-5), 555-565 (1999)
[51] Wächter, A., Biegler, L.T.: On the implementation of a primal-dual interior point filter line search algorithm for large-scale nonlinear programming. Math. Program. 106, 25-27 (2006) · Zbl 1134.90542
[52] Westerlund, T., Pettersson, F.: An extended cutting plane method for solving convex minlp problems. Comp. Chem. Eng. 19, 131-136 (1995)
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.