Skip to main content
SpringerLink
Log in

A storm of feasibility pumps for nonconvex MINLP

  • Full Length Paper
  • Series B
  • Published:
Mathematical Programming Submit manuscript

Abstract

One of the foremost difficulties in solving Mixed-Integer Nonlinear Programs, either with exact or heuristic methods, is to find a feasible point. We address this issue with a new feasibility pump algorithm tailored for nonconvex Mixed-Integer Nonlinear Programs. Feasibility pumps are algorithms that iterate between solving a continuous relaxation and a mixed-integer relaxation of the original problems. Such approaches currently exist in the literature for Mixed-Integer Linear Programs and convex Mixed-Integer Nonlinear Programs: both cases exhibit the distinctive property that the continuous relaxation can be solved in polynomial time. In nonconvex Mixed-Integer Nonlinear Programming such a property does not hold, and therefore special care has to be exercised in order to allow feasibility pump algorithms to rely only on local optima of the continuous relaxation. Based on a new, high level view of feasibility pump algorithms as a special case of the well-known successive projection method, we show that many possible different variants of the approach can be developed, depending on how several different (orthogonal) implementation choices are taken. A remarkable twist of feasibility pump algorithms is that, unlike most previous successive projection methods from the literature, projection is “naturally” taken in two different norms in the two different subproblems. To cope with this issue while retaining the local convergence properties of standard successive projection methods we propose the introduction of appropriate norm constraints in the subproblems; these actually seem to significantly improve the practical performance of the approach. We present extensive computational results on the MINLPLib, showing the effectiveness and efficiency of our algorithm.

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

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6

Similar content being viewed by others

Notes

  1. These failures happen in practice as shown in Sect. 5.4.

  2. Note that again the objective function is defined in the MIQP case only on the integer variables.

  3. No detailed computational results are reported here for the preliminary computational investigation, some of them are discussed in detail in [16].

  4. Note that this is the same issue discussed in the solution pool case.

