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.