3. Filtered Beam Search

Filtered Beam Search (FBS) first proposed in 12 for machine scheduling problems is essentially an approximate Branch and Bound (B&B) method. It partially inherits the power of B&B to search the feasible space systematically while also limiting the computational time. An example of a search tree for our multicasting problem with N = 7, filter width f = 4 and beam width b = 2 is presented in Fig. 1. The root node represents the partial multicast tree with only the source node before any transmission, and the nodes at level 1 represent the possible multicast trees after the source transmits its information. In general, we find the multicast trees after k transmissions at level k of the search tree. Some of these may be infeasible, and the rest are either complete or partial. The key to FBS is the two parameters filter width f and the beam width b. At each level of the tree, we follow a two-stage process to determine which partial multicast trees are likely to provide good solutions when they are completed. First, all nodes corresponding to partial multicast trees are evaluated for their quality by a local evaluation function (LEF) which is called filtering. The best f nodes are considered for a thorough investigation by a global evaluation function (GEF). Among these f nodes the best b are retained in the search tree for beam construction and...