Files
Abstract
As shown by Manne and Vietorisz (1963) investment planning problems involving economies of scale and/or indivisibilities are ccnviently stated as zero-one mixed integer, programming. This paper presents the results of experimentation by Martin Weitzman, Ronald Davis., and the author on the development of an efficient branch and bound algorithm for the solution of zero-one mixed integer programming problems. Two classes of algorithms (which are by no means mutually exclusive) are discussed (1) those for finding optimum solutions and 2) those for finding "good" solutions. The latter class of algorithms are included in the discussion since it is frequently prohibitively expensive to find the optimum solution to such problems and the formulator of the problem is content to have a solution which is with a known percentage of the optimum. Algorithms of the first class which are discussed are (1) Healy (1964), (2) Driebeek (1966) and (3) Davis, Kendrick, and Weitzman (1967). Within the second class two subgroups of - algorithms are discussed; those which provide upper bounds on minimization problems, [(1) Round-off solutions, (2) "Driebeek" round-off solutions, and (3) Kendrick-Weitzman solutions]; and those which provide lower bounds, riiealy solutions].