Heuristic Algorithms for Capital Budgeting Decisions in Multi-Division Firms

By Meir J. RosenblattJames R. Freeland
1977| Working Paper No. 369

This paper presents two versions of a heuristic algorithm to solve a model of the capital budgeting problem in a multi-division firm. These algorithms allow a final allocation of the budget to projects to be found in two information exchanges between the divisions and headquarters. Headquarters need not have detailed information about the projects facing each division. The algorithms a reinitiated with divisions sending headquarters information about the amount of money needed in each of the budgeting periods and what cash flow they can generate given the requested allocation , Headquarters then uses this information about cash demand and potential growth rate of each division to get an initial budget allocation for each division. These budgets, with some variations, are used by each division to solve a linear programming problem. Each division, then, submits a proposal which consists of the integer part and the fractional part of the linear programming solution. Optimizing the overall horizon value, headquarters makes the final allocation. To test these algorithms a simulation program was developed. This program generates random cash flows and compares the solution achieved using this algorithm with an overall centralized solution. The centralized solution is a linear one and thus serves as an upper bound on the centralized integer solution (which is an upper bound on the decentralized integer solution). Thus, the algorithm which results in a decentralized integer solution is compared with a centralized linear solution. More than a thousand examples are solved, resulting in a average relative error of less than 1%.