×

zbMATH — the first resource for mathematics

Computing feasible points for binary MINLPs with MPECs. (English) Zbl 1411.90008
Summary: Nonconvex mixed-binary nonlinear optimization problems frequently appear in practice and are typically extremely hard to solve. In this paper we discuss a class of primal heuristics that are based on a reformulation of the problem as a mathematical program with equilibrium constraints. We then use different regularization schemes for this class of problems and use an iterative solution procedure for solving series of regularized problems. In the case of success, these procedures result in a feasible solution of the original mixed-binary nonlinear problem. Since we rely on local nonlinear programming solvers the resulting method is fast and we further improve its reliability by additional algorithmic techniques. We show the strength of our method by an extensive computational study on 662 MINLPLib2 instances, where our methods are able to produce feasible solutions for \(60{\%}\) of all instances in at most 10 s.

MSC:
90-08 Computational methods for problems pertaining to operations research and mathematical programming
90C11 Mixed integer programming
90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)
90C59 Approximation methods and heuristics in mathematical programming
90C26 Nonconvex programming, global optimization
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Achterberg, T., SCIP: solving constraint integer programs, Math. Program. Comput., 1, 1-41, (2009) · Zbl 1171.90476
[2] Baumrucker, BT; Renfro, JG; Biegler, LT, MPEC problem formulations and solution strategies with chemical engineering applications, Comput. Chem. Eng., 32, 2903-2913, (2008)
[3] Benoist, T.; Estellon, B.; Gardi, F.; Megel, R.; Nouioua, K., Localsolver 1.x: a black-box local-search solver for 0-1 programming, 4OR, 9, 299, (2011) · Zbl 1231.90318
[4] Berthold, T.: Heuristic algorithms in global MINLP solvers. Ph.D. thesis, Technische Universität Berlin (2014)
[5] Berthold, T.; Gleixner, AM, Undercover: a primal MINLP heuristic exploring a largest sub-MIP, Math. Program., 144, 315-346, (2014) · Zbl 1291.90144
[6] Berthold, T., Heinz, S., Pfetsch, M.E., Vigerske, S.: Large neighborhood search beyond MIP. In: Proceedings of the 9th Metaheuristics International Conference (MIC 2011), pp. 51-60 (2011)
[7] Berthold, T.; Heinz, S.; Vigerske, S.; Lee, J. (ed.); Leyffer, S. (ed.), Extending a CIP framework to solve MIQCPs, 427-444, (2012), New York · Zbl 1242.90120
[8] 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
[9] Bonami, P.; Gonçalves, JPM, Heuristics for convex mixed integer nonlinear programs, Comput. Optim. Appl., 51, 729-747, (2012) · Zbl 1241.90189
[10] D’Ambrosio, C.; Frangioni, A.; Liberti, L.; Lodi, A.; Festa, P. (ed.), Experiments with a feasibility pump approach for nonconvex MINLPs, No. 6049, 350-360, (2010), Berlin
[11] D’Ambrosio, C.; Frangioni, A.; Liberti, L.; Lodi, A., A storm of feasibility pumps for nonconvex MINLP, Math. Program., 136, 375-402, (2012) · Zbl 1257.90056
[12] Dolan, ED; Moré, JJ, Benchmarking optimization software with performance profiles, Math. Program., 91, 201-213, (2002) · Zbl 1049.90004
[13] Drud, AS, CONOPT—a large-scale GRG code, INFORMS J. Comput., 6, 207-216, (1994) · Zbl 0806.90113
[14] Drud, A.S.: CONOPT: a system for large scale nonlinear optimization, tutorial for CONOPT subroutine library. Technical Report, ARKI Consulting and Development A/S, Bagsvaerd, Denmark (1995)
[15] Drud, A.S.: CONOPT: a system for large scale nonlinear optimization, reference manual for CONOPT subroutine library. Technical Report, ARKI Consulting and Development A/S, Bagsvaerd, Denmark (1996)
[16] Fischer, A., A special Newton-type optimization method, Optimization, 24, 269-284, (1992) · Zbl 0814.65063
[17] Fischetti, M.; Lodi, A., Local branching, Math. Program., 98, 23-47, (2003) · Zbl 1060.90056
[18] GAMS Development Corporation: General Algebraic Modeling System (GAMS) Release 24.5.4. Washington, DC, USA (2015). http://www.gams.com. Accessed 10 Aug 2018
[19] Gill, PE; Murray, W.; Saunders, MA, SNOPT: an SQP algorithm for large-scale constrained optimization, SIAM Rev., 47, 99-131, (2005) · Zbl 1210.90176
[20] Gleixner, A., Eifler, L., Gally, T., Gamrath, G., Gemander, P., Gottwald, R.L., Hendel, G., Hojny, C., Koch, T., Miltenberger, M., Müller, B., Pfetsch, M.E., Puchert, C., Rehfeldt, D., Schlösser, F., Serrano, F., Shinano, Y., Viernickel, J.M., Vigerske, S., Weninger, D., Witt, J.T., Witzig, J.: The SCIP Optimization Suite 5.0. Technical Report 17-61, ZIB, Takustr.7, 14195 Berlin (2017)
[21] Hoheisel, T.; Kanzow, C.; Schwartz, A., Theoretical and numerical comparison of relaxation methods for mathematical programs with complementarity constraints, Math. Program., 137, 257-288, (2013) · Zbl 1262.65065
[22] Hu, XM; Ralph, D., Convergence of a penalty method for mathematical programming with complementarity constraints, J. Optim. Theory Appl., 123, 365-390, (2004)
[23] Koch, T.; Achterberg, T.; Andersen, E.; Bastert, O.; Berthold, T.; Bixby, RE; Danna, E.; Gamrath, G.; Gleixner, AM; Heinz, S.; Lodi, A.; Mittelmann, H.; Ralphs, T.; Salvagnin, D.; Steffy, DE; Wolter, K., MIPLIB 2010, Math. Program. Comput., 3, 103-163, (2011)
[24] Kraemer, K.; Kossack, S.; Marquardt, W., An efficient solution method for the MINLP optimization of chemical processes, Comput. Aided Chem. Eng., 24, 105, (2007)
[25] Kraemer, K., Marquardt, W.: Continuous reformulation of MINLP problems. In: Diehl, M., Glineur, F., Jarlebring, E., Michiels, W. (eds.) Recent Advances in Optimization and Its Applications in Engineering: The 14th Belgian-French-German Conference on Optimization, pp. 83-92. Springer, Berlin (2010). https://doi.org/10.1007/978-3-642-12598-0_8
[26] Liberti, L.; Mladenović, N.; Nannicini, G., A recipe for finding good solutions to MINLPs, Math. Program. Comput., 3, 349-390, (2011) · Zbl 1276.90041
[27] Luo, Z.Q., Pang, J.S., Ralph, D.: Mathematical Programs with Equilibrium Constraints. Cambridge University Press, Cambridge (1996) · Zbl 1139.90003
[28] Maher, S.J., Fischer, T., Gally, T., Gamrath, G., Gleixner, A., Gottwald, R.L., Hendel, G., Koch, T., Lübbecke, M.E., Miltenberger, M., Müller, B., Pfetsch, M.E., Puchert, C., Rehfeldt, D., Schenker, S., Schwarz, R., Serrano, F., Shinano, Y., Weninger, D., Witt, J.T., Witzig, J.: The SCIP optimization suite 4.0. Technical Report 17-12, ZIB, Takustr.7, 14195 Berlin (2017)
[29] Nannicini, G.; Belotti, P., Rounding-based heuristics for nonconvex MINLPs, Math. Program. Comput., 4, 1-31, (2012) · Zbl 1257.90059
[30] Nannicini, G., Belotti, P., Liberti, L.: A local branching heuristic for MINLPs (2008). arXiv preprint arXiv:0812.2188
[31] Rose, D.; Schmidt, M.; Steinbach, MC; Willert, BM, Computational optimization of gas compressor stations: MINLP models versus continuous reformulations, Math. Methods Oper. Res., 83, 409-444, (2016) · Zbl 1354.90008
[32] Sahinidis, N.V.: BARON 14.3.1: Global Optimization of Mixed-Integer Nonlinear Programs, User’s Manual (2014)
[33] Schmidt, M.; Steinbach, MC; Willert, BM; Jünger, M. (ed.); Reinelt, G. (ed.), A primal heuristic for nonsmooth mixed integer nonlinear optimization, 295-320, (2013), Berlin · Zbl 1317.90212
[34] Schmidt, M., Steinbach, M.C., Willert, B.M.: An MPEC based heuristic. In: Koch, T., Hiller, B., Pfetsch, M.E., Schewe, L. (eds.) Evaluating Gas Network Capacities, SIAM-MOS series on Optimization, Chapter 9, pp. 163-180. SIAM (2015). https://doi.org/10.1137/1.9781611973693.ch9
[35] Scholtes, S., Convergence properties of a regularization scheme for mathematical programs with complementarity constraints, SIAM J. Optim., 11, 918-936, (2001) · Zbl 1010.90086
[36] Stein, O.; Oldenburg, J.; Marquardt, W., Continuous reformulations of discrete-continuous optimization problems, Comput. Chem. Eng., 28, 1951-1966, (2004)
[37] Sun, D.; Qi, L., On NCP-functions, Comput. Optim. Appl., 13, 201-220, (1999) · Zbl 1040.90544
[38] Tawarmalani, M., Sahinidis, N.V.: Convexification and Global Optimization in Continuous and Mixed-Integer Nonlinear Programming: Theory, Algorithms, Software, and Applications. Kluwer Academic Publishers, Dordrecht (2002) · Zbl 1031.90022
[39] Tawarmalani, M.; Sahinidis, NV, Global optimization of mixed-integer nonlinear programs: a theoretical and computational study, Math. Program., 99, 563-591, (2004) · Zbl 1062.90041
[40] Tawarmalani, M.; Sahinidis, NV, A polyhedral branch-and-cut approach to global optimization, Math. Program., 103, 225-249, (2005) · Zbl 1099.90047
[41] Ugray, Z.; Lasdon, L.; Plummer, J.; Glover, F.; Kelly, J.; Martí, R., Scatter search and local NLP solvers: a multistart framework for global optimization, INFORMS J. Comput., 19, 328-340, (2007) · Zbl 1241.90093
[42] Wächter, A.; Biegler, LT, On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming, Math. Program., 106, 25-57, (2006) · Zbl 1134.90542
[43] Wächter, A.; Biegler, LT, Line search filter methods for nonlinear programming: motivation and global convergence, SIAM J. Optim., 16, 1-31, (2005) · Zbl 1114.90128
[44] Wu, B., Ghanem, B.: \(l_p\)-box ADMM: a versatile framework for integer programming. Technical Report (2016). http://arxiv.org/abs/1604.07666. Accessed 10 Aug 2018
[45] Ye, JJ; Zhu, DL, Optimality conditions for bilevel programming problems, Optimization, 33, 9-27, (1995) · Zbl 0820.65032
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.