Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

On the enumerative nature of Gomory’s dual cutting plane method

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

Abstract

For 30 years after their invention half a century ago, cutting planes for integer programs have been an object of theoretical investigations that had no apparent practical use. When they finally proved their practical usefulness in the late eighties, that happened in the framework of branch and bound procedures, as an auxiliary tool meant to reduce the number of enumerated nodes. To this day, pure cutting plane methods alone have poor convergence properties and are typically not used in practice. Our reason for studying them is our belief that these negative properties can be understood and thus remedied only based on a thorough investigation of such procedures in their pure form. In this paper, the second in a sequence, we address some important issues arising when designing a computationally sound pure cutting plane method. We analyze the dual cutting plane procedure proposed by Gomory in 1958, which is the first (and most famous) convergent cutting plane method for integer linear programming. We focus on the enumerative nature of this method as evidenced by the relative computational success of its lexicographic version (as documented in our previous paper on the subject), and we propose new versions of Gomory’s cutting plane procedure with an improved performance. In particular, the new versions are based on enumerative schemes that treat the objective function implicitly, and redefine the lexicographic order on the fly to mimic a sound branching strategy. Preliminary computational results are reported.

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
$34.99 /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 excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Achterberg, T., Koch, T., Martin, A.: MIPLIB 2003. Oper. Res. Lett. 34, 361–372 (2006). Problems available at http://miplib.zib.de

  2. Arthur J.L., Ravindran A.: PAGP, a partitioning algorithm for (linear) goal programming problems. ACM Trans. Math. Softw. 6(3), 378–386 (1980)

    Article  MATH  MathSciNet  Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

  4. Balinski M.L., Tucker A.W.: Duality theory of linear programs: A constructive approach with applications. SIAM Rev. 11(3), 347–377 (1969)

    Article  MATH  MathSciNet  Google Scholar 

  5. Bixby R.E., Ceria S., McZeal C.M., Savelsbergh M.W.P.: An updated mixed integer programming library: MIPLIB 3 0. Optima 58, 12–15 (1998)

    Google Scholar 

  6. Borg I., Groenen P.J.F.: Modern Multidimensional Scaling: Theory and Applications. Springer, Berlin (2005)

    MATH  Google Scholar 

  7. Chvátal V.: Edmonds polytopes and a hierarchy of combinatorial problems. Discrete Math. 4, 305–337 (1973)

    Article  MATH  MathSciNet  Google Scholar 

  8. Cook W., Kannan R., Schrijver A.: Chvátal closures for mixed integer programming problems. Math. Program. 47, 155–174 (1990)

    Article  MATH  MathSciNet  Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

  11. Gomory R.E.: Outline of an algorithm for integer solutions to linear programs. Bull. Am. Soc. 64, 275–278 (1958)

    Article  MATH  MathSciNet  Google Scholar 

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

  13. Gomory R.E.: An algorithm for integer solutions to linear programming. In: Graves, R.L., Wolfe, P. (eds) Recent Advances in Mathematical Programming, pp. 269–302. McGraw-Hill, New York (1963)

    Google Scholar 

  14. Nemhauser G., Wolsey L.: Integer and Combinatorial Optimization. Wiley, London (1988)

    MATH  Google Scholar 

  15. Nourie F.J., Venta E.R.: An upper bound on the number of cuts needed in Gomory’s method of integer forms. Oper. Res. Lett. 1, 129–133 (1982)

    Article  MATH  MathSciNet  Google Scholar 

  16. Tamiz M., Jones D.F., El-Darzi E.: A review of goal programming and its applications. Ann. Oper. Res. 58(1), 39–53 (1995)

    Article  MATH  MathSciNet  Google Scholar 

  17. Zanette, A., Fischetti, M., Balas, E.: Lexicography and degeneracy: Can a pure cutting plane algorithm work? Math. Program. (2010, to appear)

Download references

Author information

Authors and Affiliations

  1. Carnegie Mellon University, Pittsburgh, PA, USA

    Egon Balas

  2. DEI, University of Padova, Padova, Italy

    Matteo Fischetti & Arrigo Zanette

Authors
  1. Egon Balas
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Matteo Fischetti
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Arrigo Zanette
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Matteo Fischetti.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Balas, E., Fischetti, M. & Zanette, A. On the enumerative nature of Gomory’s dual cutting plane method. Math. Program. 125, 325–351 (2010). https://doi.org/10.1007/s10107-010-0392-4

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10107-010-0392-4

Keywords

Mathematics Subject Classification (2000)

Search

Navigation