Course 12: The Method of Solving Integer Program: Branch and Bound Method

Author: OptimizationCity Group

Table of Contents

Introduction

The main difference between an integer program and a linear program is the assumption that the variables of the problem are integer. At first glance, this assumption helps to achieve the optimal solution by controlling the all solution and report the best one as the optimal solution. Suppose a model has n binary variables (it can take zero or one value). If n=10, the number of solutions will be more than 1000. If n=20, the number of solutions will be more than one million. If n=30, the number of solutions will be more than one billion, and even the fastest computers will not be able to check all the solutions. . Now, if the number of variables is on the scale of millions, the difficulty of the solution increases rapidly.

The computational complexity of an integer program depends on two factors:

1) Number of integer variables

2) Structure of the problem

As can be seen, the number of constraints has no effect on the difficulty of solving the problem, which is contrary to the linear program. Since solving integer program is actually much more difficult than solving linear program, it sometimes seems logical to turn the problem into a relaxed linear program by removing integrity and then solving it by the simplex method. Then the solution obtained from the simplex method is rounded to integer numbers. This method may be used to solve some problems where the value of the variables is very large. But this method has the following two problems:

1- Maybe the rounded solution is no longer feasible.

2- Maybe the rounded solution is no longer optimal.

To explain the above two points, consider the following example.

The optimal solution of the above problem is x₁=2, x₂=5/9, z=11. We round the variable that has an non integer value, i.e. x₂=5/9 to the integer number x₂=1. The resulting solution is x₁=2, x₂=1 and z=7. The optimal solution of the original model, i.e. x₁=0, x₂=0, z= 10, has a lot of difference.

The most common algorithm for solving integer programming problems is the Branch and Bound method. The main point of this method is the implicit counting of feasible solutions. In the following, this method is studied.

Branch and Bound method

Because the number of possible solutions of a limited integer programming problem is finite; to find its optimal solution, the enumeration procedure should be used. As mentioned, because the number of solutions is so large, any counting method must be consciously designed to examine a small percentage of the solutions.

The basis of the branch and bound method is as follows:

Suppose the objective function is a minimization problem and the value of the objective function does not exceed a certain value which is the upper bound (denoted by z_U). This upper bound is usually the value of the objective function for the best feasible solution found so far. The feasible region is divided into several subsets. Then the lower bound of each subset (z_L) is obtained. This lower bound means that if z_L is greater than z_U, the corresponding subset is excluded from the analysis. Any subset that does not have a feasible solution or the best feasbile solution has been found, is excluded from the analysis. Any subset that is removed for any of the above reasons is called fathomed. When a branch reaches the bottom, one of the remaining subset that has the best bound is selected and the branching process is performed on it. This work continues until a feasible solution is obtained whose value of the objective function does not exceed the lower bound of any of the remaining subsets. this solution is the optimal.

Branch and bound algorithm

In the following, the summary of the branch and bound method is described:

Initial step: z_U=∞. Consider all solutions to the problem as the existing subset.

Branching step: Select one of the remaining subsets (a subset that has neither reached the bottom nor branched) for branching. Then divide the selected subset into two or more subsets.

Bounding step: Determine the lower bound of this subset and denoted as (z_L)

Fathoming step: Any new subset that meets one of the following conditions is excluded from further consideration.

Test 1: z_L≥z_U

Test 2: The desired subset does not contain any feasible solution.

Test 3: The best feasible solution of this subset is specified, z_L. If z_L<z_U, this solution replaces the best so far optimal solution and z_U=z_L. Test 1 is performed for the rest of the nodes.

Optimal step: Stop when there are no more subsets left to branch. The best feasible solution is the optimal solution. Otherwise, go to the branching step.

Example:

Consider the problem of assigning work to the four persons. The goal is to assign each job exclusively to one of the four people so that the total costs are minimized.

Solution:

Iteration 0: This problem has 24!=4 combination of solutions. We denote the lower bound of these 24 solutions by z_L. To calculate the lower bound, summing the minimum possible allocation costs (that is, the sum of the minimum numbers of the columns) is considered. Here is equal to 2+1+2+2=7. This solution is related to the allocation of DCDC, which is clearly the infeasible solution.

Iteration 1: We start by assigning work 1 to each person. For example, the lower bound , z_L, for assigning work 1 to person A becomes equal to (2+1+2)+9=14. In this way, the cost of assigning work 1 to person A is 9, and the minimum costs for the rest of the work, provided that person A is not assigned any more work, is 2+1+2. The lower bound for work 1 to person B is equal to (2+1+2)+4=9. To assign work 1 to person C, the lower bound is equal to (3+2+5)+3=13. To assign work 1 to person D, z_L is equal to (2+1+3)+2=8.