References

  1. Achterberg, T., Berthold, T.: Improving the feasibility pump. Discrete Opt. 4, 77–86 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  2. Al-Khayyal, F.A., Sherali, H.D.: On finitely terminating branch-and-bound algorithms for some global optimization problems. SIAM J. Opt. 10, 1049–1057 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  3. Attouch, H., Bolte, J., Redont, P., Soubeyran, A.: Proximal Alternating Minimization and Projection Methods for Nonconvex Problems: An Approach Based on the Kurdyka-Lojasiewicz Inequality. Math. Oper. Res. 35, 438–457 (2010)

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  5. Bauschke, H.H., Borwein, J.M.: On projection algorithms for solving convex feasibility problems. SIAM Rev. 38, 367–426 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  6. Belotti, P., Lee, J., Liberti, L., Margot, F., Wächter, A.: Branching and bound tightening techniques for non-convex MINLP. Opt. Methods Softw. 24, 597–634 (2009)

    Article  MATH  Google Scholar 

  7. Berthold, T., Gleixner, A.: Undercover primal MINLP heuristic. In: Bonami, P., Liberti, L., Miller, A., Sartenaer, A. (eds.) Proceedings of the European Workshop on Mixed-Integer Nonlinear Programming, pp. 103–113. Université de la Méditerranée, Marseille (2010)

  8. Bonami, P., Cornuéjols, G., Lodi, A., Margot, F.: A feasibility pump for mixed integer nonlinear programs. Math. Prog. 119, 331–352 (2009)

    Google Scholar 

  9. Bonami, P., Gonçalves, J.: Primal heuristics for mixed integer nonlinear programs. Technical report, IBM (2008)

  10. Bonami, P., Lee, J.: BONMIN user’s manual. IBM Corporation, Technical report (June 2007)

  11. Bruglieri, M., Liberti, L.: Optimal running and planning of a biomass-based energy production process. Energy Policy 36, 2430–2438 (2008)

    Article  Google Scholar 

  12. Bussieck, M.R., Drud, A.S., Meeraus, A.: MINLPLib—a collection of test models for mixed-integer nonlinear programming. INFORMS J. Comput. 15, 114–119 (2003)

    Google Scholar 

  13. COIN-OR. Introduction to IPOPT: a tutorial for downloading, installing, and using IPOPT (2006)

  14. COUENNE. https://projects.coin-or.org/Couenne, v. 0.1

  15. D’Ambrosio, C.: Application-oriented Mixed Integer Non-Linear Programming. PhD thesis, DEIS, Università di Bologna (2009)

  16. D’Ambrosio, C., Frangioni, A., Liberti, L., Lodi, A.: Experiments with a feasibility pump approach for nonconvex MINLPs. In: Festa, P. (ed.) Symposium on Experimental Algorithms, volume 6049 of LNCS, pp. 350–360. Springer, Heidelberg (2010)

    Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  18. d’Antonio, G., Frangioni, A.: Convergence analysis of deflected conditional approximate subgradient methods. SIAM J. Opt. 20, 357–386 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  19. Duran, M., Grossmann, I.: An outer-approximation algorithm for a class of mixed-integer nonlinear programs. Math. Prog. 36, 307–339 (1986)

    Article  MathSciNet  MATH  Google Scholar 

  20. Fischetti, M., Glover, F., Lodi, A.: The feasibility pump. Math. Prog. 104, 91–104 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  21. Fletcher, R., Leyffer, S.: Solving mixed integer nonlinear programs by outer approximation. Math. Prog. 66, 327–349 (1994)

    Article  MathSciNet  MATH  Google Scholar 

  22. Fourer, R., Gay, D., Kernighan, B.: AMPL: A Modeling Language for Mathematical Programming, 2nd edn. Duxbury Press, Brooks, Cole Publishing Co., Florence, KY (2003)

    Google Scholar 

  23. Grippo, L., Sciandrone, M.: On the convergence of the block nonlinear Gauss-Seidel method under convex constraints. Oper. Res. Lett. 26, 127–136 (2000)

    Article  MathSciNet  MATH  Google Scholar 

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

    Google Scholar 

  25. ILOG. ILOG CPLEX 11.0 User’s Manual. ILOG S.A., Gentilly, France (2008)

  26. Liberti, L.: Writing global optimization software. In: Liberti, L., Maculan, N. (eds.) Global Optimization: From Theory to Implementation, pp. 211–262. Springer, Berlin (2006)

    Google Scholar 

  27. Liberti, L., Cafieri, S., Savourey, D.: Reformulation Optimization Software Engine. In: Fukuda, K., van der Hoeven, J., Joswig, M., Takayama, N. (eds.) Mathematical Software, vol. 6327, pp. 303–314. LNCS Springer, New York (2010)

  28. Liberti, L., Cafieri, S., Tarissan, F.: Reformulations in mathematical programming: A computational approach. In: Abraham, A., Hassanien, A.-E., Siarry, P., Engelbrecht, A. (eds.) Foundations of Computational Intelligence, vol. 3, pp. 153–234. Studies in Computational Intelligence, Springer, Berlin (2009)

  29. Liberti, L., Dražic, M.: Variable neighbourhood search for the global optimization of constrained NLPs. In: Proceedings of GO Workshop, Almeria, Spain (2005)

  30. Liberti, L., Mladenović, N., Nannicini, G.: A good recipe for solving MINLPs. In: Maniezzo, V., Stützle, T., Voß, S. (eds.) Hybridizing metaheuristics and mathematical programming, vol. 10, pp. 231–244. Annals of Information Systems, Springer, New York (2009)

  31. Nannicini, G., Belotti, P.: Local branching for MINLPs. Technical report, CMU (2009)

  32. Nannicini, G., Belotti, P.: Rounding-based heuristics for nonconvex MINLPs. Technical report, CMU (2009)

  33. Schoen, F.: Two-phase methods for global optimization. In: Pardalos, P.M., Romeijn, H.E. (eds.) Handbook of Global Optimization, vol. 2, pp. 151–177. Kluwer, Dordrecht (2002)

  34. Tseng, P.: Convergence of a block coordinate descent method for nondifferentiable minimization. J. Opt. Theory Appl. 109, 475–494 (2001)

    Google Scholar 

  35. Tuy, H.: Convex Analysis and Global Optimization. Kluwer, Dordrecht (1998)

    MATH  Google Scholar 

  36. Vavasis, S.A.: Nonlinear Optimization: Complexity Issues. Oxford University Press, Oxford (1991)

    MATH  Google Scholar 

  37. von Neumann, J.: Functional Operators, Vol. II. Princeton University Press, Princeton (1950)

Download references

Acknowledgments

One of the authors (LL) is grateful for the following financial support: ANR 07-JCJC-0151 “ARS”and 08-SEGI-023 “AsOpt”; Digiteo Emergence “ARM”, Emergence “PASO”, Chair “RMNCCO”; Microsoft-CNRS Chair “OSD”. The remaining three authors are grateful to the other author (LL) for not making them feel too “poor”. We thank two anonymous referees for a careful reading and useful comments. Part of this work was conducted while the first author was a post-doctoral student at the ISyE, University of Wisconsin-Madison and DEIS, University of Bologna. The support of both institutions is strongly acknowledged.

Author information

Authors and Affiliations

  1. LIX, Ecole Polytechnique, Paris, France

    Claudia D’Ambrosio & Leo Liberti

  2. Dipartimento di Informatica, Università di Pisa, Pisa, Italy

    Antonio Frangioni

  3. DEI, Universitá di Bologna, Bologna, Italy

    Andrea Lodi

Authors
  1. Claudia D’Ambrosio
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Antonio Frangioni
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Leo Liberti
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Andrea Lodi
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Andrea Lodi.

Additional information

This paper extends [16].

Rights and permissions

Reprints and permissions

About this article

Cite this article

D’Ambrosio, C., Frangioni, A., Liberti, L. et al. A storm of feasibility pumps for nonconvex MINLP. Math. Program. 136, 375–402 (2012). https://doi.org/10.1007/s10107-012-0608-x

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10107-012-0608-x

Keywords

Mathematics Subject Classification

Search

Navigation