Tree representation for branch and bound

Having developed the representation, the question is how to search for the optimum. One can go through the complete enumeration, but that would involve evaluating each node of the tree. The intelligent way is to reduce the search space by implicit enumeration and evaluate as few nodes as possible. Consider the above example of separation sequencing. The objective is to minimize the cost of separation. If one looks at the nodes for each branch, there are an initial node, intermediate nodes, and a terminal node. Each node is the sum of the costs of aU earher nodes in that branch. Because this cost increases monotonicaUy as we progress through the initial, intermediate, and final nodes, we can define the upper bound and lower bounds for each branch. 

These heuristics allow us to prune the tree. If the cost at the current node is greater than or equal to the upper bormd defined earlier either from one of the prior branches or known to us from experience, then we don t need to go further in that branch. These are the two common ways to prrme the tree based on the order in which the nodes are enumerated  

In Example 5.4, we could carry out the branch and bound method using graphical representation. In real practice, for numerical computation we need algebraic representation of the tree. The following example shows the algebraic representation in terms of binary variables. 

Example 5.5 Provide the algebraic representation of the problem specified in Example 5.3 for the numerical branch-and-bound procedure. 

At the Root Node we can only select one of the three nodes. 

---