Video 6-4: Integer programs

0:03 In the previous sections, we've seen linear programs, how to model problems with them, and how to solve them. And uh there's one piece missing for many kinds of problems that we would want to model. And that's what we'll cover in in this section. And to motivate that, um remember so that many natural optimization problems actually fit the fit the uh setup of LPS. They have a linear objective function and linear constraints. For example, the the napsac problem that we've seen in the pseudo polomial chapter in in more detail uh as as the optimization problem. So there's items one up to n. They have some weights and they have values. I've written them here in vector notation because we're we're used to that anyways from LPS. And then we have a a weight constraint for the knapsack. And the goal is to select a subset of the items with maximal value but weight at most the constraint the the capacity. So you can easily write this as an a linear program where you maximize the dotproduct of of values and the variables where the variables are such that you set the variable to one if the item is included and you imagine it's zero if not. So the variable should be between zero and one and uh we want the napsac constraint to be satisfied. So uh each item um product with the weights is the total weight. You sum up the weighted the weighted weight well uh the weight contributed by each item in the set and that should be at most B. So far so good. But of course if you've seen this before then is clear.

1:48 Uh so we could use an LP solver to get an optimal solution an optimal X uh for this LP. Um but there must be some problem here because uh the LP solvers are polomial time algorithms. The NAPSAC problem is NP complete. So uh this looks like a um contradiction here. Um, and of course what's wrong is that the solution we get back from the LP solver might not make sense in the combinatorial problem. Specifically, it might not be an integral solution. When we set up this uh LP or when I set it up for for you, what what we really had in mind is that these XI should be either zero or one. You can either include the item or not. uh but the LP doesn't have that notion. It's it's a variable between zero and one but it can be any uh any real number and in particular it can can get really nonsensical. If for example you have just a single item that you can choose from but that item itself is already too heavy to uh to take then the actual solution must be zero. You cannot take anything. uh but for example if the the weight is is twice the capacity the uh integral the non-integral optimal solution that the LP will will spit out is just uh taking half of that item that still fits your constraint and it gives you half of its value. Um so in general the uh solution for an LP doesn't help at all in solving the the uh original um optimization problem.

3:30 in general means uh for some problems it doesn't help at all and the napsac problem is one where the difference here can be can be big. So um what can we do? Well, one thing is we can uh brush up the language of our optimization problems. So we can add the option to add integrality constraints. So the general form uh we've seen in the exercises the 01 version where you constrain the variables to be either zero or one. Um but uh you can also have the more general version where you just restrict them to be integers and um that's what we call an integer linear program. It's as a as before an LP but now the ILP adds this integrality constraint. Uh in full generality you can have a mixed integer linear program where some variables are continuous and some are discrete. So you would only uh have some of the variables restricted to C to the N. uh but here we'll focus on the case that all variables are integral. Uh that's the one that's most relevant for us. Uh it just is worth noting that the solvers that exist for solving these problems in practice um can usually deal fine with mixed integer linear programs.

4:51 If we go back to our napsac problem, um it's easy to turn the napsac LP into uh such a normal form ILP. You just add the constraint of integrality. And now we're modeling exactly the problem we had. If all the variables are supposed to be between 0 and one and integral, then they must be either zero or one. And then this encodes exactly the original combinatorial problem.

5:18 Something we haven't talked about at length before is the uh kind of general geometry of of linear programs. I wanted to at least drop this uh vocabulary here. A polyhedron polya the German word is the feasibility region of an LP. And this is essentially a a convex polygon in mult in higher dimensions. So formally it's just uh the intersection of half spaces in some n dimensional space. And of course uh for a specific LP given in in our normal form you can write this concisely as a set. It's a set of all vectors x so that they can satisfy the constraints. That's the feasibility region of an linear program. If you go to an integer linear program, you have to take that same region and take the intersection with the integers or the integer lattice in higher dimensions. And so it's just uh that that same P but uh intersected with Z to the N. That's a discrete set now. Um, and so we shouldn't expect the same kind of uh techniques to work, but we'll still um make some use of this.

6:42 Um, at this point maybe I I should have put this on the slide as well even though we've covered it before. Clearly uh solving integer linear programs in general is NP hard.

6:58 Basically, you've you've seen or uh well, we didn't do uh we didn't do the proof in the lecture, but uh the 01 integer programming problem was listed as one of Karp's original NP hard problems, nplete problems. Um so even the restriction to uh just binary variables is hard and that of course translates to the general problem. Uh and you can also uh um reduce easily many kind of problems to integer linear programming. There's one on the slide, right? We know the knapsack problem is NP hard. So if you could solve in general ILPS, you could solve this NP hard problem. Hence, uh, ILP is also NP hard. So we shouldn't expect fast algorithms in sharp contrast to linear programs. Also, what I said earlier about the practical solvers for integer linear programs, mixed integer linear programs, they do work, but not for such big problems. uh you can do some uh clever branch and bound algorithms for integer linear programs but uh I guess a few dozen to a few hundred variables might still be doable if you're lucky but that's much much different to the millions of variables you can easily solve even with um not super sophisticated uh LP solvers. What else uh what what can we still do despite the fact that the problem doesn't allow a general efficient solutions? One thing we can do is we can from from this uh obvious relation on the feasibility regions if we're minimizing then we'll get that the uh optimal objective value that the LPS piece fits out cannot can never be worse than what the integer linear program gives you just because all points that are feasible for the integer linear program are also feasible in the linear program. you're just dropping one constraint and so this is something we uh we can use to our benefit because again remember LPS can be solved quickly uh in in theory terms polomial time is is for free. So we can take a combinatorial one of the many combinatorial optimization problems that you can represent as an ILP and uh we can define its LP relaxation which is just take this ILP and strike off strike out the integrality constraint. Then you get the uh LP relaxation of this ILP.

