×

A dynamic convexized method for nonconvex mixed integer nonlinear programming. (English) Zbl 1215.90047

Summary: We consider in this paper the nonconvex mixed-integer nonlinear programming problem. We present a mixed local search method to find a local minimizer of an unconstrained nonconvex mixed-integer nonlinear programming problem. Then an auxiliary function which has the same global minimizers and the same global minimal value as the original problem is constructed. Minimization of the auxiliary function using our local search method can escape successfully from previously converged local minimizers by taking increasing values of parameters. For the constrained nonconvex mixed-integer nonlinear programming problem, we develop a penalty based method to convert the problem into an unconstrained one, and then use the above method to solve the later problem. Numerical experiments and comparisons on a set of MINLP benchmark problems show the effectiveness of the proposed algorithm.

MSC:

90C30 Nonlinear programming
90C11 Mixed integer programming
90C26 Nonconvex programming, global optimization
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Asaadi, J., A computational comparison of some non-linear programs, Mathematical Programming, 4, 144-154 (1973) · Zbl 0259.90044
[2] Belotti P, Lee J, Liberti L, Margot F, Wächter A. Branching and bounds tightening techniques for non-convex MINLP. Technical Report, IBM Research Report RC24620; 2008.; Belotti P, Lee J, Liberti L, Margot F, Wächter A. Branching and bounds tightening techniques for non-convex MINLP. Technical Report, IBM Research Report RC24620; 2008. · Zbl 1179.90237
[3] Borchers, B.; Mitchell, J. E., An improved branch and bound algorithm for mixed integer nonlinear programming, Computers and Operations Research, 21, 359-367 (1994) · Zbl 0797.90069
[4] Bussieck, M. R.; Drud, A. S.; Meeraus, A., MINLPLib—a collection of test models for mixed-integer nonlinear programming, INFORMS Journal on Computing, 15, 114-119 (2003) · Zbl 1238.90104
[5] Bussieck MR, Pruessner A. Mixed-integer nonlinear programming. SIAG/OPT Newsletter: View and News; 2003.; Bussieck MR, Pruessner A. Mixed-integer nonlinear programming. SIAG/OPT Newsletter: View and News; 2003.
[6] Cardoso, M. F.; Salcedo, R. L.; Azevedo, S. F.; Barbosa, D., A simulated annealing approach to the solution of MINLP problems, Computers and Chemical Engineering, 21, 1349-1364 (1997)
[7] 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, Computers and Chemical Engineering, 30, 54-69 (2005)
[8] Cheung, B. K.S.; Langevin, A.; Delmaire, H., Coupling genetic algorithm with a grid search method to solve mixed integer nonlinear programming problems, Computers and Mathematics with Applications, 32, 13-23 (1997) · Zbl 0905.90126
[9] Costa, L.; Oliveria, P., Evolutionary algorithms approach to the solution of mixed integer nonlinear programming problems, Computers and Chemical Engineering, 21, 257-266 (2001)
[10] Deep, K.; Singh, K. P.; Kansal, M. L.; Mohan, C., A real coded genetic algorithm for solving integer and mixed integer optimization problems, Applied Mathematics and Computation, 212, 505-518 (2009) · Zbl 1168.65353
[11] Duran, M. A.; Grossmann, I. E., An outer-approximation algorithm for a class of mixed-integer nonlinear programs, Mathematical Programming, 36, 307-339 (1986) · Zbl 0619.90052
[12] Exler, O.; Antelo, L. T.; Egea, J. A.; Alonso, A. A.; Banga, J. R., A tabu search-based algorithm for mixed-integer nonlinear problems and its application to integrated process and control system design, Computers and Chemical Engineering, 32, 8, 1877-1891 (2008)
[13] Exler, O.; Schittkowksi, K., A trust region SQP algorithm for mixed-integer nonlinear programming, Optimization Letters, 1, 269-280 (2007) · Zbl 1152.90551
[14] Fletcher, R.; Leyffer, S., Solving mixed integer programs by outer approximation, Mathematical Programming, 66, 327-349 (1994) · Zbl 0833.90088
[15] Floudas, C. A.; Pardalos, P. M.; Adjiman, C.; Esposito, W. R.; Gümüs, Z. H.; Harding, S. T.; Klepeis, J. L.; Meyer, C. A.; Schweiger, C. A., Handbook of test problems in local and global optimization (1999), Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht · Zbl 0943.90001
[16] Geoffrion, A. M., A generalized Benders decomposition, Journal of Optimization Theory and Applications, 10, 4, 237-260 (1972) · Zbl 0229.90024
[17] Grossmann, I. E., Review of nonlinear mixed-integer and disjunctive programming techniques, Optimization and Engineering, 3, 227-252 (2002) · Zbl 1035.90050
[18] Grossmann IE, Sahinidis NV, editors. Special issue on mixed integer programming and it’s application to engineering, part I. Optimization and Engineering 2002;3(4).; Grossmann IE, Sahinidis NV, editors. Special issue on mixed integer programming and it’s application to engineering, part I. Optimization and Engineering 2002;3(4).
[19] Grossmann IE, Sahinidis NV, editors. Special issue on mixed integer programming and it’s application to engineering, part II. Optimization and Engineering 2002;4(1).; Grossmann IE, Sahinidis NV, editors. Special issue on mixed integer programming and it’s application to engineering, part II. Optimization and Engineering 2002;4(1).
[20] Hansen, E. R.; Walster, G. W., Global optimization using interval analysis (2004), MIT Press: MIT Press Cambridge, MA · Zbl 0770.65037
[21] Hock, W.; Schittkowski, K., Test examples for nonlinear programming codes, Journal of Optimization Theory and Applications, 30, 127-129 (1980) · Zbl 0393.90072
[22] Hua, Z.; Huang, F., An efficient genetic algorithm approach to large scale mixed integer programming problems, Applied Mathematics and Computation, 174, 897-907 (2006)
[23] Jain, V.; Grossmann, I. E., Cyclic scheduling of continuous parallel-process units with decaying performance, AIChE Journal, 44, 7, 1623-1636 (1998)
[24] Karuppiah, R.; Grossmann, I. E., A Lagrangean based branch-and-cut algorithm for global optimization of nonconvex mixed-integer nonlinear programs with decomposable structures, Journal of Global Optimization, 41, 163-186 (2008) · Zbl 1145.90055
[25] Kesavan, P.; Allgor, R. J.; Gatzke, E. P.; Barton, P. I., Outer approximation algorithm for separable nonconvex mixed-integer nonlinear programs, Mathematical Programming, 100, 517-535 (2004) · Zbl 1136.90024
[26] Leyffer, S., Integrating SQP and branch-and-bound for mixed integer nonlinear programming, Computational Optimization and Applications, 18, 295-309 (2001) · Zbl 1009.90074
[27] Leyffer S. Macminlp, ampl collection of mixed integer nonlinear programs \(\langle\) http://wiki.mcs.anl.gov/leyffer/index.php/MacMINLP \(\rangle \); Leyffer S. Macminlp, ampl collection of mixed integer nonlinear programs \(\langle\) http://wiki.mcs.anl.gov/leyffer/index.php/MacMINLP \(\rangle \)
[28] Lucidi, S.; Piccialli, V.; Sciandrone, M., An algorithm model for mixed variable programming, SIAM Journal on Optimization, 15, 1057-1084 (2005) · Zbl 1077.65064
[29] Mas, R.; Pinto, J. M., A mixed-integer optimization strategy for oil supply in distribution complexes, Optimization and Engineering, 4, 23-64 (2003) · Zbl 1046.90051
[30] Pardalos, P. M.; Schnitger, G., Checking local optimality in constrained quadratic programming is NP-hard, Operations Research Letters, 7, 33-35 (1988) · Zbl 0644.90067
[31] Ponsich, A.; Pantel, C. A.; Domenech, S.; Pibouleau, L., Mixed integer nonlinear programming optimization strategies for batch plant design problems, Industrial and Engineering Chemistry Research, 46, 854-863 (2007)
[32] Quesada, I.; Grossmann, I. E., An LP/NLP based branch and bound algorithm for convex MINLP optimization problems, Computers and Chemical Engineering, 16, 937-947 (1992)
[33] Sahinidis, N. V., Baron: a general purpose global optimization software package, Journal of Global Optimization, 8, 201-205 (1996) · Zbl 0856.90104
[34] Schlüter, M.; Egea, J. A.; Banga, J. R., Extended ant colony optimization for non-convex mixed integer nonlinear programming, Computers and Operations Research, 36, 2217-2229 (2009) · Zbl 1158.90391
[35] Tawarmalani, M.; Sahinidis, N. V., Global optimization of mixed-integer nonlinear program: a theoretical and computational study, Mathematical Programming, 99, 563-591 (2004) · Zbl 1062.90041
[36] Ugray Z, Lasdon L, Plummer J, Glover F, Kelly J, Marti R. A multistart scatter search heuristic for smooth NLP and MINLP problems \(\langle\) http://www.utexas.edu/courses/lasdon/papers.htm \(\rangle \); Ugray Z, Lasdon L, Plummer J, Glover F, Kelly J, Marti R. A multistart scatter search heuristic for smooth NLP and MINLP problems \(\langle\) http://www.utexas.edu/courses/lasdon/papers.htm \(\rangle \) · Zbl 1072.90572
[37] Wah, B. W.; Chen, Y. X.; Wang, T., Simulated annealing with asymptotic convergence for nonlinear constrained optimization, Journal of Global Optimization, 39, 1-37 (2007) · Zbl 1152.90010
[38] Westerlund, T.; Petersson, F., A cutting plane method for solving convex MINLP problems, Computers and Chemical Engineering, 19, 131-136 (1995)
[39] Westerlund, T.; Pörn, R., Solving pseudo-convex mixed integer optimization problems by cutting plane techniques, Optimization and Engineering, 3, 253-280 (2002) · Zbl 1035.90051
[40] Wolsey, L. A.; Nemhauser, G. L., Integer and combinatorial optimization (1998), Wiley: Wiley New York · Zbl 0469.90052
[41] Yan, L.; Shen, K.; Hu, S., Solving mixed integer nonlinear programming problems with line-up competition algorithm, Computers and Chemical Engineering, 28, 2647-2657 (2004)
[42] Yiqing, L.; Xigang, Y.; Yongjian, L., An improved PSO algorithm for solving non-convex NLP/MINLP problems with equality constraints, Computers and Chemical Engineering, 31, 153-162 (2007)
[43] Zhu, C.; Byrd, R. H.; Nocedal, J., L-BFGS-B: Algorithm 778: L-BFGS-B, FORTRAN routines for large scale bound constrained optimization, ACM Transactions on Mathematical Software, 23, 550-560 (1997) · Zbl 0912.65057
[44] Zhu WX. A dynamic convexized function with the same global minimizers for global optimization. In: Lecture notes in computer science, vol. 4221, 2006. p. 939-48.; Zhu WX. A dynamic convexized function with the same global minimizers for global optimization. In: Lecture notes in computer science, vol. 4221, 2006. p. 939-48.
[45] Zhu, W. X.; Ali, M. M., Discrete dynamic convexized method for nonlinearly constrained nonlinear integer programming, Computers and Operations Research, 36, 2723-2728 (2009) · Zbl 1160.90598
[46] Zhu, W. X.; Ali, M. M., Solving nonlinearly constrained global optimization problem via an auxiliary function method, Journal of Computational and Applied Mathematics, 230, 2, 491-503 (2009) · Zbl 1171.65052
[47] Zhu, W. X.; Fan, H., A discrete dynamic convexized method for nonlinear integer programming, Journal of Computational and Applied Mathematics, 223, 356-373 (2009) · Zbl 1156.65065
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.