Because z_L for subset C leads to the feasible solution of CBDA; therefore, the upper bound becomes z_U=13 and CBDA becomes the current optimal solution. According to test 3, the subset C is conquered (fathomed). According to test 1, the subset A is also conquered(fathomed). Therefore only two subsets B and D remain for branching. The results are summarized in the figure below.

Iteration 2: Out of the two remaining subsets, subset D is chosen because it has the lowest lower bound. This principle is called the best bound rule. In this subset, work 1 is assigned to person D, and in this subset, 3 subsets DA, DB, and DC can be branched, and the lower bound is equal to 2+5+(3+2)=12, 2+3+(3+2)=10, and 2+1+(4+5)=12; respectively. For these three subsets, none of the fathoming conditin hold. Therefore, the remaining subsets are B, DA, DB and DC. The results of this iteration are shown in the figure below.

Iteration 3: Among the remaining four subsets, subset B is selected because of the lowest lower bound. This choice is divided into three subsets BA, BC, BD. Their lower limit will be 4+5+(2+2)=13, 4+1+(2+5)=12 and 4+4+(2+3)=13; respectively. Because BA and BC subsets are feasible solutions and the lower bound of BA and BD subsets are equal to the upper bound, so all three subsets are fathomed. Also, because the subset BC is a feasible solution, and the value of the objective function is lower than the z_U; therefore the BCDA solution is considered as the best new feasible solution. z_U=12 is equal to z_L of DA and DC subsets, so these two subsets also are fathomed. The only subset left at this point is DB. The results of this iteration are shown in the below figure.

Iteration 4: The only remaining subset is DB, which branches into DBA and DBC subsets. Their lower limit is 2+3+4+(2)=11 and 2+3+3+(5)=13; respectively. Because we have reached feasible solution in these two branches, therefore both subsets are fathomed. The feasible solution DBAC related to the DBA subset is better than the best feasible solution (11<12), so this solution (DBAC) is selected as the new feasible solution. There is no other subset that has not yet being fathomed, therefore the best feasible solution (i.e. DBAC) is the optimal solution and the algorithm ends. The summary of the calculations of this iteration is shown in the below figure.

Remark: In the above example, the best bound rule was used to select branches. Another rule is the latest bound rule. In this method, the last branch used to calculate the lower bound is used for branching.

Branch and bound algorithm for 0-1 programming

As mentioned in the previous section, many integer programming problems are in the form of 0-1 variables. But in some problems, variables can take more than two values. But these models can be converted into binary variables. Let x be an integer. In this case it can be said

where

In this case, y_i are zero and one variables.

To present the branch-and-bound solution for the binary integer programming problem, consider a general problem as follows.

which in the above model is 0≤c₁≤c₂≤…≤c_n. This assumption does not actually create a limitation. Because if c_j<0, x_j can be replaced by x_j‘-1, in which case the variable coefficient x_j‘ will be positive in the objective function. According to the above, the branch and bound algorithm for 0-1 variables is presented as follows.

Branching step: In this step, a subset is defined by assigning zero or one to some variables, which is called partial solution (x₁,x₂,…,x_N). A complete partial solution is a solution whose first N variables are equal to the partial variables. If (x₁,x₂,…,x_N) is the last partial solution, this solution is divided into two subsets, in one of which x_N+1=1 and in the other x_N+1=0.

Bounding step: The lower bound z_L corresponding to the partial solution (x₁,x₂,…,x_N) that is feasible is defined as follows:

If the partial solution is not feasible and x_N=0, the lower bound can be defined as follows:

If the partial solution is still not feasible and x_N=1, the lower bound can be defined as follows:

Fathoming step: If the current partial solution applies to one of the following three tests, there is no need to branch. These tests include:

Test 1: z_L≥z_U

where z_U is the best feasible solution that has been obtained up to this point. If a feasible solution has not been obtained so far, z_U=∞ is assumed.

Test 2: In this test, the absence of a feasible solution in the desired subset is checked, which is done by completing the current partial solution. Is it possible that at least one of the constraints is not satisfied? According to this test, if the following relation applies for any of i=1,…,m, then the branching of the current partial solution is stopped.

Test 3:

In this test, reaching the best feasible solution in the subset is checked. If the current partial solution ends with x_N=0, the feasiblity of the partial solution in which x_N+1=1 is checked. The mathematical expression of this test is as follows.

