×

A comparative study of SQP-type algorithms for nonlinear and nonconvex mixed-integer optimization. (English) Zbl 1263.90003

Summary: We present numerical results of a comparative study of codes for nonlinear and nonconvex mixed-integer optimization. The underlying algorithms are based on sequential quadratic programming (SQP) with stabilization by trust-regions, linear outer approximations, and branch-and-bound techniques. The mixed-integer quadratic programming subproblems are solved by a branch-and-cut algorithm. Second order information is updated by a quasi-Newton update formula (BFGS) applied to the Lagrange function for continuous, but also for integer variables. We do not require that the model functions can be evaluated at fractional values of the integer variables. Thus, partial derivatives with respect to integer variables are replaced by descent directions obtained from function values at neighboring grid points, and the number of simulations or function evaluations, respectively, is our main performance criterion to measure the efficiency of a code. Numerical results are presented for a set of 100 academic mixed-integer test problems. Since not all of our test examples are convex, we reach the best-known solutions in about 90% of the test runs, but at least feasible solutions in the other cases. The average number of function evaluations of the new mixed-integer SQP code is between 240 and 500 including those needed for one- or two-sided approximations of partial derivatives or descent directions, respectively. In addition, we present numerical results for a set of 55 test problems with some practical background in petroleum engineering.

MSC:

