3.2. The Capital Budgeting Problem (Problem II)
71
Because the set of all feasible combinations termed Problem II in Section
3.1 includes aspects of both The Traveling Salesman Problem and The
Knapsack Problem, the latter problem is also of interest.
The Knapsack Problem
The Knapsack Problem has two different aspects: (1) if a given space is
to be packed with items of different value and volume, the objective is to
choose the most valuable packing; or (2) if a given item is to be divided
into portions of different value, the objective is to find the most valuable
division of the item. A formal statement of the problem is
Maximize
η
/(*) = Σ<Ν*Ν
i
subject to
η
L
Z/={0, 1}
i
The ay are positive numbers; the 6y and L are positive integers.
Other examples of branch and bound problems are plant location
[Efroymson and Ray, 1965; Davis and Ray, 1969] and mixed integer linear
programming [Land and Doig, I960].
In essence the procedure in a BBA is to repeatedly partition the space of
all the feasible solutions into smaller and smaller subsets. An upper bound
in the case of maximization (or lower bound for minimization) is computed
for the value of the objective function for each subset. The partitioning,
also termed branching, is carried out so that the subsets are mutually exclusive and each feasible solution belongs to only one subset. After the
initial branching, branching is continued, but those subsets with an upper
bound that is less than the bound of a known feasible solution are not
partitioned any further and are excluded from further consideration. Otherwise, branching continues repeatedly until a feasible solution is obtained
that has a value for the objective function greater than the upper bounds
of all the other remaining subsets. The branch and bound method solves a
difficult problem by using well known techniques to solve a series of easier
problems.
To see how this decomposition takes place, suppose that we want to
solve the following problem.
71
Because the set of all feasible combinations termed Problem II in Section
3.1 includes aspects of both The Traveling Salesman Problem and The
Knapsack Problem, the latter problem is also of interest.
The Knapsack Problem
The Knapsack Problem has two different aspects: (1) if a given space is
to be packed with items of different value and volume, the objective is to
choose the most valuable packing; or (2) if a given item is to be divided
into portions of different value, the objective is to find the most valuable
division of the item. A formal statement of the problem is
Maximize
η
/(*) = Σ<Ν*Ν
i
subject to
η
L
Z/={0, 1}
i
The ay are positive numbers; the 6y and L are positive integers.
Other examples of branch and bound problems are plant location
[Efroymson and Ray, 1965; Davis and Ray, 1969] and mixed integer linear
programming [Land and Doig, I960].
In essence the procedure in a BBA is to repeatedly partition the space of
all the feasible solutions into smaller and smaller subsets. An upper bound
in the case of maximization (or lower bound for minimization) is computed
for the value of the objective function for each subset. The partitioning,
also termed branching, is carried out so that the subsets are mutually exclusive and each feasible solution belongs to only one subset. After the
initial branching, branching is continued, but those subsets with an upper
bound that is less than the bound of a known feasible solution are not
partitioned any further and are excluded from further consideration. Otherwise, branching continues repeatedly until a feasible solution is obtained
that has a value for the objective function greater than the upper bounds
of all the other remaining subsets. The branch and bound method solves a
difficult problem by using well known techniques to solve a series of easier
problems.
To see how this decomposition takes place, suppose that we want to
solve the following problem.