Bounding algorithms

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

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

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. 

Ibaraki, T., The power of dominance relations in branch bound algorithms. JACM 24(2), 264-279 (1977). 

The results for this scenario were obtained using GAMS 2.5/CPLEX. The overall mathematical formulation entails 385 constraints, 175 continuous variables and 36 binary/discrete variables. Only 4 nodes were explored in the branch and bound algorithm leading to an optimal value of 215 t (fresh- and waste-water) in 0.17 CPU seconds. Figure 4.5 shows the water reuse/recycle network corresponding to fixed outlet concentration and variable water quantity for the literature example. It is worth noting that the quantity of water to processes 1 and 3 has been reduced by 5 and 12.5 t, respectively, from the specified quantity in order to maintain the outlet concentration at the maximum level. The overall water requirement has been reduced by almost 35% from the initial amount of 165 t. 

The overall model for scenario 1, which is MILP, entails 1320 constraints, 546 continuous and 120 discrete/binary variables. 52 nodes were explored in the branch and bound algorithm and the optimal freshwater requirement of 1767.84 kg was reached in 1.61 CPU seconds. Figure 4.9 shows the corresponding water reuse/recycle network. 

Table 4.4 is the summary of the mathematical model and the results obtained for the case study. The model for scenario 1 involves 637 constraints, 245 continuous and 42 binary variables. Seventy nodes were explored in the branch and bound algorithm. The model was solved in 1.61 CPU seconds, yielding an objective value (profit) of 1.61 million over the time horizon of interest, i.e. 6 h. This objective is concomitant with the production of 850 t of product and utilization of 210 t of freshwater. Ignoring any possibility for water reuse/recycle, whilst targeting the same product quantity would result in 390 t of freshwater utilization. Therefore, exploitation of water reuse/recycle opportunities results in more than 46% savings in freshwater utilization, in the absence of central reusable water storage. The water network to achieve the target is shown in Fig. 4.14. 

As shown in Table 4.4, the model for scenario 2, which is a nonconvex MINLP, consists of 1195 constraints, 352 continuous and 70 binary variables. An average of 151 nodes were explored in the branch and bound algorithm over the 3 major iterations between the MILP master problem and NLP subproblems. The problem was solved in 2.48 CPU seconds with an objective value of 1.67 million. Whilst the product quantity is the same as in scenario 1, i.e. 850 t, the water requirement is only 185 t, which corresponds to 52.56% reduction in freshwater requirement. The water network to achieve this target is shown in Fig. 4.15. 

Example To illustrate the spatial branch and bound algorithm, consider the global solution of... 

More generally, MILPs are solved with branch and bound algorithms, similar to the spatial branch and bound method of the previous section, that explore the search space. As seen in Fig. 3-61, binary variables are used to define the search tree, and a number of bounding properties can be noted from the structure of (3-110). 

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. 

---