Okay, so our last topic is to introduce the idea, the concept for heuristic algorithms. So our knapsack example is a very good one for us to illustrate the idea. So we all know that we have a knapsack capacity 11 kilograms, we have 5 items to select from. And we know that we have this formulation as an integer program. So all these are not new. And then we also know that we are able to find an optimal solution which is (1, 0, 1, 0, 1). This gives us an objective value which is 9, okay? So these are all something that is not new. So the thing is that actually the knapsack problem is the so called NP-hard problem. So if you are not so familiar with this idea of NP-hardness, that's also fine. Just try to be convinced by me that most researchers in the world they believe that there's no efficient way to solve the knapsack problem and find an optimal solution. So there's no efficient exact algorithm. What does that mean? So first, an exact algorithm sold for an optimal solution. If you want to find an optimal solution, in this case, no one has found a polynomial-time algorithm. No one has found a quick enough algorithm that can be applied to any knapsack problem. As long as you have millions of variables for knapsack, you only have one constraint. So as long as you have thousands of hundreds of variables, there is no simple, easy way to find an optimal solution. So that's the idea of NP-hard. Somehow it just means, well, the knapsack problem is just hard, then branch and bound or whatever exact algorithm they are not so easy not, so efficient. So we still may run branch and bound as always, but it may take a long time to solve an instance of a knapsack problem. If we have for example, thousands of variables. So when finding an optimal solution is not practical, is too time consuming, we would look for the other way. We will look for good heuristic algorithms. So heuristic algorithm is going to report a solution in a very short time, and at least it should be in polynomial time, okay? So using the big O notation, it may be n square m, for example, it may be n square log n for example, and so on, and so on. Somehow it must be at least a polynomial time. And then the reported solutionhopefully is near-optimal. So obviously it should be a feasible solution, it may be executable, and hopefully it is near-optimal. So if we want to explain this idea with some visualization, it may be the following. So pretty much when we are talking about solutions, we are talking about optimal solution or near optimal solutions. That corresponds to the idea of heuristic algorithms and exact algorithms. So suppose we are comparing exact algorithms and heuristic algorithms. Suppose we try to compare about solution quality, okay?. Then if this is a maximization problem, then of course for exact algorithm it is going to reach an optimal solution. And for the heuristic algorithm probably, it cannot, but the gap should not be too far from each other. If the exact algorithm can get you an optimal solution, which objective value is 100, the heuristic algorithm probably gives you 95,92, 88, something like that. But if you talk about the solution time or computational time, the heuristic algorithm typically is very quick, while the exact algorithm may take such a long time, okay? So somehow the heuristic algorithm is to try to sacrifice a little bit on the objective value to save you a lot of time, and that's the idea of heuristic algorithm. So coming back to knapsack, we now gives you a very intuitive greedy algorithm that actually you already see. So we first sought all the items according to their value-to-weight ratio from large to small. And then along the order, try to put each item into the knapsack one by one, wherever it is possible. And don't forget now this is an integer program. So possible means we may take 100% of that item. When this is possible, pick that item. Otherwise, throw it away and consider the next one. Now we really need to consider the next one. Because whenever one item is too large to be put with the residual capacity, the next item may be smaller and can be put into the knapsack. So we really need to try each one one by one until all items are tried once. Or until it happens that all the capacity has been used out. So recall our example, to take the order is going to be 3, 4, 5, 2, and 1. And then we're going to try item 3, item 4, item 5, and then we still have a few limited capacity is not going to be enough for items 1 and 2. So the reported solution would be (0, 0, 1, 1, 1). Also the solution here is not 0, 0.6,1,1, 1 is not, because this is not an integer solution. We are trying to solve this integer program, we need to find an integer solution. And in this case 0, 0, 1, 1 is a feasible solution. That gives us an objective value which is 8. So when we write ALG as the superscript, that means we are getting this according to an algorithm. We have zALG, that means the objective value obtained by the heuristic algorithm, okay? So this gives us a concrete example of a greedy algorithm, which is a heuristic for the knapsack problem. So the only thing remaining is to talk about the concept of optimality gap, which is the heart of evaluating a heuristic algorithm. Well, what's the issue? The issue is that, whenever you have a problem, you have a way to find an optimal solution. That's an exact algorithm. That's good, but also an exact algorithm may be too time consuming. That's why we try to do heuristic algorithms. But heuristic algorithm does not guarantee anything. So you may propose your heuristic algorithm, I may propose my uristik algorithms, and there can be only all kinds of hundreds of different heuristic algorithms. Somehow we need to evaluate which one is better, right? So the most intuitive way is to check their objective values, or say it in another way, we may check the optimality gap. So what's that? Well, in the previous example, the reported solution is (0, 0, 1, 1, 1), that objective value is 8, and optimal solution as we already know is (1, 0, 1, 0, 1). That solution gives us an optimal objective value, which is 9. So a very natural measurement of the quality or the performance of a reported solution is to see what's the difference between the two objective values. We obviously hope the objective values to be as small as possible, I mean a difference to be as small as possible. That is determined as the optimality gap. So in this particular case, we may have an absolute error or a relative error. So the absolute error is, of course, the difference. And in this case because this is a maximization problem, we're going to use the larger value which is z* to subtract this zALG, okay? The larger one is here and then the lower one is there. So if we subtract the ALG from z*, we're going to get 1, right? 9 minus 8 is 1. So that absolute error is 1, okay? We're not going to use zALG to minus the z*, that does not make sense. And then If you put this as the numerator and the original z* as the denominator, you are going to get the percentage error, in this case is going to be 1 over 9. So that's exactly 11.1%, okay? So that's very good. And now we know how to measure the difference between one solution and optimal solution. So that's good. Note that when we are doing the optimality gap definition, if this is a minimization problem, or suppose we are dealing a minimization problem we're going to use zALG to minus z*. That's how we get a positive absolute error. And also we're going to use that as the numerator, and use again z* as the denominator to deal with that percentage error. So that's how we get the definitions for a minimization problem. So we don't need to say whether you have a large objective value or a small objective value. All we want is to have small optimality gap.
