Skip to main content
SpringerLink
Log in

Lift-and-project cuts for convex mixed integer nonlinear programs

Linear programming based separation and extended formulations

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

Abstract

We describe a computationally effective method for generating lift-and-project cuts for convex mixed-integer nonlinear programs (MINLPs). The method relies on solving a sequence of cut-generating linear programs and in the limit generates an inequality as strong as the lift-and-project cut that can be obtained from solving a cut-generating nonlinear program. Using this procedure, we are able to approximately optimize over the rank one lift-and-project closure for a variety of convex MINLP instances. The results indicate that lift-and-project cuts have the potential to close a significant portion of the integrality gap for convex MINLPs. In addition, we find that using this procedure within a branch-and-cut solver for convex MINLPs significantly reduces the total solution time for many instances. We also demonstrate that combining lift-and-project cuts with an extended formulation that exploits separability of convex functions yields significant improvements in both relaxation bounds and the time to calculate the relaxation. Overall, these results suggest that with an effective separation routine, like the one proposed here, lift-and-project cuts may be as effective for solving convex MINLPs as they have been for solving mixed-integer linear programs.

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

Similar content being viewed by others

References

  1. Abhishek, K., Leyffer, S., Linderoth, J.T.: FilMINT: an outer-approximation-based solver for nonlinear mixed integer programs. INFORMS J. Comput. 22, 555–567 (2010)

    Article  MATH  MathSciNet  Google Scholar 

  2. Atamtürk, A., Narayanan, V.: Conic mixed integer rounding cuts. Math. Program. 122, 1–20 (2010)

    Article  MATH  MathSciNet  Google Scholar 

  3. Balas, E.: Disjunctive programming. Ann. Discret. Math. 5, 3–51 (1979)

    Article  MATH  MathSciNet  Google Scholar 

  4. Balas, E.: A modified lift-and-project procedure. Math. Program. 79, 19–31 (1997)

    MATH  MathSciNet  Google Scholar 

  5. Balas, E., Ceria, S., Cornuejols, G.: Mixed 0–1 programming by lift-and-project in a branch-and-cut framework. Manag. Sci. 42, 1229–1246 (1996)

    Article  MATH  Google Scholar 

  6. Balas, E., Jeroslow, R.G.: Strengthening cuts for mixed integer programs. Eur. J. Oper. Res. 4, 224–234 (1980)

    Article  MATH  MathSciNet  Google Scholar 

  7. Balas, E., Perregaard, M.: A precise correspondence between lift-and-project cuts, simple disjunctive cuts. Math. Program. Ser. B 94, 221–245 (2003)

    Article  MATH  Google Scholar 

  8. Balas, E., Saxena, A.: Optimizing over the split closure. Math. Program. 113, 219–240 (2008)

    Article  MATH  MathSciNet  Google Scholar 

  9. Bertsekas, D., Gallager, R.: Data Networks, 2nd edn. Prentice-Hall Inc, Upper Saddle River (1992)

    MATH  Google Scholar 

  10. Bodur, M., Dash, S., Günlük, O.: Cutting planes from extended LP formulations. Math. Program. (2016). doi:10.1007/s10107-016-1005-7

    MATH  Google Scholar 

  11. Bodur, M., Dash, S., Günlük, O., Luedtke, J.: Strengthened Benders Cuts for Stochastic Integer Programs with Continuous Recourse. http://www.optimization-online.org/DB_HTML/2014/03/4263.html (2014)

  12. Bonami, P.: Lift-and-project cuts for mixed integer convex programs. In: Günlük, O., Woeginger, G. (eds.) Integer Programming and Combinatoral Optimization, Lecture Notes in Computer Science, vol. 6655, pp. 52–64. Springer, Berlin (2011). doi:10.1007/978-3-642-20807-2_5

    Chapter  Google Scholar 

  13. Bonami, P.: On optimizing over lift-and-project closures. Math. Program. Comput. 4, 151–179 (2012)

    Article  MATH  MathSciNet  Google Scholar 

  14. Bonami, P., Minoux, M.: Using rank-1 lift-and-project closures to generate cuts for 0–1 MIPs, a computational investigation. Discret. Optim. 2, 288–307 (2005)

    Article  MATH  MathSciNet  Google Scholar 

  15. Bonami, P., Tramontani, A.: Advances in CPLEX for mixed integer nonlinear optimization. International Symposium on Mathematical Programming. Pittsburgh. PA, USA (2015)

  16. Boorstyn, R., Frank, H.: Large-scale network topological optimization. IEEE Trans. Commun. 25, 29–47 (1977)

    Article  MATH  Google Scholar 

  17. Borchers, B., Mitchell, J.E.: An improved branch and bound algorithm for mixed integer nonlinear programs. Comput. Oper. Res. 21, 359–368 (1994)

    Article  MATH  MathSciNet  Google Scholar 

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

  19. Castillo, I., Westerlund, J., Emet, S., Westerlund, T.: Optimization of block layout design problems with unequal areas: a comparison of MILP and MINLP optimization methods. Comput. Chem. Eng. 30, 54–69 (2005)

    Article  Google Scholar 

  20. Ceria, S., Soares, J.: Convex programming for disjunctive optimization. Math. Program. 86, 595–614 (1999)

    Article  MATH  MathSciNet  Google Scholar 

  21. Cezik, M.T., Iyengar, G.: Cuts for mixed 0–1 conic programming. Math. Program. 104, 179–202 (2005)

    Article  MATH  MathSciNet  Google Scholar 

  22. Conforti, M., Cornuéjols, G., Zambelli, G.: Polyhedral approaches to mixed integer linear programming. In: Jünger, M., Liebling, T., Naddef, D., Pulleyblank, W., Reinelt, G., Rinaldi, G., Wolsey, L. (eds.) 50 Years of Integer Programming 1958–2008, pp. 343–385. Springer, New York (2009)

    Google Scholar 

  23. Cornuéjols, G.: Valid inequalities for mixed integer linear programs. Math. Program. Ser. B 112, 3–44 (2008)

    Article  MATH  MathSciNet  Google Scholar 

  24. Dash, S., Günlük, O., Lodi, A.: MIR closures of polyhedral sets. Math. Program. 121, 33–60 (2010)

    Article  MATH  MathSciNet  Google Scholar 

  25. Dash, S., Günlük, O., Vielma, J.: Computational experiments with cross and crooked cross cuts. INFORMS J. Comput. 26, 780–797 (2014)

    Article  MATH  MathSciNet  Google Scholar 

  26. Dolan, E., Moré, J.: Benchmarking optimization software with performance profiles. Math. Program. 91, 201–213 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  27. Drewes, S.: Mixed Integer Second Order Cone Programming. Ph.D. thesis, Technische Universität Darmstadt (2009)

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

    Article  MATH  MathSciNet  Google Scholar 

  29. Elhedhli, S.: Service system design with immobile servers, stochastic demand, and congestion. Manuf. Serv. Oper. Manag. 8, 92–97 (2006)

    Article  Google Scholar 

  30. Fischetti, M., Lodi, A.: Optimizing over the first Chvátal closure. Math. Program. Ser. B 110, 3–20 (2007)

    Article  MATH  Google Scholar 

  31. Fischetti, M., Lodi, A., Tramontani, A.: On the separation of disjunctive cuts. Math. Program. 128, 205–230 (2011)

    Article  MATH  MathSciNet  Google Scholar 

  32. Fletcher, R., Leyffer, S.: User Manual for FilterSQP. University of Dundee Numerical Analysis Report NA-181 (1998)

  33. Frangioni, A., Gentile, C.: Perspective cuts for a class of convex 0–1 mixed integer programs. Math. Program. 106, 225–236 (2006)

    Article  MATH  MathSciNet  Google Scholar 

  34. Gomory, R.E.: An Algorithm for the Mixed Integer Problem. Technical Report RM-2597, The RAND Corporation (1960)

  35. Günlük, O., Lee, J., Weismantel, R.: MINLP strengthening for separable convex quadratic transportation-cost UFL. Technical Report RC24213 (W0703-042), IBM Research Division (2007)

  36. Günlük, O., Linderoth, J.: Perspective relaxation of mixed integer nonlinear programs with indicator variables. In: Lodi, A., Panconesi, A., Rinaldi, G. (eds.) IPCO, Lecture Notes in Computer Science, vol. 5035, pp. 1–16. Springer, New York (2008)

    Google Scholar 

  37. Harjunkoski, I., Westerlund, T., Porn, R., Skrifvars, H.: Different transformations for solving non-convex trim loss problems by MINLP. Eur. J. Oper. Res. 105, 594–603 (1998)

    Article  MATH  Google Scholar 

  38. Hijazi, H., Bonami, P., Ouorou, A.: An outer-inner approximation for separable mixed-integer nonlinear programs. INFORMS J. Comput. 26, 31–44 (2014)

    Article  MATH  MathSciNet  Google Scholar 

  39. Hiriart-Urruty, J.B., Lemarechal, C.: Convex Analysis and Minimization Algorithms I: Fundamentals (Grundlehren Der Mathematischen Wissenschaften). Springer, New York (1993)

    MATH  Google Scholar 

  40. IBM: Using the CPLEX Callable Library, Version 12 (2009)

  41. Kelley, J.: The cutting-plane method for solving convex programs. J. SIAM 8, 703–712 (1960)

    MATH  MathSciNet  Google Scholar 

  42. Kılınç, M., Linderoth, J., Luedtke, J.: Effective Separation of Disjunctive Cuts for Convex Mixed Integer Nonlinear Programs. Technical Report 1681, Computer Sciences Department, University of Wisconsin-Madison (2010)

  43. Kılınç, M.R.: Disjunctive Cutting Planes and Algorithms for Convex Mixed Integer Nonlinear Programming. Ph.D. thesis, University of Wisconsin-Madison (2011)

  44. Leyffer, S.: MacMINLP: Test Problems for Mixed Integer Nonlinear Programming. http://www-unix.mcs.anl.gov/~leyffer/macminlp (2003)

  45. Modaresi, S., Kılınç, M., Vielma, J.P.: Intersection cuts for nonlinear integer programming: convexification techniques for structured sets. Math. Program. 155, 575–611 (2016)

    Article  MATH  MathSciNet  Google Scholar 

  46. Modaresi, S., Kılınç, M.R., Vielma, J.P.: Split cuts and extended formulations for mixed integer conic quadratic programming. Oper. Res. Lett. 43(1), 10–15 (2015)

    Article  MathSciNet  Google Scholar 

  47. Nemhauser, G., Wolsey, L.: A recursive procedure for generating all cuts for 0–1 mixed integer programs. Math. Program. 46, 379–390 (1990)

    Article  MATH  Google Scholar 

  48. Nemhauser, G.L., Savelsbergh, M.W.P., Sigismondi, G.C.: MINTO, a mixed INTeger optimizer. Oper. Res. Lett. 15, 47–58 (1994)

    Article  MATH  MathSciNet  Google Scholar 

  49. Quesada, I., Grossmann, I.E.: An LP/NLP based branch-and-bound algorithm for convex MINLP optimization problems. Comput. Chem. Eng. 16, 937–947 (1992)

    Article  Google Scholar 

  50. Ravemark, D.E., Rippin, D.W.T.: Optimal design of a multi-product batch plant. Comput. Chem. Eng. 22(1–2), 177–183 (1998)

    Article  Google Scholar 

  51. Sawaya, N.: Reformulations, Relaxations and Cutting Planes for Generalized Disjunctive Programming. Ph.D. thesis, Chemical Engineering Department, Carnegie Mellon University (2006)

  52. Sawaya, N., Laird, C.D., Biegler, L.T., Bonami, P., Conn, A.R., Cornuéjols, G., Grossmann, I.E., Lee, J., Lodi, A., Margot, F., Wächter, A.: CMU-IBM Open Source MINLP Project Test Set. http://egon.cheme.cmu.edu/ibm/page.htm. Accessed 19 April 2016

  53. Stubbs, R., Mehrotra, S.: A branch-and-cut method for 0–1 mixed convex programming. Math. Program. 86, 515–532 (1999)

    Article  MATH  MathSciNet  Google Scholar 

  54. Tawarmalani, M., Sahinidis, N.: A polyhedral branch-and-cut approach to global optimization. Math. Program. 103(2), 225–249 (2005)

    Article  MATH  MathSciNet  Google Scholar 

  55. Türkay, M., Grossmann, I.E.: Logic-based MINLP algorithms for the optimal synthesis of process networks. Comput. Chem. Eng. 20(8), 959–978 (1996)

    Article  Google Scholar 

  56. Vecchietti, A., Grossmann, I.E.: LOGMIP: a disjunctive 0–1 non-linear optimizer for process system models. Comput. Chem. Eng. 23(4–5), 555–565 (1999). doi:10.1016/S0098-1354(98)00293-2. http://www.sciencedirect.com/science/article/B6TFT-3XY28Y0-B/2/2709e69a55450cf2263efcc5368850db

  57. Vielma, J., Dunning, I., Huchette, J., Lubin, M.: Extended Formulations in Mixed Integer Conic Quadratic Programming. Technical Report. http://arxiv.org/abs/1505.07857 (2015)

  58. Zhu, Y., Kuno, T.: A disjunctive cutting-plane-based branch-and-cut algorithm for 0–1 mixed-integer convex nonlinear programs. Ind. Eng. Chem. Res. 45(1), 187–196 (2006). doi:10.1021/ie0402719

    Article  Google Scholar 

