# Operations Research 09B: Branch and Bound for Integer Programming

In this video, I’ll talk about how to solve

IP problems using the branch and bound method. The branch-and-bound algorithm is actually

an enumeration of candidate solutions in the search space. It splits the original problem into branches

of subproblems. Before enumerating the candidate solutions

of a branch, the branch is checked against upper or lower estimated bounds of the optimal

solution. The branch is discarded if it cannot produce

a better solution than the best one found so far by the algorithm. Let’s check the branch-and bound algorithm

for solving maximization IP or Mixed IP problems. A minimization IP or Mixed IP problem can

be converted to a maximization problem by maximizing the opposite of the objective function. Step 1 is called Initialization. Set z* to be negative infinity. Solve the LP relaxation; If not fathomed,

then continue. I’ll talk about what fathoming is later. Step 2 is called branching. Select the unfathomed subproblem that was

created recently. Then choose a branch variable that is supposed

to be an integer but it is not right now in the optimal solution to the LP relaxation

of the subproblem. Let xj be this variable and xj* its value

in the solution. Create two new subproblems by adding the respective

constraints xj ≤ the floor function of xj* and xj ≥ the ceiling function of xj*. The floor function means the largest integer

less than or equal to xj*. The ceiling function means the smallest integer

greater than or equal to xj*. Step 3 is called bounding. For each new subproblem, obtain the optimal

z value of the LP relaxation, which will be the upper bound for this branch of subproblems. Step 4 is called fathoming. Mark the new subproblem as fathomed if at

least one of the following three tests is true. Test 1, its z value ≤ z*. Test 2, its LP relaxation has no feasible

solutions. Test 3, the optimal solution to its LP relaxation

has integer values for all integer restricted variables. If this test is true, we need to also update

z* and re-test F1. Step 5 is called the optimality test. We need to stop the algorithm when all the

subproblems are fathomed; the current z* is optimal. Otherwise, go to Step 2. and repeat the process. Let’s check this MIP example. It is a maximization problem with 4 variables,

x1 through x4. They are all required to be greater than or

equal to 0. Only x1, x2, and x3 are required to be integer

numbers. The LP relaxation is the problem without the

integer restrictions. Now, let’s initialize z* to be negative infinity. Then we solve the LP relaxation using the

simplex method. The optimal solution is x1 is equal to 1.25,

x2 is equal to 1.5, x3 is equal to 1.75, and x4 is equal to 0. The z value is 14.25. This problem is unfathomed because, one, the

LP relaxation’s z value, 14.25, is not less than or equal to z*, negative infinity; two,

the LP relaxation is not infeasible, and three, x1, x2, and x3 are supposed to be integers

but they are not right now. Let’s randomly pick one variable that is supposed

to be an integer but it is not now. For example, we pick x1. We call x1 the branch variable. We can split the search space into two parts. One is less than or equal to 1 and the other

is greater than or equal to 2. Accordingly, the original problem is split

into two subproblems. One is the original LP relaxation with an

additional constraint x1 is less than or equal to 1. The other is the original LP relaxation with

an additional constraint x1 is greater than or equal to 2. Let’s solve these two subproblems using the

simplex method . We find that this subproblem is infeasible. So it is fathomed based on Test 2. The optimal solution to this subproblem is

(1, 1.2, 1.8, 0) and the z value is 14.2. This is not fathomed because 14.2 is not less

than or equal to the current z* value. Some integer-restricted variables still have

fractional numbers. We pick x2 as the branch variable and formulate

two subproblems. One is the original LP relaxation with two

additional constraints x1 is less than or equal to 1 and x2 is less than or equal to

1. The other is the original LP relaxation with

two additional constraints x1 is less than or equal to 1 and x2 is greater or equal to

2. Let’s solve these two subproblems and these

are their optimal solutions. Neither of the two subproblems is fathomed. So we need to continue this process and split

it using x1 again for this branch because it is supposed to be an integer but it is

not now. This branch should be x1 is less than or equal

to 0. But we know from the problem formulation that

x1 should be greater than or equal to 0. So the only possible value in this branch

is just x1 is equal to 0. This branch should be x1 is greater than or

equal to 1. But we know from a previous step that x1 should

be less than or equal to 1. So the only possible value in this branch

is just x1 is equal to 1. Let’s solve these two subproblems using the

simplex method. We find that this subproblem is infeasible. So it is fathomed based on Test 2. The optimal solution to this subproblem is

(0, 0, 2, 0.5) and the z value is 13.5. This is fathomed based on test 3 because the

integer-restricted variables x1, x2, and x3 are indeed integer numbers. We also need to update the z* value because

it is better than negative infinity. After we update z*, we need to re-check unfathomed

subproblems. We find that we only have one unfathomed subproblem,

this one. But the upper bound of this branch, 12.17,

is worse than the current z* value 13.5. So, this branch is also fathomed based on

test 1. This is the final optimal solution to the

MIP problem. Let’s check this BIP example. It is a maximization problem with 4 variables,

x1 through x4. They are all required to be greater than or

equal to 0. Also, they are all required to be binary. That means, either 0 or 1. The LP relaxation is the problem without the

binary restrictions. Now, let’s initialize z* to be negative infinity. Then we solve the LP relaxation using the

simplex method. This is the optimal solution. This problem is unfathomed. x1 is still not 0 or 1 yet. We call x1 the branch variable and formulate

two subproblems. Let’s solve these two subproblems using the

simplex method. This branch is fathomed because all the variables

are binary. So we update z*. This branch is not fathomed yet. We pick x2 as the branch variable and formulate

two subproblems. Let’s solve these two subproblems and find

their optimal solutions. Neither of the two problems is fathomed. So we need to continue this process. For this branch, we split it using x4 and

formulate two subproblems. Let’s solve these two subproblems. We find that this subproblem is infeasible. So it is fathomed based on Test 2. The optimal solution to this subproblem is

(1, 1, 0, 0) and the z value is 14. This is fathomed based on test 3 because the

binary-restricted variables x1 through x4 are all 0 or 1. We update the z* value because 14 is better

than 9. After we update z*, we need to re-check unfathomed

subproblems. We find that we only have one unfathomed subproblem,

this one. But the upper bound of this branch, 13, is

worse than the current z* value 14. So, this branch is also fathomed based on

test 1. This is the final optimal solution to the

BIP problem. Okay, that’s how to use branch and bound to

solve IP, MIP, and BIP problems. Thanks for watching.

sir this video is very useful to us,your definition is very clear.

Thank you! I am waiting you to visit my channel and subscribe it!

Very clear explanations. Thank you !

Should we solve simplex again and again for each branch? Doesn't it make it too long?

Branch and bound , branch and cut, branch and price. OMG

second example , first iteration in x=1 branch , values shod be 1, .8 , 0 , .8

Hi Guys, please comment and let me know what you think about this Operations Research Open Course. Your feedback is really appreciated. If you enjoy the video, please subscribe and share. All my replies here are only related to the content in my own videos. I am afraid I won't be able to answer other questions. Thanks for your understanding.

Sir, for Minimization case, does F1 in 2:31 change to z value>z*?

Which means we only fathom when z value is greater than z*. Not greater or "equal" ?

Hi sir, can you explain for me in 5:57 why you chose the constraint x2<=1 not x2>=2 please?