×

A recipe for finding good solutions to MINLPs. (English) Zbl 1276.90041

Summary: Finding good (or even just feasible) solutions for Mixed-Integer Nonlinear Programming problems independently of the specific problem structure is a very hard but practically important task, especially when the objective and/or the constraints are nonconvex. With this goal in mind, we present a general-purpose heuristic based on Variable Neighborhood Search, Local Branching, a local Nonlinear Programming algorithm and Branch-and-Bound. We test the proposed approach on MINLPLib, comparing with several existing heuristic and exact methods. An implementation of the proposed heuristic is freely available and can employ all NLP/MINLP solvers with an AMPL interface as the main search tools.

MSC:

90C11 Mixed integer programming
90C26 Nonconvex programming, global optimization
90C59 Approximation methods and heuristics in mathematical programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Abhishek, K., Leyffer, S., Linderoth, J.: Filmint: An outer-approximation based solver for nonlinear mixed-integer programs. Technical report ANL/MCS-P1374-0906, Argonne National Laboratory (2007) · Zbl 1243.90142
[2] Adjiman C., Androulakis I., Floudas C.: Global optimization of MINLP problems in process synthesis and design. Comput. Chem. Eng. 21, S445–S450 (1997)
[3] Aouchiche M., Bonnefoy J., Fidahoussen A., Caporossi G., Hansen P., Hiesse L., Lacheré J., Monhait A.: VNS for extremal graphs 14: The AGX 2 system. In: Liberti, L., Maculan, N. (eds) Global Optimization: From Theory to Implementation, pp. 281–308. Springer, Berlin (2006) · Zbl 1100.90052
[4] Belotti, P.: Couenne: a user’s manual. Technical report, Lehigh University (2009). http://www.coin-or.org/Couenne
[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(4–5), 597–634 (2008) · Zbl 1179.90237 · doi:10.1080/10556780903087124
[6] Bonami, P., Biegler, L., Conn, A., Cornuéjols, G., Grossmann, I., Laird, C., Lee, J., Lodi, A., Margot, F., Sawaya, N., Wächter, A.: An algorithmic framework for convex Mixed Integer Nonlinear Programs. Technical report RC23771. IBM Corporation (2005) · Zbl 1151.90028
[7] Bonami P., Cornuéjols G., Lodi A., Margot F.: A feasibility pump for Mixed Integer Nonlinear Programs. Math. Program. 119(2), 331–352 (2009) · Zbl 1163.90013 · doi:10.1007/s10107-008-0212-2
[8] Bonami, P., Lee, J.: $${{\(\backslash\)tt BONMIN}}$$ user’s manual. Technical report. IBM Corporation (2007)
[9] Brimberg J., Hansen P., Mladenović N.: Attraction probabilities in variable neighborhood search. 4OR 8, 181–194 (2010) · Zbl 1193.90216 · doi:10.1007/s10288-009-0108-x
[10] Brimberg J., Mladenović N.: A variable neighbourhood algorithm for solving the continuous location-allocation problem. Stud. Location Anal. 10, 1–12 (1996) · Zbl 0885.90069
[11] Brook A., Kendrick D., Meeraus A.: Gams, a user’s guide. ACM SIGNUM Newslett. 23(3–4), 10–11 (1988) · doi:10.1145/58859.58863
[12] Bussieck, M.R., Drud, A.S., Meeraus, A.: MINLPLib–a collection of test models for Mixed-Integer Nonlinear Programming. INFORMS J. Comput. 15(1) (2003). http://www.gamsworld.org/minlp/minlplib.htm · Zbl 1238.90104
[13] Consulting, A., Development: SBB Release Notes (2002)
[14] D’Ambrosio, C.: Application oriented Mixed Integer Nonlinear Programming. Ph.D. thesis, DEIS, Università di Bologna (2009)
[15] D’Ambrosio, C., Frangioni, A., Liberti, L., Lodi, A.: Experiments with a Feasibility Pump approach for nonconvex MINLPs. In: Festa, P. (ed.) Proceedings of the 9th Symposium on Experimental Algorithms (SEA 2010). Lecture Notes in Computer Science, vol. 6049. Springer, Berlin (2010)
[16] D’Ambrosio, C., Frangioni, A., Liberti, L., Lodi, A.: A storm of Feasibility Pumps for nonconvex MINLP. Technical report OR-10-13, DEIS, Università di Bologna (2010) · Zbl 1257.90056
[17] Danna E., Rothberg E., Le Pape C.: Exploring relaxation induced neighborhoods to improve MIP solutions. Math. Program. A 102, 71–90 (2005) · Zbl 1131.90036 · doi:10.1007/s10107-004-0518-7
[18] Dražic M., Kovačević-Vujčić V., Čangalović M., Mladenović N.: Glob–a new VNS-based software for global optimization. In: Liberti, L., Maculan, N. (eds) Global Optimization: From Theory to Implementation, pp. 135–154. Springer, Berlin (2006)
[19] Drazić, M., Lavor, C., Maculan, N., Mladenović, N.: A continuous VNS heuristic for finding the tridimensional structure of a molecule (2004)
[20] Duran M., Grossmann I.: 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
[21] Fischetti M., Glover F., Lodi A.: The feasibility pump. Math. Program. A 104(1), 91–104 (2005) · Zbl 1077.90039 · doi:10.1007/s10107-004-0570-3
[22] Fischetti M., Lodi A.: Local branching. Math. Program. 98, 23–37 (2003) · Zbl 1060.90056 · doi:10.1007/s10107-003-0395-5
[23] 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
[24] Fletcher R., Leyffer S.: Numerical experience with lower bounds for MIQP branch-and-bound. SIAM J. Optim. 8(2), 604–616 (1998) · Zbl 0912.90225 · doi:10.1137/S1052623494268455
[25] Fletcher R., Leyffer S.: User manual for filter. Technical report, University of Dundee, UK (1999)
[26] Fletcher R., Leyffer S.: Nonlinear programming without a penalty function. Math. Program. 91, 239–269 (2002) · Zbl 1049.90088 · doi:10.1007/s101070100244
[27] Fourer R., Gay D.: The AMPL Book. Duxbury Press, Pacific Grove (2002)
[28] Hansen P., Mladenović N.: Variable neighbourhood search: principles and applications. Eur. J. Oper. Res. 130, 449–467 (2001) · Zbl 0981.90063 · doi:10.1016/S0377-2217(00)00100-4
[29] Hansen P., Mladenović N., Brimberg J., Moreno Pérez J.: Variable neighbourhood search. In: Gendreau, M., Potvin, J.Y. (eds) Handbook of Metaheuristics, 2nd edn., Kluwer, Dordrecht (2010)
[30] Hansen P., Mladenović N., Moreno Pérez J.: Variable neighbourhood search: methods and applications. 4OR 6, 319–360 (2008) · Zbl 1179.90332 · doi:10.1007/s10288-008-0089-1
[31] Hansen P., Mladenović N., Urošević D.: Variable neighbourhood search and local branching. Comput. Oper. Res. 33(10), 3034–3045 (2006) · Zbl 1086.90042 · doi:10.1016/j.cor.2005.02.033
[32] Karmarkar N.: A new polynomial time algorithm for linear programming. Combinatorica 4(4), 373–395 (1984) · Zbl 0557.90065 · doi:10.1007/BF02579150
[33] Lavor C., Liberti L., Maculan N.: Computational experience with the molecular distance geometry problem. In: Pintér, J. (ed) Global Optimization: Scientific and Engineering Case Studies, Springer, Berlin (2006) · Zbl 1129.90389
[34] Leyffer S.: User manual for MINLP_BB. Technical report, University of Dundee, UK (1999)
[35] Liberti L.: Writing global optimization software. In: Liberti, L., Maculan, N. (eds) Global Optimization: From Theory to Implementation, pp. 211–262. Springer, Berlin (2006) · Zbl 1100.90004
[36] Liberti L., Cafieri S., Savourey D.: Reformulation optimization software engine. In: Fukuda, K., Hoeven, J., Joswig, M., Takayama, N. (eds) Mathematical Software. LNCS, vol. 6327, pp. 303–314. Springer, New York (2010) · Zbl 1294.68160
[37] Liberti, L., Dražic, M.: Variable neighbourhood search for the global optimization of constrained NLPs. In: Proceedings of GO Workshop, Almeria, Spain (2005)
[38] Liberti, L., Lavor, C., Maculan, N.: Double VNS for the molecular distance geometry problem. In: Proceedings of Mini Euro Conference on Variable Neighbourhood Search, Tenerife, Spain (2005) · Zbl 1129.90389
[39] Liberti, L., Lavor, C., Maculan, N., Marinelli, F.: Double variable neighbourhood search with smoothing for the molecular distance geometry problem. J. Glob. Optim. (accepted) · Zbl 1169.90470
[40] Liberti, L., Maculan, N. (eds): Global Optimization: From Theory to Implementation. Springer, Berlin (2006) · Zbl 1087.90005
[41] Liberti L., Nannicini G., Mladenović N.: A good recipe for solving MINLPs. In: Maniezzo, V., Stützle, T., Voss, S. (eds) Matheuristics: Hybridizing Metaheuristics and Mathematical Programming. Annals of Information Systems, vol. 10, pp. 231–245. Springer, Berlin (2009)
[42] Mladenović N., Drazic M., Kovacevic-Vujcic V., Cangalovic M.: General variable neighborhood search for the continuous optimization. Eur. J. Oper. Res. 191(3), 753–770 (2008) · Zbl 1156.90005 · doi:10.1016/j.ejor.2006.12.064
[43] Mladenović N., Petrović J., Kovačević-Vujčić V., Čangalović M.: Solving a spread-spectrum radar polyphase code design problem by tabu search and variable neighbourhood search. Eur. J. Oper. Res. 151, 389–399 (2003) · Zbl 1053.90055 · doi:10.1016/S0377-2217(02)00833-0
[44] Nannicini, G.: Point-to-point shortest paths in dynamic time-dependent road networks. Ph.D. thesis, Ecole Polytechnique, Palaiseau, France (2009) · Zbl 1201.90033
[45] Nannicini, G., Belotti, P.: Rounding-based heuristics for nonconvex MINLPs. In: Bonami, P., Liberti, L., Miller, A., Sartenaer, A. (eds.) Proceedings of the European Workshop on MINLP. CIRM, Marseille (2010) · Zbl 1257.90059
[46] Puchinger, J., Raidl, G.: Relaxation guided variable neighbourhood search. In: Proceedings of Mini Euro Conference on Variable Neighbourhood Search, Tenerife, Spain (2005) · Zbl 1211.90315
[47] Sahinidis N.: BARON: a general purpose global optimization software package. J. Glob. Optim. 8(2), 201–205 (1996) · Zbl 0856.90104 · doi:10.1007/BF00138693
[48] Smith E., Pantelides C.: A symbolic reformulation/spatial branch-and-bound algorithm for the global optimisation of nonconvex MINLPs. Comput. Chem. Eng. 23, 457–478 (1999) · doi:10.1016/S0098-1354(98)00286-5
[49] Tawarmalani M., Sahinidis N.: Global optimization of mixed integer nonlinear programs: a theoretical and computational study. Math. Program. 99, 563–591 (2004) · Zbl 1062.90041 · doi:10.1007/s10107-003-0467-6
[50] 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(1), 25–57 (2006) · Zbl 1134.90542 · doi:10.1007/s10107-004-0559-y
[51] Westerlund T., Skrifvars H., Harjunkoski I., Pörn R.: An extended cutting plane method for a class of non-convex MINLP problems. Comput. Chem. Eng. 22(3), 357–365 (1998) · Zbl 0955.90095 · doi:10.1016/S0098-1354(97)00000-8
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.