IDEAS home Printed from https://ideas.repec.org/a/spr/annopr/v140y2005i1p263-30410.1007-s10479-005-3974-4.html
   My bibliography  Save this article

Logical Processing for Integer Programming

Author

Listed:
  • Monique Guignard

  • Ellis Johnson

  • Kurt Spielberg

Abstract

This paper reviews tools which have great potential for reducing the difficulty of solving IP (and also MIP) problems, if well implemented in solvers. Recent experiments with Branch and Bound solvers, in connection with “Short Start Features”, have shown that implementations need and can still be improved. Concepts which are likely to be specially important for (0,1) MIP are pointed out. Copyright Springer Science + Business Media, Inc. 2005

Suggested Citation

  • Monique Guignard & Ellis Johnson & Kurt Spielberg, 2005. "Logical Processing for Integer Programming," Annals of Operations Research, Springer, vol. 140(1), pages 263-304, November.
    • Handle: RePEc:spr:annopr:v:140:y:2005:i:1:p:263-304:10.1007/s10479-005-3974-4
    DOI: 10.1007/s10479-005-3974-4
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/10.1007/s10479-005-3974-4
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1007/s10479-005-3974-4?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

    for a different version of it.

    References listed on IDEAS

    as
    1. C. E. Lemke & H. M. Salkin & K. Spielberg, 1971. "Set Covering by Single-Branch Enumeration with Linear-Programming Subproblems," Operations Research, INFORMS, vol. 19(4), pages 998-1022, August.
    2. Carlton E. Lemke & Kurt Spielberg, 1967. "Direct Search Algorithms for Zero-One and Mixed-Integer Programming," Operations Research, INFORMS, vol. 15(5), pages 892-914, October.
    3. Michel L. Balinski, 1961. "Fixed‐cost transportation problems," Naval Research Logistics Quarterly, John Wiley & Sons, vol. 8(1), pages 41-54, March.
    4. R. Lougee-Heimer & W. Adams, 2005. "A Conditional Logic Approach for Strengthening Mixed 0-1 Linear Programs," Annals of Operations Research, Springer, vol. 139(1), pages 289-320, October.
    5. 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.
    6. Ellis L. Johnson & Michael M. Kostreva & Uwe H. Suhl, 1985. "Solving 0-1 Integer Programming Problems Arising from Large Scale Planning Models," Operations Research, INFORMS, vol. 33(4), pages 803-819, August.
    7. Fisher, M.L. & Nemhauser, G.L. & Wolsey, L.A., 1978. "An analysis of approximations for maximizing submodular set functions," LIDAM Reprints CORE 341, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    8. Fred Glover, 1971. "A Note on Extreme-Point Solutions and A Paper by Lemke, Salkin, and Spielberg," Operations Research, INFORMS, vol. 19(4), pages 1023-1025, August.
    9. Egon Balas, 1965. "An Additive Algorithm for Solving Linear Programs with Zero-One Variables," Operations Research, INFORMS, vol. 13(4), pages 517-546, August.
    10. Michel Balinski, 2010. "Integer Programming: Methods, Uses, Computation," Springer Books, in: Michael Jünger & Thomas M. Liebling & Denis Naddef & George L. Nemhauser & William R. Pulleyblank & (ed.), 50 Years of Integer Programming 1958-2008, chapter 0, pages 133-197, Springer.
    11. Fisher, M.L. & Nemhauser, G.L. & Wolsey, L.A., 1978. "An analysis of approximations for maximizing submodular set functions - 1," LIDAM Reprints CORE 334, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    12. Michel Balinski, 2010. "Integer Programming: Methods, Uses, Computation," Springer Books, in: Michael Jünger & Thomas M. Liebling & Denis Naddef & George L. Nemhauser & William R. Pulleyblank & (ed.), 50 Years of Integer Programming 1958-2008, chapter 0, pages 133-197, Springer.
    13. Fred Glover, 1965. "A Multiphase-Dual Algorithm for the Zero-One Integer Programming Problem," Operations Research, INFORMS, vol. 13(6), pages 879-919, December.
    14. Guignard, Monique & Ryu, Choonho & Spielberg, Kurt, 1998. "Model tightening for integrated timber harvest and transportation planning," European Journal of Operational Research, Elsevier, vol. 111(3), pages 448-460, December.
    15. Kurt Spielberg, 1969. "Algorithms for the Simple Plant-Location Problem with Some Side Conditions," Operations Research, INFORMS, vol. 17(1), pages 85-111, February.
    16. Jerrold Rubin, 1973. "A Technique for the Solution of Massive Set Covering Problems, with Application to Airline Crew Scheduling," Transportation Science, INFORMS, vol. 7(1), pages 34-48, February.
    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. L. Foulds & B. Toklu & J. Wilson, 2009. "Modelling either-or relations in integer programming," Annals of Operations Research, Springer, vol. 166(1), pages 203-222, February.
    2. repec:ehu:biltok:5576 is not listed 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. Kurt Spielberg, 2007. "IP over 40+ Years at IBM Scientific Centers and Marketing," Annals of Operations Research, Springer, vol. 149(1), pages 195-208, February.
    2. Harkness, Joseph & ReVelle, Charles, 2003. "Facility location with increasing production costs," European Journal of Operational Research, Elsevier, vol. 145(1), pages 1-13, February.
    3. 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.
    4. Thomas L. Magnanti, 2021. "Optimization: From Its Inception," Management Science, INFORMS, vol. 67(9), pages 5349-5363, September.
    5. Pierre Hansen & Jack Brimberg & Dragan Urošević & Nenad Mladenović, 2007. "Primal-Dual Variable Neighborhood Search for the Simple Plant-Location Problem," INFORMS Journal on Computing, INFORMS, vol. 19(4), pages 552-564, November.
    6. 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.
    7. R. Lougee-Heimer & W. Adams, 2005. "A Conditional Logic Approach for Strengthening Mixed 0-1 Linear Programs," Annals of Operations Research, Springer, vol. 139(1), pages 289-320, October.
    8. Sarin, Subhash C. & Aggarwal, Sanjay, 2001. "Modeling and algorithmic development of a staff scheduling problem," European Journal of Operational Research, Elsevier, vol. 128(3), pages 558-569, February.
    9. U. Seppaelae, 1997. "An Evolutionary Model for Spatial Location of Economic Facilities," Working Papers ir97003, International Institute for Applied Systems Analysis.
    10. Dam, Tien Thanh & Ta, Thuy Anh & Mai, Tien, 2022. "Submodularity and local search approaches for maximum capture problems under generalized extreme value models," European Journal of Operational Research, Elsevier, vol. 300(3), pages 953-965.
    11. Beck, Yasmine & Ljubić, Ivana & Schmidt, Martin, 2023. "A survey on bilevel optimization under uncertainty," European Journal of Operational Research, Elsevier, vol. 311(2), pages 401-426.
    12. Guanyi Wang, 2024. "Robust Network Targeting with Multiple Nash Equilibria," Papers 2410.20860, arXiv.org, revised Nov 2024.
    13. Jiaming Hu & Dachuan Xu & Donglei Du & Cuixia Miao, 2024. "Differentially private submodular maximization with a cardinality constraint over the integer lattice," Journal of Combinatorial Optimization, Springer, vol. 47(4), pages 1-24, May.
    14. Rad Niazadeh & Negin Golrezaei & Joshua Wang & Fransisca Susan & Ashwinkumar Badanidiyuru, 2023. "Online Learning via Offline Greedy Algorithms: Applications in Market Design and Optimization," Management Science, INFORMS, vol. 69(7), pages 3797-3817, July.
    15. Emelogu, Adindu & Chowdhury, Sudipta & Marufuzzaman, Mohammad & Bian, Linkan & Eksioglu, Burak, 2016. "An enhanced sample average approximation method for stochastic optimization," International Journal of Production Economics, Elsevier, vol. 182(C), pages 230-252.
    16. Michel Le Breton & Juan Moreno-Ternero & Alexei Savvateev & Shlomo Weber, 2013. "Stability and fairness in models with a multiple membership," International Journal of Game Theory, Springer;Game Theory Society, vol. 42(3), pages 673-694, August.
    17. Alexandre D. Jesus & Luís Paquete & Arnaud Liefooghe, 2021. "A model of anytime algorithm performance for bi-objective optimization," Journal of Global Optimization, Springer, vol. 79(2), pages 329-350, February.
    18. 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.
    19. Bin Liu & Miaomiao Hu, 2022. "Fast algorithms for maximizing monotone nonsubmodular functions," Journal of Combinatorial Optimization, Springer, vol. 43(5), pages 1655-1670, July.
    20. repec:dgr:rugsom:99a17 is not listed on IDEAS
    21. Monabbati, Ehsan & Kakhki, Hossein Taghizadeh, 2015. "On a class of subadditive duals for the uncapacitated facility location problem," Applied Mathematics and Computation, Elsevier, vol. 251(C), pages 118-131.

    More about this item

    Keywords

    ;
    ;
    ;
    ;
    ;
    ;
    ;
    ;
    ;

    Statistics

    Access and download statistics

    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:140:y:2005:i:1:p:263-304:10.1007/s10479-005-3974-4. 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.