3.2. The Capital Budgeting Problem (Problem
II)
69
successfully employed to find a solution. The essence of the strategy of the
algorithm is to (1) decompose Problem I into the set of all feasible combinations (termed Problem II), and (2) consider the economic return for
each combination (termed Problem III). The combination of (1) and (2)
with the best return is necessarily the optimum solution for Problem I.
Problem II is a capital budgeting (CB) problem and is concerned with
the allocation of capital among the new dams to be built. Problem II can be
stated as follows:
Maximize the objective function of Problem I subject to constraints
(2.2)-(2.6) of Problem I.
Problem III is an operational policy (OP) problem and is concerned
with the allocation and flow of water. Problem III can be stated as follows:
Maximize the revenue Χ;,·* in Eq. (2.7) of Problem I for all j, j = 1,
2,. . . , M, subject to constraints (2.8)-(2.17) of Problem I.
The two problems are interconnected because Χφ in the CB problem is
determined only by obtaining the optimal solution of the OP problem, and
the total number of dams in the OP problem is the optimal solution of the
CB problem (see Fig. 3.1). We shall examine methods of solving Problems
II and III separately.
3.2. The Capital Budgeting Problem (Problem II)
The CB problem is solved by using a branch and bound algorithm. Before describing the algorithm itself, a few remarks are pertinent concerning
the branch and bound method as an optimization technique.
3.2.1. The Branch and Bound Method As an Optimization
Tool
In optimization a branch and bound algorithm (BBA) comprises a
heuristically structured search of the space of all feasible solutions. A number of BBA's have been proposed to solve a wide variety of combinatorial
problems [Golamb and Baumert, 1965; Little et al, 1963]. Hillier and
Lieberman [1967, pp. 565-570] provide a brief, simple summary of the
technique. By combinatorial problem we mean an optimization problem
that has some objective function /(x) to be minimized or maximized subject to a set of constraints, with the extremum to be established by the
assignment of values to the set of variables x. Considerable flexibility exists
in both the nature of the objective function and the constraints. Combinatorial problems with nonlinear, discontinuous, discrete, and even nonmathematically defined objective functions can be solved as long as /(x)
II)
69
successfully employed to find a solution. The essence of the strategy of the
algorithm is to (1) decompose Problem I into the set of all feasible combinations (termed Problem II), and (2) consider the economic return for
each combination (termed Problem III). The combination of (1) and (2)
with the best return is necessarily the optimum solution for Problem I.
Problem II is a capital budgeting (CB) problem and is concerned with
the allocation of capital among the new dams to be built. Problem II can be
stated as follows:
Maximize the objective function of Problem I subject to constraints
(2.2)-(2.6) of Problem I.
Problem III is an operational policy (OP) problem and is concerned
with the allocation and flow of water. Problem III can be stated as follows:
Maximize the revenue Χ;,·* in Eq. (2.7) of Problem I for all j, j = 1,
2,. . . , M, subject to constraints (2.8)-(2.17) of Problem I.
The two problems are interconnected because Χφ in the CB problem is
determined only by obtaining the optimal solution of the OP problem, and
the total number of dams in the OP problem is the optimal solution of the
CB problem (see Fig. 3.1). We shall examine methods of solving Problems
II and III separately.
3.2. The Capital Budgeting Problem (Problem II)
The CB problem is solved by using a branch and bound algorithm. Before describing the algorithm itself, a few remarks are pertinent concerning
the branch and bound method as an optimization technique.
3.2.1. The Branch and Bound Method As an Optimization
Tool
In optimization a branch and bound algorithm (BBA) comprises a
heuristically structured search of the space of all feasible solutions. A number of BBA's have been proposed to solve a wide variety of combinatorial
problems [Golamb and Baumert, 1965; Little et al, 1963]. Hillier and
Lieberman [1967, pp. 565-570] provide a brief, simple summary of the
technique. By combinatorial problem we mean an optimization problem
that has some objective function /(x) to be minimized or maximized subject to a set of constraints, with the extremum to be established by the
assignment of values to the set of variables x. Considerable flexibility exists
in both the nature of the objective function and the constraints. Combinatorial problems with nonlinear, discontinuous, discrete, and even nonmathematically defined objective functions can be solved as long as /(x)