×

zbMATH — the first resource for mathematics

Rounding-based heuristics for nonconvex MINLPS. (English) Zbl 1257.90059
Summary: We propose two primal heuristics for nonconvex mixed-integer nonlinear programs. Both are based on the idea of rounding the solution of a continuous nonlinear program subject to linear constraints. Each rounding step is accomplished through the solution of a mixed-integer linear program. Our heuristics use the same algorithmic scheme, but they differ in the choice of the point to be rounded (which is feasible for nonlinear constraints but possibly fractional) and in the linear constraints. We propose a feasibility heuristic, that aims at finding an initial feasible solution, and an improvement heuristic, whose purpose is to search for an improved solution within the neighborhood of a given point. The neighborhood is defined through local branching cuts or box constraints. Computational results show the effectiveness in practice of these simple ideas, implemented within an open-source solver for nonconvex mixed-integer nonlinear programs.

MSC:
90C11 Mixed integer programming
90C59 Approximation methods and heuristics in mathematical programming
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Balas, E.; Jeroslow, R., Canonical cuts on the unit hypercube, SIAM J. Appl. Math., 23, 61-69, (1972) · Zbl 0237.52004
[2] Belotti, P.: Couenne: a user’s manual. Tech. Rep., Lehigh University (2009). http://www.coin-or.org/Couenne · Zbl 1062.90041
[3] 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, (2008) · Zbl 1179.90237
[4] Biegler L., Grossmann I., Westerberg A.: Systematic Methods of Chemical Process Design. Prentice Hall, Upper Saddle River (NJ) (1997)
[5] 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
[6] Bonami, P., Gonçalves, J.: Primal heuristics for mixed-integer nonlinear programs. Tech. Rep. RC24639, IBM (2008) · Zbl 1077.90039
[7] 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
[8] D’Ambrosio, C.: Application oriented Mixed Integer Nonlinear Programming. Ph.D. thesis, DEIS, Università di Bologna (2009) · Zbl 0981.90063
[9] 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) · Zbl 1179.90237
[10] D’Ambrosio, C.; Frangioni, A.; Liberti, L.; Lodi, A., On interval-subgradient and no-good cuts, Oper. Res. Lett., 38, 341-345, (2010) · Zbl 1202.90238
[11] 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
[12] Fischetti, M.; Glover, F.; Lodi, A., The feasibility pump, Math. Program. A, 104, 91-104, (2005) · Zbl 1077.90039
[13] Fischetti, M.; Lodi, A., Local branching, Math. Program., 98, 23-37, (2003) · Zbl 1060.90056
[14] Floudas, C., Global optimization in design and control of chemical process systems, J. Process Control, 10, 125-134, (2001)
[15] Glover, F.W., Tabu search—part I, ORSA J. Comput., 1, 190-206, (1989) · Zbl 0753.90054
[16] Hansen, P.; Mladenović, N., Variable neighbourhood search: principles and applications, Eur. J. Oper. Res., 130, 449-467, (2001) · Zbl 0981.90063
[17] IBM ILOG: IBM ILOG CPLEX 12.1 User’s Manual. IBM ILOG, Gentilly, France (2010) · Zbl 1163.90013
[18] Kilinç Karzan, F.; Nemhauser, G.L.; Savelsbergh, M.W.P., Information-based branching schemes for binary linear mixed-integer programs, Math. Program. Comput., 1, 249-293, (2009) · Zbl 1184.90114
[19] Liberti, L., Mladenović, N., Nannicini, G.: A good recipe for solving MINLPs. Math. Program. Comput. (2011). doi:10.1007/s12532-011-0031-y · Zbl 1276.90041
[20] Lindo Systems: LINDO Solver Suite: user manual. http://www.gams.com/solvers/lindoglobal.pdf · Zbl 1202.90238
[21] McCormick, G., Computability of global solutions to factorable nonconvex programs: part i—convex underestimating problems, Math. Program., 10, 146-175, (1976) · Zbl 0349.90100
[22] 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, France (2010) · Zbl 1257.90059
[23] Nannicini, G., Belotti, P., Liberti, L.: A local branching heuristic for MINLPs. Tech. Rep. 0812.2188 (2008). http://arxiv.org/abs/0812.2188 · Zbl 0237.52004
[24] Nemhauser G., Wolsey L.: Integer and Combinatorial Optimization. Wiley, New York (1988) · Zbl 0652.90067
[25] Sahinidis, N., BARON: a general purpose global optimization software package, J. Glob. Optim., 8, 201-205, (1996) · Zbl 0856.90104
[26] Shectman, J.; Sahinidis, N., A finite algorithm for global minimization of separable concave programs, J. Glob. Optim., 12, 1-36, (1998) · Zbl 0906.90159
[27] Smith, E.: On the optimal design of continuous processes. Ph.D. thesis, Imperial College of Science, Technology and Medicine, University of London (1996)
[28] 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)
[29] 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
[30] 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, 25-57, (2006) · Zbl 1134.90542
[31] Wolsey L.: Integer Programming. Wiley, New York (1998)
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.