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

Cutting plane algorithms for 0-1 programming based on cardinality cuts

Author

Listed:
  • Oguz, Osman

Abstract

We present new valid inequalities for 0-1 programming problems that work in similar ways to well known cover inequalities. Discussion and analysis of these cuts is followed by their revision and use in integer programming as a new generation of cuts that excludes not only portions of polyhedra containing noninteger points, also parts with some integer points that have been explored in search of an optimal solution. Our computational experimentations demonstrate that this new approach has significant potential for solving large scale integer programming problems.

Suggested Citation

  • Oguz, Osman, 2010. "Cutting plane algorithms for 0-1 programming based on cardinality cuts," European Journal of Operational Research, Elsevier, vol. 205(2), pages 273-279, September.
    • Handle: RePEc:eee:ejores:v:205:y:2010:i:2:p:273-279
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377-2217(10)00014-7
    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. Zonghao Gu & George L. Nemhauser & Martin W. P. Savelsbergh, 1999. "Lifted Cover Inequalities for 0-1 Integer Programs: Complexity," INFORMS Journal on Computing, INFORMS, vol. 11(1), pages 117-123, February.
    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. Gérard Cornuéjols & Milind Dawande, 1999. "A Class of Hard Small 0-1 Programs," INFORMS Journal on Computing, INFORMS, vol. 11(2), pages 205-210, May.
    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. Ali, Agha Iqbal & O'Connor, Debra J., 2010. "The impact of distribution system characteristics on computational tractability," European Journal of Operational Research, Elsevier, vol. 200(2), pages 323-333, January.
    2. Domenech, B & Lusa, A, 2016. "A MILP model for the teacher assignment problem considering teachers’ preferences," European Journal of Operational Research, Elsevier, vol. 249(3), pages 1153-1160.
    3. Alper Atamtürk & Laurent Flindt Muller & David Pisinger, 2013. "Separation and Extension of Cover Inequalities for Conic Quadratic Knapsack Constraints with Generalized Upper Bounds," INFORMS Journal on Computing, INFORMS, vol. 25(3), pages 420-431, August.
    4. Nwana, V. & Darby-Dowman, K. & Mitra, G., 2005. "A co-operative parallel heuristic for mixed zero-one linear programming: Combining simulated annealing with branch and bound," European Journal of Operational Research, Elsevier, vol. 164(1), pages 12-23, July.
    5. Diego Klabjan & George L. Nemhauser, 2002. "A Polyhedral Study of Integer Variable Upper Bounds," Mathematics of Operations Research, INFORMS, vol. 27(4), pages 711-739, November.
    6. Heiko Vogel, 2012. "Solving market split problems with heuristical lattice reduction," Annals of Operations Research, Springer, vol. 196(1), pages 581-590, July.
    7. Panton, David & John, Maria & Lucas, Stephen & Mason, Andrew, 2003. "Flight test data cycle map optimisation," European Journal of Operational Research, Elsevier, vol. 146(3), pages 486-497, May.
    8. Yongjia Song & James R. Luedtke & Simge Küçükyavuz, 2014. "Chance-Constrained Binary Packing Problems," INFORMS Journal on Computing, INFORMS, vol. 26(4), pages 735-747, November.
    9. Freville, Arnaud, 2004. "The multidimensional 0-1 knapsack problem: An overview," European Journal of Operational Research, Elsevier, vol. 155(1), pages 1-21, May.
    10. Guidong Zhu & Jonathan F. Bard & Gang Yu, 2006. "A Branch-and-Cut Procedure for the Multimode Resource-Constrained Project-Scheduling Problem," INFORMS Journal on Computing, INFORMS, vol. 18(3), pages 377-390, August.
    11. Bertazzi, Luca & Maggioni, Francesca, 2018. "A stochastic multi-stage fixed charge transportation problem: Worst-case analysis of the rolling horizon approach," European Journal of Operational Research, Elsevier, vol. 267(2), pages 555-569.
    12. Thomas L. Magnanti, 2021. "Optimization: From Its Inception," Management Science, INFORMS, vol. 67(9), pages 5349-5363, September.
    13. Zhan, Junpeng & Ansari, Osama Aslam & Liu, Weijia & Chung, C.Y., 2019. "An accurate bilinear cavern model for compressed air energy storage," Applied Energy, Elsevier, vol. 242(C), pages 752-768.
    14. Manur, Ashray & Venkataramanan, Giri & Sehloff, David, 2018. "Simple electric utility platform: A hardware/software solution for operating emergent microgrids," Applied Energy, Elsevier, vol. 210(C), pages 748-763.
    15. Joni L. Jones & Gary J. Koehler, 2005. "A Heuristic for Winner Determination in Rule-Based Combinatorial Auctions," INFORMS Journal on Computing, INFORMS, vol. 17(4), pages 475-489, November.
    16. Dimitri J. Papageorgiou & Alejandro Toriello & George L. Nemhauser & Martin W. P. Savelsbergh, 2012. "Fixed-Charge Transportation with Product Blending," Transportation Science, INFORMS, vol. 46(2), pages 281-295, May.
    17. Danial Davarnia & Jean-Philippe P. Richard & Ece Içyüz-Ay & Bijan Taslimi, 2019. "Network Models with Unsplittable Node Flows with Application to Unit Train Scheduling," Operations Research, INFORMS, vol. 67(4), pages 1053-1068, July.
    18. Anantaram Balakrishnan & Gang Li & Prakash Mirchandani, 2017. "Optimal Network Design with End-to-End Service Requirements," Operations Research, INFORMS, vol. 65(3), pages 729-750, June.
    19. Gary J. Koehler, 2011. "Minimal Equivalent Binary Knapsack Inequalities," INFORMS Journal on Computing, INFORMS, vol. 23(3), pages 425-429, August.
    20. Aristide Mingozzi & Roberto Roberti, 2018. "An Exact Algorithm for the Fixed Charge Transportation Problem Based on Matching Source and Sink Patterns," Transportation Science, INFORMS, vol. 52(2), pages 229-238, March.

    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:205:y:2010:i:2:p:273-279. 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.