×

zbMATH — the first resource for mathematics

Integrality gap minimization heuristics for binary mixed integer nonlinear programming. (English) Zbl 1402.90101
Summary: We present two feasibility heuristics for binary mixed integer nonlinear programming. Called integrality gap minimization algorithm (IGMA) – Versions 1 and 2, our heuristics are based on the solution of integrality gap minimization problems with a space partitioning scheme defined over the integer variables of the problem addressed. Computational results on a set of benchmark instances show that the proposed approaches present satisfactory results.

MSC:
90C11 Mixed integer programming
90C59 Approximation methods and heuristics in mathematical programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Belotti, P.: Design of telecommunication networks with shared protection. Available from CyberInfrastructure for MINLP at: www.minlp.org/library/problem/index.php?i=51 (2009). Accessed 14 Oct 2016
[2] Belotti, P; Berthold, T, Three ideas for a feasibility pump for nonconvex MINLP, Optim. Lett., 11, 3-15, (2017) · Zbl 1373.90080
[3] Bertacco, L; Fischetti, M; Lodi, A, A feasibility pump heuristic for general mixed-integer problems, Discrete Optim., 4, 63-76, (2007) · Zbl 1169.90415
[4] Berthold, T., Gleixner, A.M.: Undercover—a primal heuristic for minlp based on sub-mips generated by set covering. Technical Report ZIB-REPORT 09-04 (2009)
[5] Berthold, T.: Heuristic algorithms in global MINLP solvers. Ph.D. thesis, Technische Universität Berlin (2014)
[6] Berthold, T, Rens, Math. Program. Comput., 6, 33-54, (2014) · Zbl 1304.90147
[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; Gonçalves, J, Heuristics for convex mixed integer nonlinear programs, Comput. Optim. Appl., (2008) · Zbl 1241.90189
[9] Bonami, P., Kilinç, M., Linderoth, J.: Algorithms and software for convex mixed integer nonlinear programs. Technical Report 1664, Computer Sciences Department, University of Wisconsin-Madison (2009) · Zbl 1242.90121
[10] Bonami, P; Lee, J; Leyffer, S; Wächter, A, On branching rules for convex mixed-integer nonlinear optimization, J. Exp. Algorithmics, 18, 2.6:2.1-2.6:2.31, (2013) · Zbl 1322.90052
[11] Bragalli, C; D’Ambrosio, C; Lee, J; Lodi, A; Toth, P, On the optimal design of water distribution networks: a practical MINLP approach, Optim. Eng., 13, 219-246, (2012) · Zbl 1293.76045
[12] Christodoulou, M., Costoulakis, C.: Nonlinear mixed integer programming for aircraft collision avoidance in free flight. In: Proceedings of the 12th IEEE Mediterranean Electrotechnical Conference, 2004. MELECON 2004, vol. 1, pp. 327-330 (2004) · Zbl 1312.90046
[13] 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
[14] D’Ambrosio, C; Lodi, A, Mixed integer nonlinear programming tools: a practical overview, 4OR, 9, 329-349, (2011) · Zbl 1235.90101
[15] Danna, E; Rothberg, E; Pape, C, Exploring relaxation induced neighborhoods to improve mip solutions, Math. Program., 102, 71-90, (2005) · Zbl 1131.90036
[16] Dash Optimization. Getting Started with Xpress. http://www.fico.com/xpress. Accessed 14 Oct 2016
[17] 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
[18] Fampa, M; Lee, J; Melo, W, On global optimization with indefinite quadratics, EURO J. Comput. Optim., (2016) · Zbl 1384.90075
[19] Fischetti, M; Lodi, A, Local branching, Math. Program., 98, 23-47, (2003) · Zbl 1060.90056
[20] Fletcher, R; Leyffer, S, Solving mixed integer nonlinear programs by outer approximation, Math. Program., 66, 327-349, (1994) · Zbl 0833.90088
[21] Fourer, R., Gay, D.M., Kernighan, B.: AMPL: a mathematical programming language. In: Wallace, S.W. (ed.) Algorithms and Model Formulations in Mathematical Programming. Nato Asi Series F, Computer And Systems Sciences, Vol. 51. Springer, New York, NY, pp. 50-151 (1989). · Zbl 0229.90024
[22] GAMS World. Minlp library 2. https://www.gamsworld.org/minlp/minlplib2/html/ (2014). Accessed 14 Oct 2016
[23] Gentilini, I.: Minlp approach for the TSPN (traveling salesman problem with neighborhoods). Available from CyberInfrastructure for MINLP at: https://www.minlp.org/library/problem/index.php?i=124 (2011). Accessed 14 Oct 2016
[24] Geoffrion, AM, Generalized benders decomposition, J. Optim. Theory Appl., 10, 237-260, (1972) · Zbl 0229.90024
[25] Gopalakrishnan, A., Biegler, L.: Minlp and MPCC formulations for the cascading tanks problem. Available from CyberInfrastructure for MINLP at: https://www.minlp.org/library/problem/index.php?i=140(2011). Accessed 14 Oct 2016 · Zbl 0833.90088
[26] Guillen, G., Pozo, C.: Optimization of metabolic networks in biotechnology. Available from CyberInfrastructure for MINLP at: https://www.minlp.org/library/problem/index.php?i=81 (2010). Accessed 14 Oct 2016 · Zbl 1060.90056
[27] Hemmecke, R; Köppe, M; Lee, J; Weismantel, R; Jünger, M (ed.); Liebling, TM (ed.); Naddef, D (ed.); Nemhauser, GL (ed.); Pulleyblank, WR (ed.); Reinelt, G (ed.); Rinaldi, G (ed.); Wolsey, LA (ed.), Nonlinear integer programming, 561-618, (2010), Berlin · Zbl 1187.90270
[28] Intel Corporation: Intel C++ Compiler 16.0 User and Reference Guide. https://software.intel.com/en-us/intel-cplusplus-compiler-16.0-user-and-reference-guide. Accessed 14 Oct 2016 · Zbl 0619.90052
[29] Leyffer, S; Linderoth, J; Luedtke, J; Miller, A; Munson, T, Applications and algorithms for mixed integer nonlinear programming, J. Phys. Conf. Ser., 180, 012014, (2009)
[30] Liberti, L; Mladenović, N; Nannicini, G, A recipe for finding good solutions to minlps, Math. Program. Comput., 3, 349-390, (2011) · Zbl 1276.90041
[31] Liu, P., Pistikopoulos, E.N., Li, Z.: Global multi-objective optimization of a nonconvex minlp problem and its application on polygeneration energy systems design. Available from CyberInfrastructure for MINLP at: https://www.minlp.org/library/problem/index.php?i=42 (2009). Accessed 14 Oct 2016 · Zbl 1235.90101
[32] López, CO; Beasley, JE, A note on solving minlp’s using formulation space search, Optim. Lett., 8, 1167-1182, (2014) · Zbl 1292.90213
[33] Melo, W; Fampa, M; Raupp, F, Integrating nonlinear branch-and-bound and outer approximation for convex mixed integer nonlinear programming, J. Glob. Optim., 60, 373-389, (2014) · Zbl 1312.90046
[34] Mouret, S., Grossmann, I.: Crude-oil operations scheduling. Available from CyberInfrastructure for MINLP at: https://www.minlp.org/library/problem/index.php?i=117 (2010). Accessed 14 Oct 2016 · Zbl 1293.76045
[35] Murray, W; Ng, K-M, An algorithm for nonlinear optimization problems with binary variables, Comput. Optim. Appl., 47, 257-288, (2010) · Zbl 1200.90156
[36] Nannicini, G., Belotti, P., Liberti, L.: A local branching heuristic for MINLPs. ArXiv e-prints (2008) · Zbl 1241.90189
[37] Quesada, I; Grossmann, IE, An LP/NLP based branch and bound algorithm for convex MINLP optimization problems, Comput. Chem. Eng., 16, 937-947, (1992)
[38] Raghavachari, M, On connections between zero-one integer programming and concave programming under linear constraints, Oper. Res., 17, 680-684, (1969) · Zbl 0176.49805
[39] Savelsbergh, MWP, Preprocessing and probing techniques for mixed integer programming problems, ORSA J. Comput., 6, 445-454, (1994) · Zbl 0814.90093
[40] Science Technology Facilities Council: HSL: A collection of Fortran codes for large scale scientific computation. http://www.hsl.rl.ac.uk/. Accessed 14 Oct 2016
[41] Trespalacios, F; Grossmann, IE, Review of mixed-integer nonlinear and generalized disjunctive programming methods, Chem. Ing. Tech., 86, 991-1012, (2014)
[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] You, F; Grossmann, IE, Mixed-integer nonlinear programming models and algorithms for large-scale supply chain design with stochastic inventory management, Indus. Eng. Chem. Res., 47, 7802-7817, (2008)
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.