Home

More Papers

Methods for Solving the Capital Allocation Problem

Printable version

A difficulty of the zero-one integer programming formulation of the capital budgeting problem is that, while it is relatively easy to express mathematically, it is difficult to solve. The number of possible solutions grows very fast (in an exponential fashion) with the number of decision variables. In the basic formulation where there are only two alternatives for each project (fund and not fund). if there are N projects, then there are 2^N potential solutions (including the possibility of doing none of the projects). With 30 projects, for example, there are over 1 billion alternative project portfolios. If we consider more alternatives for each project, say m₁ ways of doing the first project, m₂ ways of doing the second project, etc., then the number of possible solutions is (m₁+1)×(m₂+1)×...(m_N+1). If there were two ways of doing each of the 30 projects, for example, there are more than 200 trillion possibilities to consider. It is only recently, with the advent of powerful desk-top and portable computers, that solving real-world capital allocation problems has become practical. Even now, unless we are dealing with situations involving only a few projects, it is not possible to solve the problem by simply trying all possibilities. More efficient solution methods are needed.

There are three common methods for solving the capital allocation problem: ranking, linear programming, and integer programming. To illustrate, we will use the simplified example introduced above. To review, we have $10,000 to spend on a subset of the following 4 projects:

The optimal allocation is the solution to:

.

Ranking Projects by Benefit/Cost Ratios

The easiest way of “solving” the capital allocation problem is to rank the projects by benefit-cost ratio (b_i/c_i) and then to fund the projects from the top down until the budget is exhausted. Provided that there are no project interdependencies (including mutual exclusivities), this approach often gives a reasonable solution. However, (as will be illustrated below) the solution is only approximate (even when there are no project interdependencies) and typically fails to use the entire budget.

For the example, the project ranking based on benefit/cost ratios is:

Based on ranking, the solution is to choose projects 1 and 3 for a total benefit of $13,571. Note that with this solution $10,000 - $8,571 = $1,429 of the budget is unspent.

Linear Programming Solution

If we ignore the integer constraints and require only that the decision variables lie between zero and one, the problem becomes a linear program:

.

This reformulation can be easily solved using linear programming software (or by hand using the Simplex Method). The optimal solution is:

x₁ = 1, x₂ = 0.5, x₃ = 1, x₄ = 0

which gives a total benefit of $15,714.

The linear programming solution, of course, is not feasible. It is not possible to get half the benefit from project 2 by giving it half its required funding. However, based on “rounding”, the solution obtained ignoring the zero-one constraints appears to add credence to the solution derived using ranking.

Since linear programs can quickly solve even very large problems, the technique may appear attractive for capital budgeting. However, unless there are multiple, more complicated (non-integer) constraints that must be satisfied, linear programming provides little beyond the simpler approach based on ranking. Also, even if some of the optimal values of the variables in the linear programming solution are integers, those values may not be very close to the correct solution. Linear programming solutions should be reserved for problems with multiple constraints (e.g., people and dollar constraints, different funds for different kinds of projects, multi-period constraints) that are so large that the more exact methods (such as integer programming) won't work.

Integer Programming Solution

As with linear programming, software packages are available for solving integer programming problems. However, requiring variables to be integer makes the solution much more difficult. Most software packages for integer programming are based on the solution method known as “branch and bound.”

Branch and bound solves the integer programming problem by creating a series of sub-problems that relax the integer constraints. Each sub problem is solved using linear programming. Eventually, a solution is found that maximizes the objective function while satisfying the integer constraints.

To illustrate using the example, branch and bound would begin by solving:

.

As we saw above, the solution is:

x₁ = 1, x₂ = 0.5, x₃ = 1, x₄ = 0

and the resulting benefit value is $15,714.

Since the solution is not purely integer, we have not solved the zero-one programming problem. Therefore, branch and bound creates two new sub-problems by "branching" on the non-integer variable x₂. Specifically, we define a sub-problem with x₂ set to zero:

Sub-Problem 1A

.

and a sub-problem with x₂ set to one:

Sub-Problem 1B

.

Based on the solution to the original, relaxed problem, we know that the integer solutions to each of these problems must have a value less than or equal to the upper "bound" of $15,714.

Branch and bound now proceeds to solve each of these sub-problems using linear programming. If the optimal solution to either is (coincidentally) integer, it is an optimal solution to the sub-problem, and the value can be used to terminate searches of all other sub-problems whose upper bounds are lower. If the solution is not integer, we must create two new sub-problems by again branching on the non-integer variable.

The solutions to the above sub-problems are:

Sub-Problem 1A: x₂ = 0

x₁ = 1, x₂ = 0, x₃ = 1, x₄ = 0.667

(Non-integer)

Benefit: $15,476.

Sub-Problem 1B: x₂ = 1

x₁ = 1, x₂ = 1, x₃ = 0.714, x₄ = 0

(Non-integer)

Benefit: $15,610.

Since neither solution is integer, both problems are “active”, and we must continue branching. The next step would be to define sub-problems to 1B (since it yielded a solution with a higher benefit). Sub-problem 2BA would have the additional constraint that x₃ = 0 and sub-problem 2BB would have the additional constraint that x₃ = 1. Each of these sub-problems is solved to see if they remain active. A sub-problem does not become inactive until either all variables in the solution are integer or there is no feasible solution to it. The branch and bound process continues until there are no remaining sub-problems that are still active.

Continuing to branch and bound, the example eventually yields the solution:

x₁ = 0, x₂ = 1, x₃ = 1, x₄ = 1

which provides a total benefit of $15,000. Notice that this solution yields a higher total benefit than the solution provided by ranking or the feasible solution derived by rounding the linear programming solution. The fact that the simpler approaches did not yield the optimal solution illustrates the dangers of relying on approximate methods.

As illustrated by the above, the limitation of the branch and bound method is that it requires testing many combinations of specific integer values for the variables, and each combination requires the solution of a "normal" optimization problem. Thus, the number of possibilities increases exponentially with the number of decision variables (projects) that must be evaluated. This is a serious problem. Even with sophisticated integer programming software packages and modern supercomputers, if there are more than just a few hundred projects, it is often impossible to solve the problem using integer programming.

Choosing a Solution Method

Of the three basic solution approaches, ranking by benefit-to-cost ratio is usually the best choice for capital allocation when projects are independent with only one budget constraint. Although the solution is only approximate, if there are many projects such that the most costly projects make up only a small fraction of the budget, the result from ranking will be very close to optimal even for budgets that fall between the cumulative costs generated by the ranked list. Ranking is intuitive and less complicated than the other approaches. Furthermore, although not described here, the ranking approach can be modified to account for project interdependencies. Linear programming solutions are best when there are multiple constraints that must be satisfied and the problem is too large to be solved using integer programming. Integer programming gives the most accurate solution, but the slow solution speed and large memory requirements imposed may not be worth the added accuracy.

A Mathematical Model of the Capital Allocation Problem