A Branch-and-Bound Algorithm for Zero-One Mixed Integer Programming Problems

Ronald E. Davis, David Kendrick and Martin Weitzman
Additional contact information
Ronald E. Davis: Stanford University, Stanford, California

Operations Research, 1971, vol. 19, issue 4, 1036-1044

Abstract: This paper presents the results of experimentation on the development of an efficient branch-and-bound algorithm for the solution of zero-one linear mixed integer programming problems. An implicit enumeration is employed using bounds that are obtained from the fractional variables in the associated linear programming problem. The principal mathematical result used in obtaining these bounds is the piecewise linear convexity of the criterion function with respect to changes of a single variable in the interval [0, 1]. A comparison with the computational experience obtained with several other algorithms on a number of problems is included.

Date: 1971
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.19.4.1036 (application/pdf)

Related works:
Working Paper: A Branch and Bound Algorithm for Zero-One Mixed Integer Programming Problems (1967)
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:oropre:v:19:y:1971:i:4:p:1036-1044

Access Statistics for this article

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