90-08 Computational methods for problems pertaining to operations research and mathematical programming
90C10 Integer programming
90C30 Nonlinear programming
90C55 Methods of successive quadratic programming type
65K05 Numerical mathematical programming methods
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Asaadi J.: A computational comparison of some non-linear programs. Math. Program. 4, 144–154 (1973) · Zbl 0259.90044 · doi:10.1007/BF01584657
[2] Audet C., Dennis J.E.: Pattern search algorithm for mixed variable programming. SIAM J. Optim. 11, 573–594 (2001) · Zbl 1035.90048 · doi:10.1137/S1052623499352024
[3] Ayatollahi S., Narimani M., Moshfeghiam M.: Intermittent gas lift in Aghjari Oil 488 Field, a mathematical study. J. Petroleum Sci. Eng. 42, 245–255 (2004) · doi:10.1016/j.petrol.2003.12.015
[4] Bellman R.: Introduction to Matrix Analysis. McGraw-Hill, India (1960) · Zbl 0124.01001
[5] 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 · doi:10.1080/10556780903087124
[6] Belotti, P.: Couenne: a user’s manual, Technical Report, Department of Mathematical Sciences, Clemson University, Clemson SC 29643, USA (2009)
[7] Bonami, P., Biegler, L.T., Conn, A.R., Cornuejols, G., Grossmann, I.E., Laird, C.D., Lee, J., Lodi, A., Margot, F., Sawaya, N., Waechter, A.: An algorithmic framework for convex mixed integer nonlinear programs. IBM Research Report RC23771 (2005)
[8] Bonami, P., Kilinç, M., Linderoth, J.: Algorithms and software for convex mixed-integer nonlinear programs, Technical Report No. 1664, Computer Science Department, University of Wisconsin, Madison (2009) · Zbl 1242.90121
[9] Borchers B., Mitchell J.E.: An improved branch-and-bound algorithm for mixed integer nonlinear programming. Comput. Oper. Res. 21(4), 359–367 (1994) · Zbl 0797.90069 · doi:10.1016/0305-0548(94)90024-8
[10] Bünner M.J., Schittkowski K., van de Braak G.: Optimal design of electronic components by mixed-integer nonlinear programming. Optim. Eng. 5, 271–294 (2004) · Zbl 1151.90503 · doi:10.1023/B:OPTE.0000038887.72677.3e
[11] Bussieck, M.R., Vigerske, S. : MINLP Solver Software, submitted for publication (2010)
[12] Bussieck, M.R., Drud, A.S., Meeraus, A.: MINLPLib–a collection of test models for mixed integer nonlinear programming. GAMS Development Corp, Washington D.C., USA (2007) · Zbl 1238.90104
[13] Chen Z., Zhang X.: A nonmonotone trust-region algorithm with nonmonotone penalty parameters for constrained optimization. J. Comput. Appl. Math. 172, 7–39 (2004) · Zbl 1059.65053 · doi:10.1016/j.cam.2003.12.048
[14] Conn, A.R., Gould, N.M., Toint, P.L.: Trust-region methods. MPS-SIAM Series on Optimization, Philadelphia (2000) · Zbl 0958.65071
[15] Deng N.Y., Xiao Y., Zhou F.J.: Nonmonotonic trust-region algorithm. J. Optim. Theory Appl. 26, 259–285 (1993) · Zbl 0797.90088 · doi:10.1007/BF00939608
[16] Dolan E.D., Moré J.J.: Benchmarking optimization software with performance profiles. Math. Program. 91, 201–213 (2002) · Zbl 1049.90004 · doi:10.1007/s101070100263
[17] Duran M., Grossmann I.E.: An outer-approximation algorithm for a class of Mixed Integer Nonlinear Programs. Math. Program. 36, 307–339 (1986) · Zbl 0619.90052 · doi:10.1007/BF02592064
[18] Exler O., Antelo L.T., Egea J.A., Alonso A.A., Banga J.R.: Tabu search-based algorithm for mixed-integer nonlinear problems and its application to integrated process and control system design. Comput. Chem. Eng. 32(8), 1877–1891 (2008) · doi:10.1016/j.compchemeng.2007.10.008
[19] Exler, O., Lehmann, T., Schittkowski, K.: MISQPN : a Fortran subroutine for mixed-integer nonlinear optimization by outer approximation supported by mixed-integer search steps - user’s guide, version 1.0, Report, Department of Computer Science, University of Bayreuth (2009)
[20] Exler, O., Lehmann, T., Schittkowski, K.: MISQP: A Fortran subroutine of a trust region SQP algorithm for mixed-integer nonlinear programming–user’s guide, Report, Department of Computer Science, University of Bayreuth (2012) · Zbl 1263.90003
[21] Exler O., Schittkowski K.: A trust region SQP algorithm for mixed integer nonlinear programming. Optim. Lett. 1(3), 269–280 (2007) · Zbl 1152.90551 · doi:10.1007/s11590-006-0026-1
[22] Fletcher R.: A new approach to variable metric algorithms. Comput. J. 13, 317–322 (1970) · Zbl 0207.17402 · doi:10.1093/comjnl/13.3.317
[23] Fletcher, R.: Second order correction for nondifferentiable optimization. In: Watson, G.A. (ed.) Numerical analysis, pp. 85–114, Springer, Berlin (1982)
[24] Fletcher R., Leyffer S.: Solving mixed integer nonlinear programs by outer approximation. Math. Program. 66, 327–349 (1994) · Zbl 0833.90088 · doi:10.1007/BF01581153
[25] Floudas C.A.: Nonlinear and Mixed-Integer Optimization. Oxford University Press, New York (1995) · Zbl 0886.90106
[26] Fukushima M.: A successive quadratic programming algorithm with global and superlinear convergence properties. Math. Program. 35, 253–264 (1986) · Zbl 0597.90077 · doi:10.1007/BF01580879
[27] Goldfarb D., Idnani A.: A numerically stable method for solving strictly convex quadratic programs. Math. Program. 27, 1–33 (1983) · Zbl 0537.90081 · doi:10.1007/BF02591962
[28] Grossmann I.E.: Review of nonlinear mixed-integer and disjunctive programming techniques. Optim. Eng. 3, 227–252 (2002) · Zbl 1035.90050 · doi:10.1023/A:1021039126272
[29] Grossmann, I.E., Kravanja, Z.: Mixed-integer nonlinear programming: a survey of algorithms and applications. In: Conn, A.R., Biegler, L.T., Coleman, T.F., Santosa, F.N. (eds.) Large-Scale Optimization with Applications, Part II: Optimal Design and Control. Springer, New York (1997) · Zbl 0884.65058
[30] Gupta O.K., Ravindran V.: Branch-and-bound experiments in convex nonlinear integer programming. Manag. Sci. 31, 1533–1546 (1985) · Zbl 0591.90065 · doi:10.1287/mnsc.31.12.1533
[31] Günlük O., Linderoth J.: Perspective relaxation of mixed integer nonlinear programs with indicator variables. Math. Program. Series B 104, 186–203 (2010)
[32] Hartwanger C., Schittkowski K., Wolf H.: Computer aided optimal design of horn radiators for satellite communication. Eng. Optim. 33, 221–244 (2000) · doi:10.1080/03052150008940918
[33] Hock W., Schittkowski K.: A comparative performance evaluation of 27 nonlinear programming codes. Computing 30, 335–358 (1983) · Zbl 0508.90074 · doi:10.1007/BF02242139
[34] Lehmann, T., Schittkowski, K.: MIQL: A Fortran subroutine for convex mixed-integer quadratic programming–user’s guide, version 1.0, Report, Department of Computer Science, University of Bayreuth (2009)
[35] Lehmann, T., Schittkowski, K.: MINLPB4: A Fortran code for nonlinear mixed-integer quadratic programming by branch-and-bound - user’s guide, version 1.0, Report, Department of Computer Science, University of Bayreuth (2009)
[36] Lehmann, T., Schittkowski, K.: MISQPOA: a Fortran subroutine for mixed-integer nonlinear optimization by outer approximation–user’s guide, version 1.0, Report, Department of Computer Science, University of Bayreuth (2009)
[37] Lehmann, T., Schittkowski, K., Spickenreuther, T.: BFOUR: a Fortran subroutine for integer optimization by branch-and-bound–user’s guide, Report, Department of Computer Science, University of Bayreuth, Germany (2009)
[38] Leyffer S.: Integrating SQP and branch-and-bound for mixed integer nonlinear programming. Comput. Optim. Appl. 18, 295–309 (2001) · Zbl 1009.90074 · doi:10.1023/A:1011241421041
[39] Li H.L., Chou C.T.: A global approach for nonlinear mixed discrete programming in design optimization. Eng. Optim. 22, 109–122 (1994) · doi:10.1080/03052159308941328
[40] Lootsma, F.A.: Performance evaluation of nonlinear optimization methods via multi-criteria analysis and via linear model analysis. In: Powell, M.J.D. (ed.) Nonlinear Optimization, vol. 82. Academic Press, San Diego (1982) · Zbl 0547.90084
[41] Maratos, N.: Exact penalty function algorithms for finite-dimensional and control optimization problems, Ph.D. thesis, University of London, England (1978)
[42] Nowak, I., Alperin, H., Vigerske, S.: LaGO–an object oriented library for solving MINLPs. In: Bliek, C., Jermann, C., Neumaier, A. (eds.) Global Optimization and Constraint Satisfaction. Lecture Notes in Computer Science, vol. 2861, pp. 32–42. Springer, Berlin (2003) · Zbl 1255.90100
[43] Powell, M.J.D.: ZQPCVX, A FORTRAN subroutine for convex quadratic programming, Report DAMTP/1983/NA17, University of Cambridge, England (1983)
[44] 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) · doi:10.1016/0098-1354(92)80028-8
[45] Ray T., Sarker R.: Genetic algorithm for solving a gas lift optimization problem. J. Petroleum Sci. Eng. 59, 84–96 (2007) · doi:10.1016/j.petrol.2007.03.004
[46] Saaty T.L.: A scaling method for priorities in hierarchical structures. J. Math. Psychol. 15, 234–281 (1977) · Zbl 0372.62084 · doi:10.1016/0022-2496(77)90033-5
[47] Sahinidis, N.V., Tawarmalani, M.: BARON 9.0.4: Global Optimization of Mixed-Integer Nonlinear Programs, User’s Manual (2010). http://www.gams.com/dd/docs/solvers/baron.pdf
[48] Schittkowski, K.: Nonlinear Programming Codes - Information, Tests, Performance. Lecture Notes in Economics and Mathematical Systems, vol. 183. Springer, Berlin (1980) · Zbl 0435.90063
[49] Schittkowski, K.: QL: A Fortran code for convex quadratic programming–User’s guide, Report, Department of Mathematics, University of Bayreuth, Germany (2003)
[50] Schittkowski, K.: A collection of 100 test problems for nonlinear mixed-integer programming in Fortran–user’s guide, Report, Department of Computer Science, University of Bayreuth (2010)
[51] Schittkowski, K., Yuan, Y.-X.: Sequential quadratic programming methods to appear: Wiley Encyclopedia of Operations Research and Management Science (2010)
[52] Schlueter, M.: Nonlinear Mixed Integer Based Optimization Techniques for Space Applications. Dissertation, School of Mathematics, University of Birmingham (2012)
[53] Tawarmalani M., Sahinidis N.V.: A polyhedral branch-and-cut approach to global optimization. Math. Program. 103, 225–249 (2005) · Zbl 1099.90047 · doi:10.1007/s10107-005-0581-8
[54] Thomas I., Kröner, A.: Mixed-integer optimization of distillation column tray position in industrial practice. In: Marquardt, W., Pantelides, C. (eds.) 16th European Symposium on Computer Aided Engineering ans 9th International Symposium on Porcess Systems Engineering. Elsevier, Amsterdam, pp. 1015–1020 (2006)
[55] Toint P.L.: A non-monotone trust region algorithm for nonlinear optimization subject to convex constraints. Math. Program. 77(1), 69–94 (1997) · Zbl 0891.90153
[56] Viswanathan J., Grossmann I.E.: A combined penalty function and outer approximation method for MINLP optimization. Comput. Chem. Eng. 14, 769–782 (1990) · doi:10.1016/0098-1354(90)87085-4
[57] 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 · doi:10.1023/A:1021091110342
[58] Yuan Y.X.: On the convergence of a new trust region algorithm. Numerische Mathematik 70, 515–539 (1995) · Zbl 0828.65062 · doi:10.1007/s002110050133
[59] Yuan Y.X., Sun W.: Optimization Theory and Methods. Springer, Berlin (2006)
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.