Skip to main content
SpringerLink
Log in

A Simplex-Based Algorithm for 0-1 Mixed Integer Programming

  • Chapter
  • First Online:
Combinatorial Optimization — Eureka, You Shrink!

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 2570))

Abstract

We present a finitely convergent cutting plane algorithm for 0-1 mixed integer programming. The algorithm is a hybrid between a strong cutting plane and a Gomory-type algorithm that generates violated facet-defining inequalities of a relaxation of the simplex tableau and uses them as cuts for the original problem. We show that the cuts can be computed in polynomial time and can be embedded in a finitely convergent algorithm.

This research was supported by NSF grants DMI-0100020 and DMI-0121495

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

Access this chapter

Log in via an institution
eBook
USD 16.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 16.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. E. Balas. Facets of the knapsack polytope. Mathematical Programming, 8:146–164, 1975.

    Article  MATH  MathSciNet  Google Scholar 

  2. E. Balas, S. Ceria, and G. Cornuéjols. A lift-and-project cutting plane algorithm for mixed 0-1 programs. Mathematical Programming, 58:295–324, 1993.

    Article  MathSciNet  Google Scholar 

  3. E. Balas and E. Zemel. Facets of the knapsack polytope from minimal covers. SIAM Journal on Applied Mathematics, 34:119–148, 1978.

    Article  MATH  MathSciNet  Google Scholar 

  4. V.J. Bowman and G.L. Nemhauser. A finiteness proof for modified Dantzig cuts in integer programming. Naval Research Logistics Quarterly, 17:309–313, 1970.

    Article  MathSciNet  Google Scholar 

  5. H.P. Crowder, E.L. Johnson, and M.W. Padberg. Solving large-scale zero-one linear programming problems. Operations Research, 31:803–834, 1983.

    MATH  Google Scholar 

  6. G.B. Dantzig. Note on solving linear programs in integers. Naval Research Logistics Quarterly, 6:75–76, 1959.

    Article  MathSciNet  Google Scholar 

  7. R.E. Gomory. Outline of an algorithm for integer solutions to linear programs. Bulletin of the American Mathematical Society, 64:275–278, 1958.

    Article  MATH  MathSciNet  Google Scholar 

  8. R.E. Gomory. An algorithm for the mixed integer problem. Technical Report RM-2597, RAND Corporation, 1960.

    Google Scholar 

  9. R.E. Gomory and A.J. Hoffman. On the convergence of an integer programming process. Naval Research Logistics Quarterly, 10:121–124, 1963.

    Article  MATH  MathSciNet  Google Scholar 

  10. Z. Gu, G.L. Nemhauser, and M.W.P. Savelsbergh. Lifted cover inequalities for 0-1 integer programs: Complexity. INFORMS Journal on Computing, 11:117–123, 1999.

    MATH  MathSciNet  Google Scholar 

  11. P.L. Hammer, E.L. Johnson, and U.N. Peled. Facets of regular 0-1 polytopes. Mathematical Programming, 8:179–206, 1975.

    Article  MATH  MathSciNet  Google Scholar 

  12. E.L. Johnson, G.L. Nemhauser, and M.W.P. Savelsbergh. Progress in linear programming based branch-and-bound algorithms: an exposition. INFORMS Journal on Computing, 12:2–23, 2000.

    Article  MATH  MathSciNet  Google Scholar 

  13. H. Marchand, A. Martin, R. Weismantel, and L. Wolsey. Cutting planes in integer and mixed integer programming. Technical Report 9953, Université Catholique de Louvain, 1999.

    Google Scholar 

  14. H. Marchand and L.A. Wolsey. The 0-1 knapsack problem with a single continuous variable. Mathematical Programming, 85:15–33, 1999.

    Article  MATH  MathSciNet  Google Scholar 

  15. G.L. Nemhauser and L.A. Wolsey. Integer and Combinatorial Optimization. Wiley, New York, 1988.

    MATH  Google Scholar 

  16. G.L. Nemhauser and L.A. Wolsey. A recursive procedure for generating all cuts for 0-1 mixed integer programs. Mathematical Programming, 46:379–390, 1990.

    Article  MATH  MathSciNet  Google Scholar 

  17. F.J. Nourie and E.R. Venta. An upper bound on the number of cuts needed in Gomory’s method of integer forms. Operations Research Letters, 1:129–133, 1982.

    Article  MATH  MathSciNet  Google Scholar 

  18. J.-P. P. Richard, I.R. de Farias, and G.L. Nemhauser. Lifted inequalities for 0-1 mixed integer programming: Basic theory and algorithms. Technical Report 02-05, Georgia Institute of Technology, 2002.

    Google Scholar 

  19. J.-P. P. Richard, I.R. de Farias, and G.L. Nemhauser. Lifted inequalities for 0-1 mixed integer programming: Superlinear lifting. Technical report, Georgia Institute of Technology, 2002. (in preparation).

    Google Scholar 

  20. L.A. Wolsey. Faces for a linear inequality in 0-1 variables. Mathematical Programming, 8:165–178, 1975.

    Article  MATH  MathSciNet  Google Scholar 

  21. E. Zemel. Easily computable facets of the knapsack polytope. Mathematics of Operations Research, 14:760–764, 1989.

    Article  MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. School of Industrial and Systems Engineering, Georgia Institute of Technology, 30332-0205, Atlanta, GA, USA

    Jean-Philippe P. Richard & George L. Nemhauser

  2. Center for Operations Research and Econometrics, 34 Voie du Roman Pays, 1348, Louvain-La-Neuve, Belgium

    Ismael R. de Farias

Authors
  1. Jean-Philippe P. Richard
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Ismael R. de Farias
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. George L. Nemhauser
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Institut für Informatik, Universität zu Köln, Pohligstr. 1, 50969, Köln, Germany

    Michael Jünger

  2. Institut für Informatik, Universität Heidelberg, Im Neuenheimer Feld 368, 69120, Heidelberg, Germany

    Gerhard Reinelt

  3. Istituto di Analisi dei Sistemi ed Informatica “Antonio Ruberti”, CNR, viale Manzoni 30, 00185, Rome, Italy

    Giovanni Rinaldi

Rights and permissions

Reprints and permissions

Copyright information

© 2003 Springer-Verlag Berlin Heidelberg

About this chapter

Cite this chapter

Richard, JP.P., de Farias, I.R., Nemhauser, G.L. (2003). A Simplex-Based Algorithm for 0-1 Mixed Integer Programming. In: Jünger, M., Reinelt, G., Rinaldi, G. (eds) Combinatorial Optimization — Eureka, You Shrink!. Lecture Notes in Computer Science, vol 2570. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-36478-1_15

Download citation

  • DOI: https://doi.org/10.1007/3-540-36478-1_15

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-00580-3

  • Online ISBN: 978-3-540-36478-8

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation