IDEAS home Printed from https://ideas.repec.org/a/spr/annopr/v139y2005i1p321-35210.1007-s10479-005-3453-y.html
   My bibliography  Save this article

Classical Cuts for Mixed-Integer Programming and Branch-and-Cut

Author

Listed:
  • Manfred Padberg

Abstract

We review classical valid linear inequalities for mixed-integer programming, i.e., Gomory's fractional and mixed-integer cuts, and discuss their use in branch-and-cut. In particular, a generalization of the recent mixed-integer rounding (MIR) inequality and a sufficient condition for the global validity of classical cuts after branching has occurred are derived. Copyright Springer Science + Business Media, Inc. 2005

Suggested Citation

  • Manfred Padberg, 2005. "Classical Cuts for Mixed-Integer Programming and Branch-and-Cut," Annals of Operations Research, Springer, vol. 139(1), pages 321-352, October.
    • Handle: RePEc:spr:annopr:v:139:y:2005:i:1:p:321-352:10.1007/s10479-005-3453-y
    DOI: 10.1007/s10479-005-3453-y
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/10.1007/s10479-005-3453-y
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1007/s10479-005-3453-y?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. POCHET, Yves & WOLSEY, Laurence A., 1988. "Lot-size models with backlogging: strong reformulations and cutting planes," LIDAM Reprints CORE 791, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    2. Laurence A. Wolsey, 1976. "Technical Note—Facets and Strong Valid Inequalities for Integer Programs," Operations Research, INFORMS, vol. 24(2), pages 367-372, April.
    3. Fred Glover, 1968. "A New Foundation for a Simplified Primal Integer Programming Algorithm," Operations Research, INFORMS, vol. 16(4), pages 727-740, August.
    4. Manfred W. Padberg & M. R. Rao, 1982. "Odd Minimum Cut-Sets and b -Matchings," Mathematics of Operations Research, INFORMS, vol. 7(1), pages 67-80, February.
    5. C. A. Trauth, Jr. & R. E. Woolsey, 1969. "Integer Linear Programming: A Study in Computational Efficiency," Management Science, INFORMS, vol. 15(9), pages 481-493, May.
    6. Robert B. Wilson, 1967. "Letter to the Editor—Stronger Cuts in Gomory's All-Integer Integer Programming Algorithm," Operations Research, INFORMS, vol. 15(1), pages 155-157, February.
    7. R. D. Young, 1971. "Hypercylindrically Deduced Cuts in Zero-One Integer Programs," Operations Research, INFORMS, vol. 19(6), pages 1393-1405, October.
    8. T. L. Magnanti & R. Vachani, 1990. "A Strong Cutting Plane Algorithm for Production Scheduling with Changeover Costs," Operations Research, INFORMS, vol. 38(3), pages 456-473, June.
    9. BARANY, Imre & VAN ROY, Tony J. & WOLSEY, Laurence A., 1984. "Strong formulations for multi-item capacitated lot sizing," LIDAM Reprints CORE 590, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    10. M. W. Padberg & T. J. Van Roy & L. A. Wolsey, 1985. "Valid Linear Inequalities for Fixed Charge Problems," Operations Research, INFORMS, vol. 33(4), pages 842-861, August.
    11. CORDIER, Cécile & MARCHAND, Hugues & LAUNDY, Richard & WOLSEY, Laurence A., 1999. "bc-opt: a branch-and-cut code for mixed integer programs," LIDAM Reprints CORE 1431, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    12. Karla L. Hoffman & Manfred Padberg, 1993. "Solving Airline Crew Scheduling Problems by Branch-and-Cut," Management Science, INFORMS, vol. 39(6), pages 657-682, June.
    13. Padberg, M.W. & Van Roy, T.J. & Wolsey, L.A., 1985. "Valid linear inequalities for fixed charge problems," LIDAM Reprints CORE 656, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    14. Harlan Crowder & Manfred W. Padberg, 1980. "Solving Large-Scale Symmetric Travelling Salesman Problems to Optimality," Management Science, INFORMS, vol. 26(5), pages 495-509, May.
    15. A. M. Geoffrion, 1969. "An Improved Implicit Enumeration Approach for Integer Programming," Operations Research, INFORMS, vol. 17(3), pages 437-454, June.
    16. G. Dantzig & R. Fulkerson & S. Johnson, 1954. "Solution of a Large-Scale Traveling-Salesman Problem," Operations Research, INFORMS, vol. 2(4), pages 393-410, November.
    17. D. Chinhyung Cho & Manfred W. Padberg & M. R. Rao, 1983. "On the Uncapacitated Plant Location Problem. II: Facets and Lifting Theorems," Mathematics of Operations Research, INFORMS, vol. 8(4), pages 590-612, November.
    18. CERIA, Sebastian & CORDIER, Cécile & MARCHAND, Hugues & WOLSEY, Laurence A., 1998. "Cutting planes for integer programs with general integer variables," LIDAM Reprints CORE 1334, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    19. Harlan Crowder & Ellis L. Johnson & Manfred Padberg, 1983. "Solving Large-Scale Zero-One Linear Programming Problems," Operations Research, INFORMS, vol. 31(5), pages 803-834, October.
    20. WOLSEY, Laurence A., 1976. "Facets and strong valid inequalities for integer programs," LIDAM Reprints CORE 246, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    21. Karla L. Hoffman & Manfred Padberg, 1991. "Improving LP-Representations of Zero-One Linear Programs for Branch-and-Cut," INFORMS Journal on Computing, INFORMS, vol. 3(2), pages 121-134, May.
    22. A. M. Geoffrion & R. E. Marsten, 1972. "Integer Programming Algorithms: A Framework and State-of-the-Art Survey," Management Science, INFORMS, vol. 18(9), pages 465-491, May.
    23. Egon Balas, 1965. "An Additive Algorithm for Solving Linear Programs with Zero-One Variables," Operations Research, INFORMS, vol. 13(4), pages 517-546, August.
    24. Martin Grötschel & Michael Jünger & Gerhard Reinelt, 1984. "A Cutting Plane Algorithm for the Linear Ordering Problem," Operations Research, INFORMS, vol. 32(6), pages 1195-1220, December.
    25. WOLSEY, Laurence A., 1989. "Strong formulations for mixed integer programming: a survey," LIDAM Reprints CORE 864, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    26. Imre Barany & Tony J. Van Roy & Laurence A. Wolsey, 1984. "Strong Formulations for Multi-Item Capacitated Lot Sizing," Management Science, INFORMS, vol. 30(10), pages 1255-1261, October.
    27. D. Chinhyung Cho & Ellis L. Johnson & Manfred Padberg & M. R. Rao, 1983. "On the Uncapacitated Plant Location Problem. I: Valid Inequalities and Facets," Mathematics of Operations Research, INFORMS, vol. 8(4), pages 579-589, November.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Wassila Drici & Fatma Zohra Ouail & Mustapha Moulaï, 2018. "Optimizing a linear fractional function over the integer efficient set," Annals of Operations Research, Springer, vol. 267(1), pages 135-151, August.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Aardal, K.I. & van Hoesel, S., 1995. "Polyhedral Techniques in Combinatorial Optimization," Other publications TiSEM ed028a07-eb6a-4c8d-8f21-d, Tilburg University, School of Economics and Management.
    2. Ellis L. Johnson & George L. Nemhauser & Martin W.P. Savelsbergh, 2000. "Progress in Linear Programming-Based Algorithms for Integer Programming: An Exposition," INFORMS Journal on Computing, INFORMS, vol. 12(1), pages 2-23, February.
    3. Santanu S. Dey & Jean-Philippe Richard, 2009. "Linear-Programming-Based Lifting and Its Application to Primal Cutting-Plane Algorithms," INFORMS Journal on Computing, INFORMS, vol. 21(1), pages 137-150, February.
    4. Richard Laundy & Michael Perregaard & Gabriel Tavares & Horia Tipi & Alkis Vazacopoulos, 2009. "Solving Hard Mixed-Integer Programming Problems with Xpress-MP: A MIPLIB 2003 Case Study," INFORMS Journal on Computing, INFORMS, vol. 21(2), pages 304-313, May.
    5. Robert E. Bixby & Eva K. Lee, 1998. "Solving a Truck Dispatching Scheduling Problem Using Branch-and-Cut," Operations Research, INFORMS, vol. 46(3), pages 355-367, June.
    6. Quentin Louveaux & Laurence Wolsey, 2007. "Lifting, superadditivity, mixed integer rounding and single node flow sets revisited," Annals of Operations Research, Springer, vol. 153(1), pages 47-77, September.
    7. Hugues Marchand & Laurence A. Wolsey, 2001. "Aggregation and Mixed Integer Rounding to Solve MIPs," Operations Research, INFORMS, vol. 49(3), pages 363-371, June.
    8. Wei-Kun Chen & Liang Chen & Mu-Ming Yang & Yu-Hong Dai, 2018. "Generalized coefficient strengthening cuts for mixed integer programming," Journal of Global Optimization, Springer, vol. 70(1), pages 289-306, January.
    9. Absi, Nabil & Kedad-Sidhoum, Safia, 2008. "The multi-item capacitated lot-sizing problem with setup times and shortage costs," European Journal of Operational Research, Elsevier, vol. 185(3), pages 1351-1374, March.
    10. Zonghao Gu & George L. Nemhauser & Martin W.P. Savelsbergh, 2000. "Sequence Independent Lifting in Mixed Integer Programming," Journal of Combinatorial Optimization, Springer, vol. 4(1), pages 109-129, March.
    11. Doostmohammadi, Mahdi & Akartunalı, Kerem, 2018. "Valid inequalities for two-period relaxations of big-bucket lot-sizing problems: Zero setup case," European Journal of Operational Research, Elsevier, vol. 267(1), pages 86-95.
    12. Aardal, K. & van Hoesel, C.P.M., 1995. "Polyhedral techniques in combinatorial optimization," Research Memorandum 014, Maastricht University, Maastricht Research School of Economics of Technology and Organization (METEOR).
    13. Christopher Hojny & Tristan Gally & Oliver Habeck & Hendrik Lüthen & Frederic Matter & Marc E. Pfetsch & Andreas Schmitt, 2020. "Knapsack polytopes: a survey," Annals of Operations Research, Springer, vol. 292(1), pages 469-517, September.
    14. Mirchandani, Prakash, 2000. "Projections of the capacitated network loading problem," European Journal of Operational Research, Elsevier, vol. 122(3), pages 534-560, May.
    15. Astrid S. Kenyon & David P. Morton, 2003. "Stochastic Vehicle Routing with Random Travel Times," Transportation Science, INFORMS, vol. 37(1), pages 69-82, February.
    16. Jans, Raf & Degraeve, Zeger, 2007. "Meta-heuristics for dynamic lot sizing: A review and comparison of solution approaches," European Journal of Operational Research, Elsevier, vol. 177(3), pages 1855-1875, March.
    17. Robert Bixby & Edward Rothberg, 2007. "Progress in computational mixed integer programming—A look back from the other side of the tipping point," Annals of Operations Research, Springer, vol. 149(1), pages 37-41, February.
    18. Wei-Kun Chen & Liang Chen & Yu-Hong Dai, 2023. "Lifting for the integer knapsack cover polyhedron," Journal of Global Optimization, Springer, vol. 86(1), pages 205-249, May.
    19. Martin Durbin & Karla Hoffman, 2008. "OR PRACTICE---The Dance of the Thirty-Ton Trucks: Dispatching and Scheduling in a Dynamic Environment," Operations Research, INFORMS, vol. 56(1), pages 3-19, February.
    20. Ghosh, Diptesh & Sumanta Basu, 2011. "Diversified Local Search for the Traveling Salesman Problem," IIMA Working Papers WP2011-01-03, Indian Institute of Management Ahmedabad, Research and Publication Department.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:annopr:v:139:y:2005:i:1:p:321-352:10.1007/s10479-005-3453-y. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.