Practical Solution of Large Mixed Integer Programming Problems with Umpire

J. J. H. Forrest, J. P. H. Hirst and J. A. Tomlin
Additional contact information
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

Management Science, 1974, vol. 20, issue 5, 736-773

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.

Date: 1974
References: Add references at CitEc
Citations: View citations in EconPapers (8)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.20.5.736 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormnsc:v:20:y:1974:i:5:p:736-773

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().