It has serious practical consequences if it is known that a combinatorial problem is NP-complete. Then one can conclude according to the present state of science that no simple combinatorial algorithm can be applied and only an enumerative-type method can solve the problem in question. Enumerative methods are investigating many cases only in a non-explicit, i.e. implicit, way. It means that huge majority of the cases are dropped based on consequences obtained from the analysis of the particular numerical problem. The three most important enumerative methods are (i) implicit enumeration, (ii) dynamic programming, and (iii) branch and bound method. This chapter is devoted to the latter one. Implicit enumeration and dynamic programming can be applied within the family of optimization problems mainly if all variables have discrete nature. Branch and bound method can easily handle problems having both discrete and continuous variables. Further on the techniques of implicit enumeration can be incorporated easily in the branch and bound frame. Branch and bound method can be applied even in some cases of nonlinear programming.
The Branch and Bound (abbreviated further on as B&B) method is just a frame of a large family of methods. Its substeps can be carried out in different ways depending on the particular problem, the available software tools and the skill of the designer of the algorithm.
Boldface letters denote vectors and matrices; calligraphic letters are used for sets. Components of vectors are denoted by the same but non-boldface letter. Capital letters are used for matrices and the same but lower case letters denote their elements. The columns of a matrix are denoted by the same boldface but lower case letters.
Some formulae with their numbers are repeated several times in this chapter. The reason is that always a complete description of optimization problems is provided. Thus the fact that the number of a formula is repeated means that the formula is identical to the previous one.
In this section the branch and bound method is shown on a numerical example. The problem is a sample of the binary knapsack problem which is one of the easiest problems of integer programming but it is still NP-complete. The calculations are carried out in a brute force way to illustrate all features of B&B. More intelligent calculations, i.e. using implicit enumeration techniques will be discussed only at the end of the section.
There are many different knapsack problems. The first and classical one is the binary knapsack problem. It has the following story. A tourist is planning a tour in the mountains. He has a lot of objects which may be useful during the tour. For example ice pick and can opener can be among the objects. We suppose that the following conditions are satisfied.
Each object has a positive value and a positive weight. (E.g. a balloon filled with helium has a negative weight. See Exercises 24.1-1 and 24.1-2) The value is the degree of contribution of the object to the success of the tour.
The objects are independent from each other. (E.g. can and can opener are not independent as any of them without the other one has limited value.)
The knapsack of the tourist is strong and large enough to contain all possible objects.
The strength of the tourist makes possible to bring only a limited total weight.
But within this weight limit the tourist want to achieve the maximal total value.
The following notations are used to the mathematical formulation of the problem:
For each object a so-called binary or zero-one decision variable, say , is introduced:
is the weight of the object in the knapsack.
Similarly is the value of the object on the tour. The total weight in the knapsack is
which may not exceed the weight limit. Hence the mathematical form of the problem is
The difficulty of the problem is caused by the integrality requirement. If constraint (24.3) is substituted by the relaxed constraint, i.e. by
then the Problem (24.1), (24.2), and (24.4) is a linear programming problem. (24.4) means that not only a complete object can be in the knapsack but any part of it. Moreover it is not necessary to apply the simplex method or any other LP algorithm to solve it as its optimal solution is described by
Then there is an index and an optimal solution such that
Notice that there is only at most one non-integer component in . This property will be used at the numerical calculations.
From the point of view of B&B the relation of the Problems (24.1), (24.2), and (24.3) and (24.1), (24.2), and (24.4) is very important. Any feasible solution of the first one is also feasible in the second one. But the opposite statement is not true. In other words the set of feasible solutions of the first problem is a proper subset of the feasible solutions of the second one. This fact has two important consequences:
These properties are used in the course of the branch and bound method intensively.
The basic technique of the B&B method is that it divides the set of feasible solutions into smaller sets and tries to fathom them. The division is called branching as new branches are created in the enumeration tree. A subset is fathomed if it can be determined exactly if it contains an optimal solution.
To show the logic of B&B the problem
will be solved. The course of the solution is summarized on Figure 24.1.
Notice that condition (24.5) is satisfied as
The set of the feasible solutions of (24.6) is denoted by , i.e.
The continuous relaxation of (24.6) is
The set of the feasible solutions of (24.7) is denoted by , i.e.
Thus the difference between (24.6) and (24.7) is that the value of the variables must be either 0 or 1 in (24.6) and on the other hand they can take any value from the closed interval in the case of (24.7).
As the value of is non-integer, the optimal value 67.54 is just an upper bound of the optimal value of (24.6) and further analysis is needed. The value 67.54 can be rounded down to 67 because of the integrality of the coefficients in the objective function.
The key idea is that the sets of feasible solutions of both problems are divided into two parts according the two possible values of . The variable is chosen as its value is non-integer. The importance of the choice is discussed below.
Hence the problem
is a relaxation of the problem
The optimal value is 65.26 which gives the upper bound 65 for the optimal value of Problem (24.9). The other subsets of the feasible solutions are immediately investigated. The optimal solution of the problem
giving the value 67.28. Hence 67 is an upper bound of the problem
As the upper bound of (24.11) is higher than the upper bound of (24.9), i.e. this branch is more promising, first it is fathomed further on. It is cut again into two branches according to the two values of as it is the non-integer variable in the optimal solution of (24.10). Let
The sets and are containing the feasible solution of the original problems such that is fixed to 1 and is fixed to 0. In the sets and both variables are fixed to 1. The optimal solution of the first relaxed problem, i.e.
As it is integer it is also the optimal solution of the problem
The optimal objective function value is 65. The branch of the sets and is completely fathomed, i.e. it is not possible to find a better solution in it.
The other new branch is when both and are fixed to 1. If the objective function is optimized on then the optimal solution is
Applying the same technique again two branches are defined by the sets
The optimal solution of the branch of is
The optimal value is 63.32. It is strictly less than the objective function value of the feasible solution found in the branch of . Therefore it cannot contain an optimal solution. Thus its further exploration can be omitted although the best feasible solution of the branch is still not known. The branch of is infeasible as objects 1, 2, and 3 are overusing the knapsack. Traditionally this fact is denoted by using as optimal objective function value.
At this moment there is only one branch which is still unfathomed. It is the branch of . The upper bound here is 65 which is equal to the objective function value of the found feasible solution. One can immediately conclude that this feasible solution is optimal. If there is no need for alternative optimal solutions then the exploration of this last branch can be abandoned and the method is finished. If alternative optimal solutions are required then the exploration must be continued. The non-integer variable in the optimal solution of the branch is . The subbranches referred later as the 7th and 8th branches, defined by the equations and , give the upper bounds 56 and 61, respectively. Thus they do not contain any optimal solution and the method is finished.
The calculation is revisited to emphasize the general underlying logic of the method. The same properties are used in the next section when the general frame of B&B is discussed.
Problem (24.6) is a difficult one. Therefore the very similar but much easier Problem (24.7) has been solved instead of (24.6). A priori it was not possible to exclude the case that the optimal solution of (24.7) is the optimal solution of (24.6) as well. Finally it turned out that the optimal solution of (24.7) does not satisfy all constraints of (24.6) thus it is not optimal there. But the calculation was not useless, because an upper bound of the optimal value of (24.6) has been obtained. These properties are reflected in the definition of relaxation in the next section.
As the relaxation did not solved Problem (24.6) therefore it was divided into Subproblems (24.9) and (24.11). Both subproblems have their own optimal solution and the better one is the optimal solution of (24.6). They are still too difficult to be solved directly, therefore relaxations were generated to both of them. These problems are (24.8) and (24.10). The nature of (24.8) and (24.10) from mathematical point of view is the same as of (24.7).
Moreover the two subsets have no common element, i.e.
It is true for all other cases, as well. The reason is that the branching, i.e. the determination of the Subproblems (24.9) and (24.11) was made in a way that the optimal solution of the relaxation, i.e. the optimal solution of (24.7), was cut off.
The branching policy also has consequences on the upper bounds. Let be the optimal value of the problem where the objective function is unchanged and the set of feasible solutions is . Using this notation the optimal objective function values of the original and the relaxed problems are in the relation
If a subset is divided into and then
Notice that in the current Problem (24.12) is always satisfied with strict inequality
(The values and were mentioned only.) If the upper bounds of a certain quantity are compared then one can conclude that the smaller the better as it is closer to the value to be estimated. An equation similar to (24.12) is true for the non-relaxed problems, i.e. if then
but because of the difficulty of the solution of the problems, practically it is not possible to use (24.13) for getting further information.
A subproblem is fathomed and no further investigation of it is needed if either
its integer (non-relaxed) optimal solution is obtained, like in the case of , or
it is proven to be infeasible as in the case of , or
its upper bound is not greater than the value of the best known feasible solution (cases of and ).
If the first or third of these conditions are satisfied then all feasible solutions of the subproblem are enumerated in an implicit way.
The subproblems which are generated in the same iteration, are represented by two branches on the enumeration tree. They are siblings and have the same parent. Figure 24.1 visualize the course of the calculations using the parent–child relation.
The enumeration tree is modified by constructive steps when new branches are formed and also by reduction steps when some branches can be deleted as one of the three above-mentioned criteria are satisfied. The method stops when no subset remained which has to be still fathomed.
As it was mentioned in the introduction of the chapter, B&B and implicit enumeration can co-operate easily. Implicit enumeration uses so-called tests and obtains consequences on the values of the variables. For example if is fixed to 1 then the knapsack inequality immediately implies that must be 0, otherwise the capacity of the tourist is overused. It is true for the whole branch 2.
On the other hand if the objective function value must be at least 65, which is the value of the found feasible solution then it possible to conclude in branch 1 that the fifth object must be in the knapsack, i.e. must be 1, as the total value of the remaining objects 1, 2, and 4 is only 56.
Why such consequences accelerate the algorithm? In the example there are 5 binary variables, thus the number of possible cases is . Both branches 1 and 2 have 16 cases. If it is possible to determine the value of a variable, then the number of cases is halved. In the above example it means that only 8 cases remain to be investigated in both branches. This example is a small one. But in the case of larger problems the acceleration process is much more significant. E.g. if in a branch there are 21 free, i.e. non-fixed, variables but it is possible to determine the value of one of them then the investigation of 1 048 576 cases is saved. The application of the tests needs some extra calculation, of course. Thus a good trade-off must be found.
The use of information provided by other tools is further discussed in Section 24.5.
24.1-2 Show that an object of a knapsack problem having negative weight and negative value can be substituted by an object having positive weight and positive value such that the two knapsack problems are equivalent. (Hint. Use complementary variable.)
24.1-3 Solve Problem (24.6) with a branching strategy such that an integer valued variable is used for branching provided that such a variable exists.