IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v33y1985i4p803-819.html
   My bibliography  Save this article

Solving 0-1 Integer Programming Problems Arising from Large Scale Planning Models

Author

Listed:
  • Ellis L. Johnson

    (IBM Thomas J. Watson Research Center, Yorktown Heights, New York)

  • Michael M. Kostreva

    (GM Research Laboratories, Warren, Michigan)

  • Uwe H. Suhl

    (IBM Thomas J. Watson Research Center, Yorktown Heights, New York)

Abstract

We present methods that are useful in solving some large scale hierarchical planning models involving 0-1 variables. These 0-1 programming problems initially could not be solved with any standard techniques. We employed several approaches to take advantage of the hierarchical structure of variables (ordered by importance) and other structures present in the models. Critical, but not sufficient for success, was a strong linear programming formulation. We describe methods for strengthening the linear programs, as well as other techniques necessary for a commercial branch-and-bound code to be successful in solving these problems.

Suggested Citation

  • 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.
    • Handle: RePEc:inm:oropre:v:33:y:1985:i:4:p:803-819
    DOI: 10.1287/opre.33.4.803
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.33.4.803
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.33.4.803?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
    ---><---

    Citations

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


    Cited by:

    1. Ellis Johnson, 2007. "My experiences as a student and researcher in OR during the 1960’s and 70’s," Annals of Operations Research, Springer, vol. 149(1), pages 121-135, February.
    2. 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.
    3. 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.
    4. Bertsimas, Dimitris & Orlin, James B., 1953-., 1991. "A technique for speeding up the solution of the Lagrangean dual," Working papers 3278-91., Massachusetts Institute of Technology (MIT), Sloan School of Management.
    5. Monique Guignard & Ellis Johnson & Kurt Spielberg, 2005. "Logical Processing for Integer Programming," Annals of Operations Research, Springer, vol. 140(1), pages 263-304, November.
    6. Xiangyong Li & Y. P. Aneja, 2012. "A Branch-and-Cut Approach for the Minimum-Energy Broadcasting Problem in Wireless Networks," INFORMS Journal on Computing, INFORMS, vol. 24(3), pages 443-456, August.
    7. Bagloee, Saeed Asadi & Asadi, Mohsen, 2015. "Prioritizing road extension projects with interdependent benefits under time constraint," Transportation Research Part A: Policy and Practice, Elsevier, vol. 75(C), pages 196-216.
    8. 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.
    9. W. Ogryczak & K. Zorychta, 1996. "Modular Optimizer for Mixed Integer Programming MOMIP Version 2.3," Working Papers wp96106, International Institute for Applied Systems Analysis.
    10. L Virirakis, 1993. "The “Continuous Search Space Design Method†(CSSDM)," Environment and Planning B, , vol. 20(6), pages 617-643, December.
    11. Alves, Maria Joao & Climaco, Joao, 1999. "Using cutting planes in an interactive reference point approach for multiobjective integer linear programming problems," European Journal of Operational Research, Elsevier, vol. 117(3), pages 565-577, September.
    12. W. Ogryczak & K. Zorychta, 1994. "Modular Optimizer for Mixed Integer Programming MOMIP Version 2.1," Working Papers wp94035, International Institute for Applied Systems Analysis.

    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:inm:oropre:v:33:y:1985:i:4:p:803-819. 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.

    We have no bibliographic references for this item. You can help adding them by using 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: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    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.