Branch and Bound Algorithm
Exhaustive Enumeration
(完全枚举法)
Knapsack problem (背包问题)
where c i is the benefit obtained if item i is chon, b is the amount of an available resource, and a i is the amount of the available resource ud by item i.
Exhaustive enumeration is also called Brute-force arch.
The number of possible solutions is 2n, where n is the
number of variables.
Exhaustive Search Tree
•The circles are called nodes, and the lines are called branches. •At the very top of the tree, we have the root node.
•As we descend the tree, decisions are made as indicated by the number on the branches.
• A negative number, -j, implies that the variable x
j has been t
equal to 0, whereas a positive number +j, implies x j has been t equal to 1.
At any node that is not a leaf, some variable, called the paration variable, is fixed at its two possible values at the next level.
The t of solutions at the current node is divided into two mutually exclusive subts by this operation.
Choosing a paration variable and moving to the next level is called branching, becau this is how the branches of the tree are formed.
Branching strategy (i.e., choo a variable for branching) and arch strategy (e.g., depth-first).
Branch and Bound Algorithm
Elementary but important obrvation:
If you solve the LP relaxation of a pure IP and obtain a solution in which all variables are integers, then the optimal solution to the LP relaxation is also the optimal solution to the IP.
The optimal solution to the LP relaxation of this pure IP is
x1=0, x2=6, z=12.
