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

Author: OptimizationCity Group

 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 x1=2, x2=5/9, z=11. We round the variable that has an non integer value, i.e. x2=5/9 to the integer number x2=1. The resulting solution is x1=2, x2=1 and z=7. The optimal solution of the original model, i.e. x1=0, x2=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 zU). 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 (zL) is obtained. This lower bound means that if zL is greater than zU, 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: zU=∞. 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 (zL)

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

Test 1: zL≥zU

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

Test 3: The best feasible solution of this subset is specified, zL. If zL<zU, this solution replaces the best so far optimal solution and zU=zL. 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 zL. 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 , zL, 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, zL is equal to (2+1+3)+2=8.

Because zL for subset C leads to the feasible solution of CBDA; therefore, the upper bound becomes zU=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 zU; therefore the BCDA solution is considered as the best new feasible solution. zU=12 is equal to zL 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, yi 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≤c1≤c2≤…≤cn. This assumption does not actually create a limitation. Because if cj<0, xj can be replaced by xj‘-1, in which case the variable coefficient xj‘ 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 (x1,x2,…,xN). A complete partial solution is a solution whose first N variables are equal to the partial variables. If (x1,x2,…,xN) is the last partial solution, this solution is divided into two subsets, in one of which xN+1=1 and in the other xN+1=0.

Bounding step: The lower bound zL corresponding to the partial solution (x1,x2,…,xN) that is feasible is defined as follows:

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

If the partial solution is still not feasible and xN=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: zL≥zU

where zU is the best feasible solution that has been obtained up to this point. If a feasible solution has not been obtained so far, zU=∞ 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 xN=0, the feasiblity of the partial solution in which xN+1=1 is checked. The mathematical expression of this test is as follows.

If this condition is met and we also have zL<zU, then zU=zL 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: zU= and because the coefficient of the variables in the objective function are non-negative, therefore the optimal value is definitely greater than zero and zL=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 x1=0, x1=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 zU=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 x1=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 zU=11 is the current best feasible solution.

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

Test 1:

14=zL≥zU=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=zL≥zU=11, and therefore this node is fathomed.

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

Test 1:

16=zL≥zU=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 xj selects, whose value is not an integer and is in the following range:

Then the existing subset is divides into two new subsets.

1- xj≤k

2- xj≥k+1

By solving the relaxation of integer program with adding the constraints xj≤k or xj≥k+1, an upper bound (zU) 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 xj (j=1,…,I) are integers.

If a subset is fathomed with test 3 and zU>zL, then zL=zU 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 x1 and x2 have an non-integer value in the optimal solution. x2 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:

a)

The optimal answer is z=13, and (x1,x2)=(2,3).

b) The optimal solution of the relaxed integer problem is equal to (x1,x2)=(2.6,1.6) with z=14.6. The closest integer solution is (x1,x2)=(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 (x1,x2)=(1,1).

b) The optimal solution of the relaxed integer problem is equal to (x1,x2)=(0,0.9) and the nearest integer solution is (x1,x2)=(0,1) which is an infeasible solution. Another rounded solution is (x1,x2)=(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 x1®1-x1, x3®1-x3 and, x5®1-x5

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

Iteration 0: zU= 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 zL=-11. Since the solution (x1,x2,x3,x4,x5)=(0,0,0,0,0) does not apply to constraints 1 and 2, the stopping condition is not met and the node x1 must be branched to x1=1 and x1=0.

Iteration 1: Check the partial solution (0).

Test 1:

Test 2:

This node is not fathomed in this test.

Test 3: Since x1=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 zU=-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:

A)

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 x2≥2 and x2≤1 on the variable x2.

– Branch x2≥2

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

– Branch x2≤1

The optimal solution of the subproblem x2≤1 is equal to (x1,x2)=(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 x1=y1+2y2 and x2=s1+2s2. Therefore, the original integer program is converted into binary form as follows.

Max is converted to Min.

To change the sign of s1 and s2, change the variables s2®1-s2 and s1®1-s1. 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 zU=. because the coefficients of the variables are non-negative, the value of the objective function is definitely greater than -15 and therefore zL=-15. Solution (0,0,0,0) is an infeasible solution, thus the stopping condition is not met. Consider two branches y1=1 and y1=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 zL. 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 (zU=154<194=zL). 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=zL, 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 x1 variable.

Branch: x1≤1

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

Branch: x1≥2

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

Example: Consider the following integer program.

Solve the above model by branch and bound algorithm.

Solution:

The standard form of the above model is as follows:

The summary of the branch and edge method is as follows. The calculation details of each node are given below, too.

The optimal solution is x=(3,1) and z=7.

Example: Consider the following integer program.

Solve the above problem by branch and bound algorithm.

Solution:

The standard form of the above model is as follows.

The summary of the branch and edge method is as follows. The calculation details of each node are given below, too.

Leave a Reply

Your email address will not be published. Required fields are marked *