Computational Experience with Variants of the Balas Algorithm Applied to the Selection of R&D Projects

Allocating funds to independent R&D projects is a problem of practical importance for many firms. We formulate the problem as a 0-1 integer programming problem with the objective of selecting projects that will maximize the anticipated dollar contract volume, yet not exceed cost budgets. Our form-mulation accommodates R&D projects extending over several budget periods and permits carryover of unspent funds from one budget period to later periods. Experience in solving such problems by using the Balas [Balas, Egon. 1965. An additive algorithm for solving linear programs with zero-one variables. Oper. Res.13 (4, July–August) 517–549.] algorithm in its literal form and in reformulated form is summarized. Several other modifications to the algorithm are described and; their effect on efficiency is shown through presentation of computational experience on problems with as many as 50 variables.