Branch and bound

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-... 

Finally, having set up the learning problem, we need to employ a learning method that will guarantee preservation of the correctness of the branch-and-bound algorithm and make useful additions to the control information we have about the problem (Section V). 

The flowshop problem has been widely studied in the fields of both operations research (Lagweg et al., 1978 Baker, 1975) and chemical engineering (Rajagopalan and Karimi, 1989 Wiede and Reklaitis, 1987). Since the purpose of this chapter is to illustrate a novel technique to synthesize new control knowledge for branch-and-bound algorithms, we... 

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 ... 

The next section will highlight these features of the branch-and-bound framework, within the context of the flowshop scheduling problem. Then we will give an abstract description of the algorithm, followed by the... 

The large size of the solution space for combinatorial optimization problems forces us to represent it implicitly. The branch-and-bound algorithm encodes the entire solution space in a root node, which is successively expanded into branching nodes. Each of these nodes represents a subset of the original solution space specialized to contain some particular element of the problem structure. 

Having formally defined the branching structure, we must now make explicit the mechanisms by which we can eliminate subsets of the solution space from further consideration. Ibaraki (1978) has stated three major mechanisms for controlling the evolution of the branch-and-bound search algorithms, by eliminating potential solution through... 

The preceding definitions allow us to explicitly characterize a branch-and-bound algorithm by... 

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... 

One measure of efficiency is the number of nodes of the branching tree that are expanded. Ibaraki (1978) has proved that the number of nodes expanded can be linked to the strength of the control knowledge, and proves that if one branch-and-bound algorithm has a better lower-bounding function, dominance and equivalence rules, then it will expand fewer nodes. 

Let us briefly discuss the theoretical results providing the basis for the improved efficiency of branch-and-bound algorithms. Let F = [x g(.x) lower-bound test. Then, the set L, defined by L =Fr X%, contains all the partial solutions, which can be terminated only by an equivalence relation. Recall that, by definition, no node in X% can be terminated by a dominance rule. 

Let A = (F, g, D, EQ, s) be a branch-and-bound algorithm. The algorithm terminates after decomposing exactly L /EQ nodes, provided that L / EQ < 00, where L / EQ denotes the set equivalent classes of solutions induced by the equivalence conditions EQ. 

For the proof of this theorem see Ibaraki (1978) as a result of Theorem 1, a natural measure of the efficiency of a branch-and-bound procedure is the number of the resulting equivalence classes under EQ. Furthermore, the following theorem (Ibaraki, 1978) allows a direct comparison of the efficiencies of two distinct branch-and-bound algorithms ... 

Assume that the following two branch-and-bound algorithms... 

Validity. The reasoning involved in this phase must be logically justifiable that is, the final conclusion should follow deductively from the facts of the example and from the theory of the domain. If we do not ensure this, we may be able to derive conditions on the two solutions that do not respect either the structure of the domain or the example. The use of these conditions could then invalidate the optimum-seeking behavior of the branch-and-bound algorithm. 

These predicates could be created for the various states that are explored during the branch-and-bound algorithm, or an appropriate subset that has been identified during the example identification. 

In the previous sections, we presented three of the four components necessary to carry out the improvement of problem-solving performance for flowshop scheduling, using branch-and-bound algorithms. The first of... 

Generalizations derived from a few problem-solving instances. Solving branch-and-bound problems is computationally expensive. Thus we would like to be able to achieve improvements in problem solving as rapidly as possible. 

In summary, the branch-and-bound algorithm as defined in this chapter assumes that the semantics of objective function, feasibility, and branching operation are fixed with respect to the problem class. As long as their interpretations are not changed, the derived equivalence and dominance rules would remain valid. 

---