13
Aug

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.

Tags: , , , , , , , , , , , , , , , , , , , , , , , , , , , , ,

9 Comments

Leave a Reply

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