Rounding-based heuristics for nonconvex MINLPs | Mathematical Programming Computation Skip to main content
Springer Nature Link
Log in

Rounding-based heuristics for nonconvex MINLPs

  • Full Length Paper
  • Published:
Mathematical Programming Computation Aims and scope Submit manuscript

Abstract

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Balas E., Jeroslow R.: Canonical cuts on the unit hypercube. SIAM J. Appl. Math. 23(1), 61–69 (1972)

    Article  MathSciNet  MATH  Google Scholar 

  2. Belotti, P.: Couenne: a user’s manual. Tech. Rep., Lehigh University (2009). http://www.coin-or.org/Couenne

  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(4–5), 597–634 (2008)

    Google Scholar 

  4. Biegler L., Grossmann I., Westerberg A.: Systematic Methods of Chemical Process Design. Prentice Hall, Upper Saddle River (NJ) (1997)

    Google Scholar 

  5. Bonami P., Cornuéjols G., Lodi A., Margot F.: A feasibility pump for Mixed Integer Nonlinear Programs. Math. Program. 119(2), 331–352 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  6. Bonami, P., Gonçalves, J.: Primal heuristics for mixed-integer nonlinear programs. Tech. Rep. RC24639, IBM (2008)

  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

  8. D’Ambrosio, C.: Application oriented Mixed Integer Nonlinear Programming. Ph.D. thesis, DEIS, Università di Bologna (2009)

  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)

  10. D’Ambrosio C., Frangioni A., Liberti L., Lodi A.: On interval-subgradient and no-good cuts. Oper. Res. Lett. 38(5), 341–345 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  11. Danna E., Rothberg E., Le Pape C.: Exploring relaxation induced neighborhoods to improve MIP solutions. Math. Program. A 102, 71–90 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  12. Fischetti M., Glover F., Lodi A.: The feasibility pump. Math. Program. A 104(1), 91–104 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  13. Fischetti M., Lodi A.: Local branching. Math. Program. 98, 23–37 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  14. Floudas C.: Global optimization in design and control of chemical process systems. J. Process Control 10, 125–134 (2001)

    Article  Google Scholar 

  15. Glover F.W.: Tabu search—part I. ORSA J. Comput. 1(3), 190–206 (1989)

    Article  MATH  Google Scholar 

  16. Hansen P., Mladenović N.: Variable neighbourhood search: principles and applications. Eur. J. Oper. Res. 130, 449–467 (2001)

    Article  MATH  Google Scholar 

  17. IBM ILOG: IBM ILOG CPLEX 12.1 User’s Manual. IBM ILOG, Gentilly, France (2010)

  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)

    Article  MathSciNet  MATH  Google Scholar 

  19. Liberti, L., Mladenović, N., Nannicini, G.: A good recipe for solving MINLPs. Math. Program. Comput. (2011). doi:10.1007/s12532-011-0031-y

  20. Lindo Systems: LINDO Solver Suite: user manual. http://www.gams.com/solvers/lindoglobal.pdf

  21. McCormick G.: Computability of global solutions to factorable nonconvex programs: Part i—convex underestimating problems. Math. Program. 10, 146–175 (1976)

    Article  MathSciNet  Google Scholar 

  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)

  23. Nannicini, G., Belotti, P., Liberti, L.: A local branching heuristic for MINLPs. Tech. Rep. 0812.2188 (2008). http://arxiv.org/abs/0812.2188

  24. Nemhauser G., Wolsey L.: Integer and Combinatorial Optimization. Wiley, New York (1988)

    Book  MATH  Google Scholar 

  25. Sahinidis N.: BARON: a general purpose global optimization software package. J. Glob. Optim. 8(2), 201–205 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  26. Shectman J., Sahinidis N.: A finite algorithm for global minimization of separable concave programs. J. Glob. Optim. 12, 1–36 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  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)

    Article  Google Scholar 

  29. Tawarmalani M., Sahinidis N.: Global optimization of mixed integer nonlinear programs: a theoretical and computational study. Math. Program. 99, 563–591 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  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(1), 25–57 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  31. Wolsey L.: Integer Programming. Wiley, New York (1998)

    MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Singapore University of Technology and Design, Singapore, Singapore

    Giacomo Nannicini

  2. Sloan School of Management, Massachusetts Institute of Technology, Cambridge, MA, USA

    Giacomo Nannicini

  3. Department of Mathematical Sciences, Clemson University, Clemson, SC, USA

    Pietro Belotti

Authors
  1. Giacomo Nannicini
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Pietro Belotti
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Giacomo Nannicini.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Nannicini, G., Belotti, P. Rounding-based heuristics for nonconvex MINLPs. Math. Prog. Comp. 4, 1–31 (2012). https://doi.org/10.1007/s12532-011-0032-x

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s12532-011-0032-x

Mathematics Subject Classification (2000)

Search

Navigation