If this condition is met and we also have z_L<z_U, then z_U=z_L and we consider this solution as the best feasible solution. To clarify the algorithm, we solve the following example.

Example:

Solve the following integer programming problem.

Solution:

Iteration 0: z_U=∞ and because the coefficient of the variables in the objective function are non-negative, therefore the optimal value is definitely greater than zero and z_L=0. Because the solution (0,0,0,0,0,0) does not satisfy in constraints 1 and 3, therefore the stopping condition is not met. This node should be branched and this node should be divided into two branches x₁=0, x₁=1.

Iteration 1: partial solution (1) is checked:

Test 1:

Test 2:

This node is not fathomed.

Test 3: The answer (1,0,0,0,0,0) is checked whether the constraints are met or not.

This node is not fathomed in test 3.

Iteration 2: partial solution (1,0) is checked:

Test 1:

Test 2:

Test 3: The answer (1,0,1,0,0,0) is checked whether the constraints are met or not.

This node is not fathomed in test 3.

Iteration 3: partial solution (1,0,0) is checked:

Test 1:

Test 2:

Test 3: The answer (1,0,0,1,0,0) is checked whether the constraints are met or not.

The solution (1,0,0,1,0,0) is feasible and therefore z_U=12.

Iteration 4: partial solution (1,0,1) is checked:

Test 1:

Test 2:

Because constraint 1 is not met, this node is fathomed based on test 2.

Iteration 5: partial solution (1,1) is checked:

Test 1:

Test 2:

This node is fathomed.

Iteration 6: partial solution (0) is checked:

Test 1:

Test 2:

Test 3:

Since x₁=0, it should be checked whether (0,1,0,0,0,0) is feasible or not?

This node is not fathomed.

Iteration 7: partial solution (0,1) is checked:

Test 1:

Test 2:

Test 3: The answer (0,1,0,0,0,0) is checked whether the constraints are met or not.

Iteration 8: partial solution (0,1,1) is checked:

Test 1:

Test 2:

Test 3: The solution (0,1,1,0,0,0) is checked whether the constraints are met or not.

This node is fathomed with test 3 and z_U=11 is the current best feasible solution.

Iteration 9: partial solution (0,1,0) is checked:

Test 1:

14=z_L≥z_U=11 is valid, and therefore this node is fathomed.

Iteration 10: partial solution (0, 0) is checked:

Test 1:

Test 2:

Test 3: The solution (0,0,1,0,0,0) is checked whether the constraints are met or not.

This node is not fathomed.

Iteration 11: partial solution (0,0,1) is checked:

Test 1:

Test 2:

Test 3: The solution (0,0,1,0,0,0) is checked whether the constraints are met or not.

Iteration 12: partial solution (0,0,1,1) is checked:

Test 1:

15=z_L≥z_U=11, and therefore this node is fathomed.

Iteration 13: partial solution (0,0,1,0) is checked:

Test 1:

16=z_L≥z_U=11 and therefore this node is fathomed.

Iteration 14: partial solution (0,0, 0) is checked:

Test 1:

Test 2:

This node is fathomed with test 2.

All nodes are fathomed and the optimal solution is z=11 and (0,1,1,0,0,0). The summary of calculations is shown in the figure below.

Branch and bound algorithm for mixed integer programming

Consider the following integer programming model:

In the above model, if I=n, we will have a pure integer programming model. To solve the above model, the following algorithm is presented.

The integrity condition is removed and the relaxation of integer program is solved. If the resulting solution takes a discrete value for all integer variables, then the optimal solution has been obtained. Otherwise, in each iteration, a variable such as x_j selects, whose value is not an integer and is in the following range:

Then the existing subset is divides into two new subsets.

1- x_j≤k

2- x_j≥k+1

By solving the relaxation of integer program with adding the constraints x_j≤k or x_j≥k+1, an upper bound (z_U) for the subset is obtained. The solution of the relaxed problem is obtained by the dual simplex method. The tests that find out the fathomed nodes are as following three tests:

Test 1:

Test 2: With the dual simplex method, we find that there is no feasible solution.

Test 3: In the optimal solution, all variables x_j (j=1,…,I) are integers.

If a subset is fathomed with test 3 and z_U>z_L, then z_L=z_U is set and this solution is saved as the best feasible solution. When all subsets are fathomed, then the lower bound reports as the optimal solution.

Example: Solve the following integer program using the branch and bound alghorithm.

Solution:

The variables x₁ and x₂ have an non-integer value in the optimal solution. x₂ is selected from these two variables.

The coefficients of the variables in row 4 are positive and the right hand side is negative; therefore this solution is infeasibel.

