Specification of Branch-and-Bound Algorithm

To solve the problems of representation and control, we will employ the framework of the branch-and-bound algorithm, which has been used to solve many types of combinatorial optimization problems, in chemical engineering, other domains of engineering, and a broad range of management problems. Specifically, we will use the framework proposed by Ibaraki (1978), which is characterized by the following features ... 

To complete the specification of the algorithm, we require one additional decision parameter how to select the next problem Yix), which we will solve, or equivalently, which node in the branching structure to expand. We will define a search function, s, which allows us to select a node from the currently unexpanded nodes for expansion. In this chapter, as in Ibaraki (1978), we consider only best bound search, where we select the node with the minimum gix) value for expansion. Thus our branch-and-bound algorithm. A, is explicitly specified by... 

A second approach incorporates free energy information into the branch and bound algorithm. Specifically, harmonic entropic contributions are calculated and included at each minima of the upper and lower bounding functions. In this way, the progression of lower and upper bounds includes a temperature-dependent entropic term. A similar modification to the Monte Carlo minimization method has also been proposed [87] and has been shown to be effective in locating low-energy conformers of peptides [88,89]. 

---