Okay, so now let's move on to our next example. This example is actually our motivating example, okay? So we have two constraints, one maximization, objective function, and again all the variables they should be integers. So let's try to solve this problem with branch-and-bound. So as we already know, if we do linear relaxation, and then try to solve the linear program, we will see this fractional solution, okay? So in this case, we have two variables x1, and x2. Both of them are fractional. So in this case, we somehow need to choose one to branch. So in this case, let's assume we will branch on x1. So we will take a look at the value for x1, which is 15 over 4. So in this particular case, because this is, we think, 3 and 4, so we will add a constraint saying that x, y is less than or equal to 3, and add another constraint x, y is greater than or equal to 4. So let's say we do the first one. In this case, our subproblem 2 is going to generate a candidate solution. Once we say x1 should be less than or equal to 3, we solve this linear relaxation, we luckily get an integer solution, okay? So this integer solution immediately tells us that there is no need to keep branching, okay? Because this is already an integer solution, it gives us a feasible solution and IP feasible solution that can be a candidate solution, okay? So now we have 39 as our bound, so that further we may reduce some computation. And then the other side, our x candidate solution here is not integer. We get some solution where our x1 variable is 4, but x2 is 9 over 5. So in this case, we need to keep branching. So we know that the variable x2 is not good. So either we say this should be less than or equal to 1, or we say it should be greater than or equal to 2, okay? So in this case, we add two constraints again. And of course, we do that because 41, okay, the solution here, 41, the value is greater than 39, the current optimal objective value that we may obtain. So that's why we should keep branching. And then, once we have two constraints, leading to two simple problems, very quickly, we may see that, for the first one, we say x2 should be less than or equal to 1. So your x2 should be less than or equal to 1. In this case, we get a solution which, unfortunately again, is fractional. So in this case, we get this objective value, which is 40 point something, and then that is greater than 39. So again, this leaves some hope to get an optimal solution, to get a better solution. So we keep branching on this. So our x1 here is a fractional value, so we add two constraints. Either x1 is less than or equal to 4, or greater than or equal to 5, okay? And at the same time, we move on to subproblem 5. Subproblem 5 states that our x2 should be greater than or equal to 2. So in this case, this gives us an infeasible solution, and then we may also stop there. So in the next iteration we try subproblem 6. For subproblem 6, we say your x1 should be greater than or equal to 4. And your x1 should be less than or equal to 4. So no wonder the only possible case is for x1 to be equal to 4. And we also have x2 to be less than or equal to 1. So afterwards, the feasible region is just this line segment. We get a feasible solution 4,1. Similarly, for the last subproblem here, we say our x1 should be greater than or equal to 4, or x1 should be greater than equal to 5. So here you have a constraint, and eventually left this to only one point as a feasible point. In this case, we get 5,0, and it happens that this is actually an optimal solution, okay? When we solve subproblem 7, we get a solution, which is integer, and this solution has a larger objective value than the original one. So in this case, this is an optimal solution because all these nodes are concluded that there's no needed to proceed, okay? So this completes the whole process.