9:47 I guess I should be a bit specific that you can often times model the same combinatorial optimization problem in slightly different ways. You can encode it in different ways as an integer linear program and so there might be different ways to get an LP relaxation and uh the specific LP relaxation is always specific to one way to model the problem and there can be uh more or less smart ways uh but for now let's uh um let's ignore that. So the the idea is that um it's a cheap way to get to get some lower bounds for the problem if it's a minimization problem. And this is this is indeed something uh we'll come back to.

10:47 Uh let's do a a small example to see this in action. Here's the uh independent set problem. One of the other many problems you can write as an integer linear program. Again to remind you, it's a graph that we're given and we try to find an independent set. So a set of vertices, subset of vertices that have no edges uh in between and we'd like to find the largest such set. Then uh we could model this as an integer linear program by giving each vertex a variable that's either zero or one. Is it included in our independent set or not? And uh then we can simply write this out almost almost um blows directly from the natural language formulation. We maximize the number of vertices that we can pick. They're between 0 and one. The variables there are zero or one. Um and then the constraints are for every edge we can include only one of its end points at most. And that we can write as the sum of the endpoint variables has to be at most one. Now because they're uh either zero and one this is essentially a a way to express the boolean or uh we can include one or the other but not both. So it's I guess it's with the lesser equal one. It's a a NAND.

12:02 And the uh linear program relaxation on the right just replaces the binary constraint with um upper and lower bounds. So the variables are still bounded between 0 and one but they not need not be integral.

12:24 Okay. At this point uh I want to introduce another uh name. Um we'll come back to this uh in in other places too. That's the notion of an integrality gap. And uh technically it's just the the optimal value that you get for the ILP divided by the optimal value for the LP. And the question is how far away can these be from each other. So this is defined for specific LP relaxation because you need to be able to talk about one ILP and its LP. But you can also uh gap of a problem. uh in which case people usually mean the the best way to get an ILP for that problem and an LP relaxation for that ILP is a is a bit less well defined u but you sometimes find this uh this language in in the literature we've seen some example early on where this was actually not a big gap our apple farmer um had this solution where uh he was told to build a fractional number of trees of this one variety which is not really possible. So if you uh round this down and and just give up that third of a tree the uh revenue goes down from 155,500 to 155,450. So you lose uh some 80 um euros but if you take the ratio it's actually a minuscule difference. So if the integrality gap is small, we can uh potentially use this, take the ILP for the problem, avoid uh the integrality constraints, solve it as if it was a continuous problem and try to make sense of that solution as we did here essentially by rounding and uh we can hope to get approximate solutions from that. And that's indeed something we'll revisit in a more structural way when we talk about approximation algorithms. Unfortunately, in general, uh the integrality gap can be really really bad. And here's uh kind of a cartoon of what this can look like.

15:01 Suppose you have a a small LP um with these three constraints uh in 2D. So the um purple region again is is the feasibility region. If you take the um integer version of that then only these two blue points are really contained inside the region. You have to zoom in a bit. Um also the exact numbers don't matter that much. But you see how if the objective function um improves in this direction, you can shift it all the way to this uh thin acute uh point here of the triangle to get a really good solution for the uh uh LP relaxation, but you're stuck at this integer point bar on on the on the left um because there's just no other integer point contained in this. So that's kind of a sketch why the integrality gap can in general be really big and that's even even for two-dimensional problems to convince you that this is is a real problem. Uh let's look at the independent set problem. Again we've just seen the um formalization right here the two the ILP and the linear program relaxation.

16:19 So we had a constraint for each of the uh edges and the variables are just between zero and one. Now the bad case occurs if you think about uh a huge complete graph. In a complete graph the only independent sets we have are isolated vertices single vertices because whenever you pick two vertices they have an edge. uh but what happens in the linear program is we can still satisfy all those constraints by setting every vertex to 1/2. So we pick every vertex half into the independent set in this uh fractional version. We satisfy all the constraints. Uh but the solution is completely meaningless and what's worse it's optimal objective value is is n times 1/2 uh which is far away from this uh value of one that you get in the integer program. So you can think of uh this is the highdimensional version of this picture on the left where things get completely out of control. you have no no bound on the integrality gap in the in the worst case in general problems. So it's not a magic silver bullet that somehow solves things automatically.

17:38 Um but I'll point to that unit 12 uh where we'll see for some problems this is indeed helpful.