All steps can be shown in the tree below.

Example: Consider the following integer programming.

a) Solve this problem graphically.

b) Solve the relaxed integer programming graphically. Round the resulting answer to the nearest integer number. Is it feasible or not? Then calculate all the rounded solutions (round any non-integer values up and down) and check their feasibilty. Are any of these solutions feasible?

Solution:

The optimal answer is z=13, and (x₁,x₂)=(2,3).

b) The optimal solution of the relaxed integer problem is equal to (x₁,x₂)=(2.6,1.6) with z=14.6. The closest integer solution is (x₁,x₂)=(3,2), which is not feasible. All rounded solutions are as follows:

It can be seen from the above table that none of the rounded solutions are optimal.

Example: Consider the following integer programming model.

a) Solve this problem graphically.

b) Solve the relaxed integer program graphically. Round the solution to the nearest integer number. Is it feasible or not? Then calculate all the rounded solutions and check their feasibility and get the value of the objective function corresponding to the feasible solutions. Are any of these solutions optimal?

Solution:

The optimal solution of the above model is equal to (x₁,x₂)=(1,1).

b) The optimal solution of the relaxed integer problem is equal to (x₁,x₂)=(0,0.9) and the nearest integer solution is (x₁,x₂)=(0,1) which is an infeasible solution. Another rounded solution is (x₁,x₂)=(0,0) which is feasible but not optimal.

Example:

Solve the following integer programming problem using the branch-and-bound algorithm.

Solution:

To solve the above model, we convert the model to the following standard form.

– Converting max to min and changing the direction of the sign ≤ to ≥.

– Making the coefficients of the variables of the objective function positive by changing the variables x₁®1-x₁, x₃®1-x₃ and, x₅®1-x₅

– Changing the order of variables so that 0≤c₁≤c₂≤…≤c_n. For this purpose x1«x2, x3«x5 and x4«x3. In this case, the optimization model becomes the standard form as follows.

Iteration 0: z_U=∞ and because the coefficient of the variables in the objective function is non-negative, the value of the objective function is definitely greater than -11. It can be said that z_L=-11. Since the solution (x₁,x₂,x₃,x₄,x₅)=(0,0,0,0,0) does not apply to constraints 1 and 2, the stopping condition is not met and the node x₁ must be branched to x₁=1 and x₁=0.

Iteration 1: Check the partial solution (0).

Test 1:

Test 2:

This node is not fathomed in this test.

Test 3: Since x₁=0, it should be checked whether the solution (0,1,0,0,0) is feasible or not?

This node is not fathomed in this test.

Iteration 2: Check the partial solution (0,0). This solution is chosen because of the lowest lower bound.

Test 1:

Test 2:

Test 3: Check the solution (0,0,1,0,0).

This node is not fathomed in this test.

Iteration 3: Check the partial solution (1).

Test 1:

Test 2:

Test 3: check the solution (1,0,0,0,0).

This node is not fathomed.

Iteration 4: Check the partial solution (0,0,0).

Test 1:

Test 2:

This node is fathomed.

Iteration 5: Check the partial solution (1,0).

Test 2:

Test 3: check the solution (1,0,1,0,0).

Iteration 6: Check the partial solution (1,0,0).

Test 1:

Test 2:

Test 3: check the solution (1,0,0,1,0).

Iteration 7: Check the partial solution (0,1).

Test 1:

Test 2:

Test 3: check the solution (0,1,0,0,0).

Iteration 8: Check the partial solution (0,1,1).

Test 1:

Test 2:

Test 3: check the solution (0,1,1,0,0).

This node is fathomed. All nodes were examined. Optimal solution x=(0,1,1,0,0) and z_U=-6. The summary of the algorithm is shown in the figure below.

Example: Consider the following integer program:

a) Solve the above model graphically.

b) Solve the above model using the branch and bound algorthim. Use the graphical method to solve the following problems.

c) Convert the above model into the form of a binary programming model and then solve it using the binary branch and bound algorithm.

Solution:

The solution of the relaxed integer program is equal to x=(3,1.7143), z=-0.429 and the solution of the integer program is x=(2,1), z=-1.

b) Because the solution of the relaxed integer program is x=(3,1.7143), therefore, there are two branches x₂≥2 and x₂≤1 on the variable x₂.

– Branch x₂≥2

This subproblem is infeasible. Therefore, the node x₂≥2 is fathomed.

– Branch x₂≤1

The optimal solution of the subproblem x₂≤1 is equal to (x₁,x₂)=(2,1) and z=-1, so this is the optimal solution of the original model.

