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

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.