Download references

Acknowledgements

This work was supported in part by the U.S. National Science Foundation (CCF-0830153) and by the U.S. Department of Energy, Office of Science, Office of Advanced Scientific Computing Research, Applied Mathematics program under contract numbers DE-AC02-06CH11357 and DE-FG02-08ER25861. The authors would like to thank Andrew Miller for his insightful comments on this work.

Author information

Authors and Affiliations

  1. Department of Chemical Engineering, Carnegie Mellon University, Pittsburgh, PA, USA

    Mustafa R. Kılınç

  2. Department of Industrial and Systems Engineering, Wisconsin Institutes of Discovery, University of Wisconsin-Madison, Madison, WI, USA

    Jeff Linderoth & James Luedtke

Authors
  1. Mustafa R. Kılınç
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Jeff Linderoth
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. James Luedtke
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Mustafa R. Kılınç.

Electronic supplementary material

Below is the link to the electronic supplementary material.

Supplementary material 1 (pdf 156 KB)

Appendix

Appendix

Table 6 presents the gaps closed when using monoidal strenghthening to obtain strengthened lift-and-project cuts in the closure experiment presented in Sect. 6.3. The structure of this table is identical to that of Table 3. Table 3 in the Electronic Supplementary Material provides the results for each individual instance.

Table 6 Strengthened lift-and-project closure results summarized by instance family
Full size table

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Kılınç, M.R., Linderoth, J. & Luedtke, J. Lift-and-project cuts for convex mixed integer nonlinear programs. Math. Prog. Comp. 9, 499–526 (2017). https://doi.org/10.1007/s12532-017-0118-1

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s12532-017-0118-1

Keywords

Mathematics Subject Classification

Search

Navigation