Movatterモバイル変換

[0]ホーム
URL:

Skip to main content
Springer Nature Link
Log in

Projected Chvátal–Gomory cuts for mixed integer linear programs

  • FULL LENGTH PAPER
  • Published:
Mathematical Programming Submit manuscript

Abstract

Recent experiments by Fischetti and Lodi show that the first Chvátal closure of a pure integer linear program (ILP) often gives a surprisingly tight approximation of the integer hull. They optimize over the first Chvátal closure by modeling the Chvátal–Gomory (CG) separation problem as a mixed integer linear program (MILP) which is then solved by a general- purpose MILP solver. Unfortunately, this approach does not extend immediately to the Gomory mixed integer (GMI) closure of an MILP, since the GMI separation problem involves the solution of a nonlinear mixed integer program or a parametric MILP. In this paper we introduce a projected version of the CG cuts, and study their practical effectiveness for MILP problems. The idea is to project first the linear programming relaxation of the MILP at hand onto the space of the integer variables, and then to derive Chvátal–Gomory cuts for the projected polyhedron. Though theoretically dominated by GMI cuts, projected CG cuts have the advantage of producing a separation model very similar to the one introduced by Fischetti and Lodi, which can typically be solved in a reasonable amount of computing time.

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.

Similar content being viewed by others

References

  1. Ascheuer, N.: Hamiltonian path problems in the on-line optimization of flexible manufacturing systems. PhD Thesis, Technische Universität Berlin, Berlin (1995)

  2. Ascheuer, N., Fischetti, M., Grötschel, M.: A polyhedral study of the asymmetric travellingsalesman problem with time windows. Networks 36, 69–79 (2000)

    Article MATH MathSciNet  Google Scholar 

  3. Balas, E., Ceria, S., Cornuéjols, G.: A lift-and-project cutting plane algorithm for mixed 0-1programs. Math. Program. 58, 295–324 (1993)

    Article  Google Scholar 

  4. Balas, E., Saxena, A.: Optimizing over the Split Closure: Modeling and Theoretical Analysis, IMA “Hot Topics” Workshop: Mixed Integer Programming, Minneapolis, 25–29 July 2005

  5. Bixby, R.E., Ceria, S., McZeal, C.M., Savelsbergh, M.W.P.: MIPLIB 3.0, http://www.caam. rice.edu/~bixby/miplib/miplib.html

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

    Article MathSciNet  Google Scholar 

  7. Caprara, A., Letchford, A.N.: On the separation of split cuts and related inequalities. Math. Program. 94, 279–294 (2003)

    Article MATH MathSciNet  Google Scholar 

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

    Article MATH MathSciNet  Google Scholar 

  9. Codato, G., Fischetti, M.: Combinatorial Benders’ cuts for mixed-integer linear programming. Oper. Res. 54, 756–766 (2006)

    Article MathSciNet  Google Scholar 

  10. COIN-OR. www.coin-or.org

  11. 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 

  12. Cornuéjols, G., Li, Y.: On the rank of mixed 0,1 polyhedra.Math. Program. 91, 391–397 (2002)

    Article MATH MathSciNet  Google Scholar 

  13. Cornuéjols, G., Li, Y.: A connection between cutting plane theory and the geometry of numbers. Math. Program. 93, 123–127 (2002)

    Article MATH MathSciNet  Google Scholar 

  14. Dash, S., Günlük, O., Lodi, A.: On the MIR closure of polyhedra. IBM, T.J. Watson Research, Working paper (2005)

  15. Eisenbrand, F.:On the membership problem for the elementary closure of a polyhedron. Combinatorica 19, 297–300 (1999)

    Article MATH MathSciNet  Google Scholar 

  16. Fischetti, M., Lodi, A. : Optimizing over the first Ch closure. In: Jünger, M., Kaibel, V. (eds.) Integer Programming and Combinatorial Optimization—IPCO 2005, LNCS3509., pp. 12–22. Springer, Berlin Heidelberg New York (2005)

    Google Scholar 

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

    MATH MathSciNet  Google Scholar 

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

    Google Scholar 

  19. Grötschel, M., Lovász, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization. Springer, Berlin Heidelberg New York (1988)

    MATH  Google Scholar 

  20. ILOG Cplex 9.0: User’s Manual and Reference Manual, ILOG, S.A., http://www.ilog.com/ (2005)

  21. Klau,G.W., Mützel,P.: Optimal labelling of point features in rectangular labellingmodels.Math. Program. 94, 435–458 (2003)

    Article MATH MathSciNet  Google Scholar 

  22. Marchand, H., Wolsey, L.A.: Aggregation and mixed integer rounding to solve MIPs. Oper. Res. 49, 363–371 (2001)

    Article MathSciNet  Google Scholar 

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

    MATH  Google Scholar 

  24. Nemhauser,G.L.,Wolsey, L.A.:Arecursive procedure to generate all cuts for 0-1 mixed integer programs. Math. Program. 46, 379–390 (1990)

    Article MATH MathSciNet  Google Scholar 

  25. Schrijver, A.: On cutting planes. Ann. Discrete Math. 9, 291–296 (1980)

    Article MATH MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. IBM T.J. Watson Research Center, P.O. Box 218, Yorktown Heights, NY, 10598, USA

    Pierre Bonami & Sanjeeb Dash

  2. Tepper School of Business, Carnegie Mellon University, Pittsburgh, PA, 15213, USA

    Gérard Cornuéjols

  3. LIF, Faculté des Sciences de Luminy, 13288, Marseille, France

    Gérard Cornuéjols

  4. DEI, University of Padova, via Gradenigo 6A, 35131, Padova, Italy

    Matteo Fischetti

  5. DEIS, University of Bologna, viale Risorgimento 2, 40136, Bologna, Italy

    Andrea Lodi

Authors
  1. Pierre Bonami

    You can also search for this author inPubMed Google Scholar

  2. Gérard Cornuéjols

    You can also search for this author inPubMed Google Scholar

  3. Sanjeeb Dash

    You can also search for this author inPubMed Google Scholar

  4. Matteo Fischetti

    You can also search for this author inPubMed Google Scholar

  5. Andrea Lodi

    You can also search for this author inPubMed Google Scholar

Corresponding author

Correspondence toGérard Cornuéjols.

Additional information

Gérard Cornuéjols was supported in part by NSF grant DMI-0352885, ONR grant N00014-03-1-0188, and ANR grant BLAN 06-1-138894. Matteo Fischetti was supported in part by the EU projects ADONET (contract n. MRTN-CT-2003-504438) and ARRIVAL (contract n. FP6-021235-2). Andrea Lodi was supported in part by the EU projects ADONET (contract n. MRTN-CT-2003-504438) and ARRIVAL (contract n. FP6-021235-2).

Rights and permissions

About this article

Cite this article

Bonami, P., Cornuéjols, G., Dash, S.et al. Projected Chvátal–Gomory cuts for mixed integer linear programs.Math. Program.113, 241–257 (2008). https://doi.org/10.1007/s10107-006-0051-y

Download citation

Keywords

Mathematics Subject Classification (2000)

Access this article

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.

Advertisement

[8]ページ先頭
©2009-2025 Movatter.jp