The Branch-and-Bound Strategy

For a detailed analysis the reader is referred to the work of Arkun (20). The branch and bound strategy indicates that only two control sequences will be of interest to retain and examine further Sequence F0 F F and FQ F2 F (Figure 4). 

The solution to (3-111) is given by x = 4, yx = 1, t/2 = 1, t/3 = 0, and Z = 7. Here we use a depth-first strategy and branch on the variables closest to 0 or 1. Fig. 3-61 shows the progress of the branch and bound algorithm as the binary variables are selected and the bounds are updated. The sequence numbers for each node in Fig. 3-61 show the order in which they are processed. The grayed partitions correspond to the deleted nodes, and at termination of the algorithm we see that Z = 7 and an integer solution is obtained at an intermediate node where coincidentally y3 = 0. 

You can now see why for line A a branch-and-bound technique is not required to solve the design problem. Because of the way the objective function is formulated, if the ratio (pd ps) = 1, the term involving compressor i vanishes from the first summation in the objective function. This outcome is equivalent to the deletion of compressor i in the execution of a branch-and-bound strategy. (Of course the pipeline segments joined at node i may be of different diameters.) But when... 

Westerberg, A.W. and Stephanopoulos, G., "Studies in Process Synthesis—I. Branch and Bound Strategy with List Techniques for the Synthesis of Separation Schemes," Chemical Engineering Science, Vol. 30, pp 963-972, 1975. 

Jonsson J, Shin KG (1997) A parametrized branch-and-bound strategy for scheduling precedence-constrained tasks on a multiprocessor system. In Proceedings of the international conference on parallel processing, Bloomington, IL, USA, 11-15 August 1997, pp 158-165... 

Dead-end elimination. Frequently, the optimization of discretized problems will require a combinatorially large number of evaluations. In this case, whether the problem is computable at all will often depend on whether an efficient branch-and-bound strategy can be implemented. The optimization of sidechain interactions in a protein is a good example. The dead-end elimination theorem shows that it can be efficiently bounded, if one approximates the protein to consist of a set of interacting amino acids with discrete sidechain rotamer states and a fixed backbone. Then its potential energy can be written as... 

The success of any method using this fonnalism will be entirely dependent on the function/used and the search strategy. Lathrop et al. [19] use a branch-and-bound algo-... 

It fix) and g(x) are nonconvex, additional difficulties can occur. In this case, nonunique, local solutions can be obtained at intermediate nodes, and consequently lower bounding properties would be lost. In addition, the nonconvexity in g(x) can lead to locally infeasible problems at intermediate nodes, even if feasible solutions can be found in the corresponding leaf node. To overcome problems with nonconvexities, global solutions to relaxed NLPs can be solved at the intermediate nodes. This preserves the lower bounding information and allows nonlinear branch and bound to inherit the convergence properties from the linear case. However, as noted above, this leads to much more expensive solution strategies. 

---