c) To convert the original model into a binary programming, consider x₁=y₁+2y₂ and x₂=s₁+2s₂. Therefore, the original integer program is converted into binary form as follows.

Max is converted to Min.

To change the sign of s₁ and s₂, change the variables s₂®1-s₂ and s₁®1-s₁. By making these changes, we reach the following model, which can be by the binary branch and bound algorithm.

To solve the above model, we do as follows.

Iteration 0: Set z_U=∞. because the coefficients of the variables are non-negative, the value of the objective function is definitely greater than -15 and therefore z_L=-15. Solution (0,0,0,0) is an infeasible solution, thus the stopping condition is not met. Consider two branches y₁=1 and y₁=0.

Iteration 1: Check partial solution (0).

Test 1:

Test 2:

Test 3: Check the solution (0,1,0,0).

Iteration 2: Check partial solution (0,0).

Test 1:

Test 2:

Test 3: Check the solution (0,0,1,0).

Iteration 3: Check partial solution (1).

Test 1:

Test 2:

Test 3: Check the solution (1,0,0,0).

Iteration 4: Check partial solution (1,0).

Test 1:

Test 2:

Test 3: Check the solution (1,0,1,0).

Iteration 5: Check partial solution (0,0,0).

Test 1:

Test 2:

This node is fathomed.

Iteration 6: Check partial solution (0,1).

Test 1:

Test 2:

Test 3: Check the solution (0,1,0,0).

Iteration 7: Check partial solution (1,0,0).

Test 1:

Test 2:

This node is fathomed.

Iteration 8: Check partial solution (1,1).

Test 1:

Test 2:

Test 3: Check the solution (1,1,0).

Iteration 9: Check partial solution (0,1,0).

Test 1:

Test 2:

This node is fathomed.

Iteration 10: Check partial solution (0,0,1).

Test 1:

Test 2:

Test 3: Check the solution (0,0,1,0).

We check all nodes and we reach the complete solution of x=(0,0,1,1), z=1. This is the optimal solution of the problem. The summary of calculations is shown in the figure below.

Example: Using the branch-and-bound method, assign works to people in such a way that the total costs are minimized:

Solution:

Iteration 0: This problem has 5!=120 different combinations of solution. The lower bound of these 120 solutioin is called z_L. To determine the lower bound, the sum of the minimum allocation costs (i.e. the minimum numbers for columns of the above table) is considered. In this example, it is equal to 39+34+24+23+18=138. This solution is related to assignment (A, E, B, D, E), which is clearly infeasible.

Iteration 1: We start by assigning work 1 to people. We divide all the solution into 5 cases. The lower bound of assigning work 1 to different people is calculated as follows.

Iteration 2: Out of the remaining 5 subsets, subset A is chosen because of the lowest lower bound. This subset is divided into AB, AC, AD, and AE. The lower bound of these 4 subsets is calculated as follows.

From above four subsets, two feasible solutions ACBDE and ADBCE are made, and the solution ACBDE becomes the current best feasible solution, which is Z=154.

The subset 1®A and 2®B, which is abbreviated as AB, is fathomed because its lower bound is greater than the current best feasible solution (z_U=154<194=z_L). AE subset is selected for branching.

Iteration 3: The subset AE is divided into three subsets AEB, AEC and AED. The lower bound of these three subsets is calculated as follows.

The above three solution are feasible, but because the correspoding cost is more than 154=z_L, they are fathomed.

All nodes were examined. The optimal solution is equal to z=154 and assigning tasks to people is ACBDE. The results are summarized in the figure below.

Example: Consider the following integer program.

a) Solve the above problem by graphical method.

b) Solve the above problem with the branch and bound algorithm using of graphical method.

Solution:

a) The above model is solved graphically as follows.

The optimal solution of the relaxed integer program is equal to x=(1.5,1.5) and z=37.5. The optimal solution of the integer program is equal to x=(2,1) and z=40.

b) Given that x=(1.5,1.5), two branches are made for x₁ variable.

Branch: x₁≤1

The optimal solution of the relaxed problem by adding the constraint x₁≤1 is equal to (x₁,x₂)=(1,3) and z=45, which is a feasible solution for the main problem.

Branch: x₁≥2

The optimal solution of the relaxed integer program by adding the constraint x₁≥2 is equal to (x₁,x₂)=(2,1) and z=40, which is the feasible solution for the main problem. Since there is no branch left, the solution (x₁,x₂)=(2,1) and z=40 is the optimal solution.

Example: Consider the following integer program.