Advanced Search
MyIDEAS: Login

Practical Solution of Large Mixed Integer Programming Problems with Umpire

Contents:

Author Info

  • J. J. H. Forrest

    (Scicon Ltd., London, England)

  • J. P. H. Hirst

    (British Petroleum Co. Ltd., London, England)

  • J. A. Tomlin

    (Presently affiliated with Stanford University)

Registered author(s):

    Abstract

    In this paper we discuss some branch and bound methods implemented in the UMPIRE mathematical programming system for solving practical integer programming problems and give details of computational experience with these methods. We have found that the nontrivial integer programming problems we encounter tend to fall into two classes. The first class of problems is characterized by a relatively small number (less than 100) of binary integer variables embedded in a very large and difficult linear program, with a few thousand constraints and complex matrix structure. The second class of problems tends to have many more integer variables (perhaps several hundred), frequently organized into special ordered sets and expressing complex logical relationships, but embedded in a much simpler linear program with 500-1,000 constraints. Problems in the first group in particular do not generally behave well using a simple-minded "penalty" approach for reasons we will make clear and a number of heuristic estimation procedures are used to guide the branch and bound search. The most important devices used are "priorities," the "best projection criterion" and "pseudo-costs." Some or all of these heuristics can also be very useful in tackling the second group of problems, where it is important to reach a good solution quickly to limit the search.

    Download Info

    If you experience problems downloading a file, check if you have the proper application to view it first. In case of further problems read the IDEAS help page. Note that these files are not on the IDEAS site. Please be patient as the files may be large.
    File URL: http://dx.doi.org/10.1287/mnsc.20.5.736
    Download Restriction: no

    Bibliographic Info

    Article provided by INFORMS in its journal Management Science.

    Volume (Year): 20 (1974)
    Issue (Month): 5 (January)
    Pages: 736-773

    as in new window
    Handle: RePEc:inm:ormnsc:v:20:y:1974:i:5:p:736-773

    Contact details of provider:
    Postal: 7240 Parkway Drive, Suite 300, Hanover, MD 21076 USA
    Phone: +1-443-757-3500
    Fax: 443-757-3515
    Email:
    Web page: http://www.informs.org/
    More information through EDIRC

    Related research

    Keywords:

    References

    No references listed on IDEAS
    You can help add them by filling out this form.

    Citations

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

    Cited by:
    1. W. Ogryczak & K. Zorychta, 1996. "Modular Optimizer for Mixed Integer Programming MOMIP Version 2.3," Working Papers wp96106, International Institute for Applied Systems Analysis.
    2. W. Ogryczak & K. Zorychta, 1994. "Modular Optimizer for Mixed Integer Programming MOMIP Version 2.1," Working Papers wp94035, International Institute for Applied Systems Analysis.

    Lists

    This item is not listed on Wikipedia, on a reading list or among the top items on IDEAS.

    Statistics

    Access and download statistics

    Corrections

    When requesting a correction, please mention this item's handle: RePEc:inm:ormnsc:v:20:y:1974:i:5:p:736-773. See general information about how to correct material in RePEc.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Mirko Janc).

    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 references are entirely missing, you can add them using this form.

    If the full references list an item that is present in RePEc, but the system did not link 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 profile, as there may be some citations waiting for confirmation.

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