IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v214y2011i1p15-26.html
   My bibliography  Save this article

Pivot-and-reduce cuts: An approach for improving Gomory mixed-integer cuts

Author

Listed:
  • Wesselmann, Franz
  • Koberstein, Achim
  • Suhl, Uwe H.

Abstract

Gomory mixed-integer cuts are of crucial importance in solving large-scale mixed-integer linear programs. Recently, there has been considerable research particularly on the strengthening of these cuts. We present a new heuristic algorithm which aims at improving Gomory mixed-integer cuts. Our approach is related to the reduce-and-split cuts. These cuts are based on an algorithm which tries to reduce the coefficients of the continuous variables by forming integer linear combinations of simplex tableau rows. Our algorithm is designed to achieve the same result by performing pivots on the simplex tableau. We give a detailed description of the algorithm and its implementation. Finally, we report on computational results with our approach and analyze its performance. The results indicate that our algorithm can enhance the performance of the Gomory mixed-integer cuts.

Suggested Citation

  • Wesselmann, Franz & Koberstein, Achim & Suhl, Uwe H., 2011. "Pivot-and-reduce cuts: An approach for improving Gomory mixed-integer cuts," European Journal of Operational Research, Elsevier, vol. 214(1), pages 15-26, October.
    • Handle: RePEc:eee:ejores:v:214:y:2011:i:1:p:15-26
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S037722171100350X
    Download Restriction: Full text for ScienceDirect subscribers only
    ---><---

    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. 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.
    2. Suhl, Uwe H., 1994. "MOPS -- Mathematical optimization system," European Journal of Operational Research, Elsevier, vol. 72(2), pages 312-322, January.
    3. Egon Balas, 1971. "Intersection Cuts—A New Type of Cutting Planes for Integer Programming," Operations Research, INFORMS, vol. 19(1), pages 19-39, February.
    4. Egon Balas & Sebastián Ceria & Gérard Cornuéjols, 1996. "Mixed 0-1 Programming by Lift-and-Project in a Branch-and-Cut Framework," Management Science, INFORMS, vol. 42(9), pages 1229-1246, September.
    5. Kent Andersen & Gérard Cornuéjols & Yanjun Li, 2005. "Reduce-and-Split Cuts: Improving the Performance of Mixed-Integer Gomory Cuts," Management Science, INFORMS, vol. 51(11), pages 1720-1732, November.
    Full references (including those not matched with items on IDEAS)

    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. Egon Balas & Gérard Cornuéjols & Tamás Kis & Giacomo Nannicini, 2013. "Combining Lift-and-Project and Reduce-and-Split," INFORMS Journal on Computing, INFORMS, vol. 25(3), pages 475-487, August.
    2. Santanu S. Dey & Andrea Lodi & Andrea Tramontani & Laurence A. Wolsey, 2014. "On the Practical Strength of Two-Row Tableau Cuts," INFORMS Journal on Computing, INFORMS, vol. 26(2), pages 222-237, May.
    3. Kent Andersen & Gérard Cornuéjols & Yanjun Li, 2005. "Reduce-and-Split Cuts: Improving the Performance of Mixed-Integer Gomory Cuts," Management Science, INFORMS, vol. 51(11), pages 1720-1732, November.
    4. Amitabh Basu & Robert Hildebrand & Matthias Köppe, 2016. "Light on the infinite group relaxation I: foundations and taxonomy," 4OR, Springer, vol. 14(1), pages 1-40, March.
    5. Amitabh Basu & Robert Hildebrand & Matthias Köppe, 2016. "Light on the infinite group relaxation II: sufficient conditions for extremality, sequences, and algorithms," 4OR, Springer, vol. 14(2), pages 107-131, June.
    6. Egon Balas & Sebastián Ceria & Milind Dawande & Francois Margot & Gábor Pataki, 2001. "Octane: A New Heuristic for Pure 0--1 Programs," Operations Research, INFORMS, vol. 49(2), pages 207-225, April.
    7. Meyr, H., 2000. "Simultaneous lotsizing and scheduling by combining local search with dual reoptimization," European Journal of Operational Research, Elsevier, vol. 120(2), pages 311-326, January.
    8. Xiaoyi Gu & Santanu S. Dey & Jean-Philippe P. Richard, 2024. "Solving Sparse Separable Bilinear Programs Using Lifted Bilinear Cover Inequalities," INFORMS Journal on Computing, INFORMS, vol. 36(3), pages 884-899, May.
    9. Amitabh Basu & Gérard Cornuéjols & François Margot, 2012. "Intersection Cuts with Infinite Split Rank," Mathematics of Operations Research, INFORMS, vol. 37(1), pages 21-40, February.
    10. Drexl, Andreas & Nissen, Rudiger & Patterson, James H. & Salewski, Frank, 2000. "ProGen/[pi]x - An instance generator for resource-constrained project scheduling problems with partially renewable resources and further extensions," European Journal of Operational Research, Elsevier, vol. 125(1), pages 59-72, August.
    11. Vipul Jain & Ignacio E. Grossmann, 2001. "Algorithms for Hybrid MILP/CP Models for a Class of Optimization Problems," INFORMS Journal on Computing, INFORMS, vol. 13(4), pages 258-276, November.
    12. Ricardo M. Lima & Ignacio E. Grossmann, 2017. "On the solution of nonconvex cardinality Boolean quadratic programming problems: a computational study," Computational Optimization and Applications, Springer, vol. 66(1), pages 1-37, January.
    13. Amitabh Basu & Pierre Bonami & Gérard Cornuéjols & François Margot, 2011. "Experiments with Two-Row Cuts from Degenerate Tableaux," INFORMS Journal on Computing, INFORMS, vol. 23(4), pages 578-590, November.
    14. Eva K. Lee, 2004. "Generating Cutting Planes for Mixed Integer Programming Problems in a Parallel Computing Environment," INFORMS Journal on Computing, INFORMS, vol. 16(1), pages 3-26, February.
    15. Shyam S. G. Perumal & Jesper Larsen & Richard M. Lusby & Morten Riis & Tue R. L. Christensen, 2022. "A column generation approach for the driver scheduling problem with staff cars," Public Transport, Springer, vol. 14(3), pages 705-738, October.
    16. André R. S. Amaral, 2008. "An Exact Approach to the One-Dimensional Facility Layout Problem," Operations Research, INFORMS, vol. 56(4), pages 1026-1033, August.
    17. Amaro Sousa & Carlos Borges Lopes & Paulo Monteiro, 2016. "Compact ILP formulations for the routing and wavelength assignment problem in the design of optical transport networks with regenerators," EURO Journal on Computational Optimization, Springer;EURO - The Association of European Operational Research Societies, vol. 4(2), pages 189-213, May.
    18. Gennadiy Averkov & Christian Wagner & Robert Weismantel, 2011. "Maximal Lattice-Free Polyhedra: Finiteness and an Explicit Description in Dimension Three," Mathematics of Operations Research, INFORMS, vol. 36(4), pages 721-742, November.
    19. Roger Rocha & Ignacio Grossmann & Marcus Poggi de Aragão, 2013. "Cascading Knapsack Inequalities: reformulation of a crude oil distribution problem," Annals of Operations Research, Springer, vol. 203(1), pages 217-234, March.
    20. Valentin Borozan & Gérard Cornuéjols, 2009. "Minimal Valid Inequalities for Integer Constraints," Mathematics of Operations Research, INFORMS, vol. 34(3), pages 538-546, August.

    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:eee:ejores:v:214:y:2011:i:1:p:15-26. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    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.