Video 6-5: Integer Linear Programs
CS 627 – Advanced Algorithms (Winter 2026-27) · unit page
· YouTube
2026-11-16, 17:43
The transcript was generated automatically by YouTube's speech recognition and is offered as is. It may contain errors, in particular in concerning technical terms, names and formulas.
0:02 In the next section, we'll look at integer linear programs essentially the same as we've had it with an additional constraint in the variables and the motivation is that often times when we start from optimization problems uh like the ones we care about they are discrete in nature. So for example we can model the knapsack problem easily as a linear program. I could have a variable for each of the u items and we can say the variable should be one if the item is included and zero if it's not included then I can say the value I the total value I get is just uh this sum right which is zero for the items I don't get don't take and one for the items I take so sum up their values and I have this one knapsack constraint namely for all the items that I take the weight should be in total less less than our capacity this this B. Now if you just write it like this nothing stops the optimal solution from picking fractional items.
1:05 All we require here is that each x i is between 0 and one. And we could do this now um to see that uh well first of all if this would work right we we would solve p equals np. So likely there's a catch. And of course the catch is uh that some of these formulations don't have an optimal solution that is integral where all of the variables have some some integer value. And so um it may not help much here. It seems all the nice theory we've just covered.
1:44 You can still define it away to be useful. If you add this additional constraint that acts is only allowed to take integer values, then we call this an integer linear program for the obvious reason. Uh in principle, you can even have a mixture of variables that are uh forced to be integral and and real ones. Um we don't specifically need that here. Uh so all our variables are integral and then we have this standard form for ILP an integer linear program for our napsac problem. It's as easy as it gets. It's precisely what we had on the previous slide with this additional constraint that they should all be integral. And then this truthfully captures exactly the knapsack problem, right? is a a perfect encoding of this problem. Now uh for the LP we had all this lovely geometry in particular the feasibility region was just the intersection of half spaces. So uh poly polytope or unbounded polyhedron uh given by the line linear inequalities for an ILP well it's the same but taking the intersection with the integer lattice that makes it unfortunately a lot more tricky trickier to work with.
3:11 um in particular. Maybe let me dare to open this. So I suppose here is again our um our famous most uh loved problem and I can make this um find the optimal solution. This is the best integral solution. This is the best grid the best LP solution. You don't even see much of a difference. If you zoom in you do see the difference. It's tiny but it's there. Of course, the actual LP optimal point we got before, we remember had this third of an apple tree. The best actual solution is slightly down. So, we could just round the solution we get in this case. Now, this doesn't always work because rounding could also give you a point outside the feasibility region. This is the main problem why ILPS cannot easily uh be turned into this fractional LP and then still get something uh non-trivial out of it. Okay. So well we halfway expected this.
4:36 Um we've also proven earlier that solving ILP is NP hard nplete right one of the uh you proved did you prove this? No we were um you did a reduction in the exercises I think. Yeah, even though it's strongly NP hard, what we still get for free, and this is more profound than it sounds, uh the optimal objective value of the LP in a minimization problem is never larger than for the ILP. Well, obvious because I'm just adding another constraint that can only kill some solutions. So um okay a bit annoying in in the example here it's maximization it's the other way around uh but still the optimal value you get with any of the integer points is never going to be better than the bounding box around it. Now again obvious uh conclusion from the way we define things. Uh why is that useful? I think here um it's maybe useful to take a step back and think about what's what makes NPcomplete problems hard. Maybe uh insert that here as kind of a little philosophical aside.
6:16 And of course uh you can give many technical reasons like they somehow embed a sub formula and so on and so forth. What I mean here is this very verification view. If I give you a solution, a feasible solution, it's easy for you to check and evaluate how good it is in the optimization world.
7:08 I guess uh let's say if I give you any solution, I may promise you it's feasible, but you don't trust me. But you can insert it into your inequalities and check. And that's easy. So if I ask you to find uh the optimal tsp tour, I don't know, from here to the cafeteria down to the cinema and back and a few stops in between, you can come up with an order in which you want to visit the stops. I can check what the cost is. And so if you claim that takes me uh 35 minutes, I can check and say, "Yep, you're right." Now, if you say, "And this is the optimal solution." I'm a bit out of luck. All I can take is your word for it.
8:05 All I can really do is try to further improve it and fail. That's not very constructive. And we know for nplete problems ultimately this is a problem that I cannot really certify um in the same in the same uh complexity and that's precisely what LPS give us. Um if you relax the problem you take the TSP problem and make it a bit easier you allow it to somehow cheat. Now for tsp there is a specific way to do that but let's maybe at this point not get into it. you somehow make the problem a bit easier by allowing say to take two subours that are not connected and say that's is that's a feasible solution in the LP I can check that it's feasible there and then I know uh your integer optimal solution can never be better than this LP solution so it may not give optimality but at least it tells me okay your solution is so quick and 30 minutes is unbeatable So you may at least know a range that gives you um a threshold beyond which you cannot improve. And if you're very lucky, you can even make the two coincide.
9:16 Again, in the worst case, this is not going to work because it's an NPcomplete problem. For specific instances, surprisingly often, it can work. And what's behind this a bit more structured is is the idea of LP relaxations. we really care about the integer version, but that's hard to solve. So, let's just forget about the integrality constraints and see what we can get. And that's all that's behind this this fancy name. You take your ILP and you forget that it was integer constraint. Um, here's one example just for make it to make it concrete. Say the independent set problem in a graph. You can model this as a an integer linear program. In I would say the obvious way every vertex can either be in the set or not the independent set. So you have 01 variables. You want to have the largest independent set. So you maximize the sum of these axis. And the constraints are such that well if I have an edge between two vertices u and v u and v and w uh at most one of them can be used.
10:24 They cannot both be in the alleged independent set. And uh with the integrality constraint that's a truthful embedding of independent set. This is precisely the same. Now I can uh just drop this constraint with well here it's um several constraints in one right uh I give a range at least zero at most one and I say it's integral. If you relax it to being just between zero and one but any real number is fine then you get the LP relaxation for independent set.
11:02 What I said earlier with especially with this um bounding right this is a relaxation this is an easier problem than the one on the left. So any optimal solution on the left cannot be um better than the optimal solution on the right because here I'm allowing extra solutions. So this one I can solve and it tells me an upper bound for the thing on the right. A better this is a maximization problem. So uh it tells you an upper bound for the size of your independent set. That sounds useful. Uh unfortunately it's not always useful.
11:40 Um, that's the last thing I want to show today. Uh, let's play a little game here. Here's um a little graph and let's try to decide um let's try to find a vertex cover for this not independent set. Uh we could all independence set is a bit is a bit cleaner. Let's uh um vertx cover is a bit cleaner. Let's stick with that. Um how would you pick a vertex cover for this graph? Smallest vertex cover of course.
12:36 Probably doesn't matter. Okay. So um we've certainly found a solution of size three. That's an upper bound for the optimal solution. Is this optimal? How shall we know? Well, uh of course you could say we try every possible solution and pick the largest. For this small example, you can do this. Now not in general. What you can also do is take the LP relaxation. Uh it's a bit small maybe. Um that was a bit too large. This is the integer linear program for vertex cover. Very similar as for independent set. I have a variable for each vertex. They're between zero and one. I want to pick a subset. And now for each edge I have to pick at least one of the end points. So almost the same as independent set just the the sign is flipped and the the relaxation just drops this integrality constraint only between zero and one. If you solve this with an LP solver, what you get is this one. So the red one are the the optimal solution values, right? And it it tells you for these triangle vertices. Aha, pick just half of each and you're better.
13:51 you achieve optimal objective value 2.5. Of course, there's no vertex cover with 2.5 vertices. So in this specific case, you can even say I have to round up kind of right. This is just on the objective value, you're already done because I never can achieve 2.5. So three is the next closest I can really do and I got three. So I'm I'm done. So even though there is a gap between the optimal value and the ILP opt sometimes that's enough to reason that your solution was best possible. Now again this will also not always be the case uh because sadly you can have uh things like here. So here in our in our uh apple example the difference between the two solutions integral and LP opt was tiny. Just leave out the third of the tree out of 100. So and so it doesn't make a big uh difference. Um so I wanted this one.
15:00 It can be almost arbitrarily bad though in the worst case. Um if you have grid points only here and just this tiny LP with these three constraints and the direction of improvement is is such as it's shown then uh you can find the best integrate point here and the best uh integer grid point here and the best uh fractional point far away from that. Intuitively, I think this narrow triangle tells you why this could be arbitrarily bad. You can make this worse and worse. So, that's something you have to deal with. Um, this concept is called the integrality gap between an ILP and its relaxation. Uh, for our example here, it wasn't big. Um, we'll revisit this concept when we talk about approximations. There's the example again. um and is not just hypothetical. You can think about that for independent set precisely this happens.
16:20 Okay. So, um we have this uh good and bad impression of maybe linear programming. Uh number one, it's powerful to express problems in. It's just a good way to model things and sometimes you can just reformulate in the language of LPS and make your problem a bit more minimal to analysis. Second, it sometimes gives you these you cannot do better than X guarantees which are very strong sometimes and uh that I think is also why it stands out as a technique for designing algorithms. I don't know of many other techniques that do that. Sometimes you can do ad hoc techniques in a problem that come down to essentially the same thing in disguise. We'll see another more powerful notion LP duality for those who've seen it uh in the approximation chapter where you can take this a bit further, take it to the next limit if you wish, to the next level if you wish.
17:19 uh but but LPS here have this really nice certificate or kind of uh sometimes optimality uh certificate notion. Um, on the other hand, they have sometimes a huge gap between what you really care about and what they can tell you. And so it seems a bit brittle.