Hello everybody, my name is Andres Fielbaum from TU Delft and I'm going to present you a paper that we have written with Ina Simorales and Jose Verchay that presents a primal

dual algorithm that has a very neat water-filling interpretation and that's useful to approximate some non-linear extensions for classical covering problems. So in order to pose the problem and to see how its inspiration but also the formal

definition, let us start with a practical application. So imagine that we have a street that goes in this direction and we have some users that need to travel within the streets. So always to the right. So DUB is the number of passengers traveling from node U to node B. If we know this, then we can straightforwardly compute the number of passengers that's going

to traverse each arc that's connecting two consecutive nodes, which is basically the number of travelers that are going from here to here. So that's the demand that we need to serve with a transport system and to do that we have a public transport system that we can optimize that's composed by potential

bus lines. So each bus line has a cost, it has a capacity, meaning the number of passengers that it's capable of carrying and an interval which is basically it's root. So that means that line I, line one for instance case, starts here and finishes here.

So they only cross a sub-interval of the whole avenue that we are modeling. So our objective is to select some of these potential lines, a subset of these potential lines, such that we are able to carry all the demand that's crossing each of the arcs

at a minimum cost. Well this is a problem that has been well studied and it's called the unsplittable flow cover on a path. So this problem is NP-hard. Some 20 years ago it was shown that it admits a forward approximation and it also

admits a quasi-paranomial epsilon approximation. This is a little more recent. So a natural extension, a natural question is the following. What happens if instead of giving exogenous capacities, we can decide the capacity? For example, we can decide the frequency of each line or we can decide the size of

the buses of each line or whatever. In that case, we are to select which capacity are we offering per line and for each capacity we have a cost and the only thing we're going to assume is that this cost is increasing. So if we are to offer a higher capacity, a larger capacity, then the cost is also going

to be larger. But it can be non-linear, non-continuous, et cetera. And it's actually a well-known fact from public transport theory that these functions can have concave regions and convex regions, et cetera. So one specific case is the non-linear knapsack cover.

We are going to focus in all the presentation in this problem. Although our most interesting theoretical results apply for the unsplittable flow on a path problem, the techniques and the algorithm we are proposing is already well explained in this scheme, which is simpler so it's easier to explain here.

So the non-linear knapsack cover emerges basically when in the previous problem we have only one arc, but it's much easier to describe it by this way. So we have n items. For each item, we can select its capacity again and we need to cover a demand.

So we are minimizing the total cost such that subject to the fact that we are covering the whole demand and of course, positive capacities for each item. So this problem is non-linear and non-convex because f is non-linear and non-convex.

So some observations. The classical knapsack cover, so recall that the classical knapsack cover means that we, for each item, either we select it or we don't select it, it's a special case. And how's that? Well, we can consider this cost function that takes the value zero if the item is not selected

and it takes the value ci if we select any amount of the item up to its capacity. So if we select a little, of course, we are going to select all the capacity because we are paying the same. So in that case, we just need to decide for which items are we taking the capacity,

which is the classical knapsack cover. So in this case, we need to take these binary variables to decide which items i are we taking. So our problem, the non-linear extension is NP-hard because knapsack cover is NP-hard.

So then how can we relax the knapsack cover? This is relevant for us because we are going to work with a primal-dual approach. So we need to consider a non-integral version. So this is something that has been proposed a lot of years ago,

but it's relevant for us to recall it because we are going to use the same techniques. So these are knapsack cover inequalities. So this is the binary version of the problem. The first thing we could do is, okay, instead of considering binary variables, just take continuous variables. Well, it's easy to see that this is a very bad idea.

Just imagine that you have only one item with a huge capacity. So you can take a small portion of it in order to cover all the demand. But of course, with binary variables, you could not take a small portion. So this is the example and the integrality gap is as high as you want.

So you can say, okay, but this is silly because why would you consider items with a capacity higher than the demand? So just truncate all the capacities to the demand. Well, actually, if we do that, we end up with exactly the same case that we have just described. And why is that? Well, now we need to consider two items.

So the first item has cost zero and covers almost all the demand, but epsilon. The second item then... So the second item, of course, just need to cover this epsilon. What I want to say is that any reasonable algorithm will begin taking item one that has cost zero.

So basically, our problem consists on how do we cover the remaining epsilon demand with item two. So again, we have an item whose capacity is huge in comparison with the demand that we need to cover. So again, the integrality gap is not bounded if we use this relaxation.

So in order to face this problem, to overcome it, the knapsack cover inequalities were introduced some 20 years ago. So we are going to have an exponential number of inequalities, one inequality per subset of the items.

So what is the idea? Imagine that we have already taken, we have already decided that these items in A are going to be part of the solution. If that's the case, then the remaining items, those that are out of A need to be able to cover the residual demand,

which is all the demand that's not covered yet by A. And this continues to be true if instead of considering the whole capacity, we truncate the capacities, but with respect to the residual demand, not to the whole demand. That's the main difference with the previous example

that we are considering the residual demand here. This has to be larger, not necessarily equal, because in the end, maybe we are not taking all these items, but we have at least to cover the residual demand. And this is for every A that's a subset of M. And a theorem from the year 2000 is that the integrality gap

for this, inequalities for this linear formulation is two. So this is working well. So what are the main results in our case? Well, we are providing an approximation algorithm that is two plus epsilon for the non-linear knapsack cover, and that it's four plus epsilon for the non-linear

and speedable flow problem on above. So you can see that it's quite nice because we are only losing a factor of epsilon, and we can consider any function. We're not going to require any kind of hypothesis about it,

only that it's of course increasing or non-decreasing. So what's the main difficulty? Well, this is the general case. So imagine that we have two items. So if we wanted to buy, we need to cover a very small demand, then the second item is much better, because at the beginning it is really, really cheap.

But if we need to cover more of the demand, then the first item starts being more attractive, because although the first part is expensive, then we reach another segment that are really, really cheap. So maybe it's worth buying or taking this part to our solution in order to reach this cheap, superior segment.

So basically the question is the trade-off. When is it a good idea to start buying expensive, inferior segments of an item or inferior components of an item, when the superior ones are really, really cheap,

when in the end we reach parts in which the function increases really slowly. That's the main question. So in order to study this problem, we are going to do it in this presentation in a simplified scheme. You can see how to generalize it in the paper.

Actually in this scheme, we do not lose the epsilon, it's just two and four. So what we are going to assume is that the function is piecewise linear, and moreover, that all the pieces have a width one. So basically each of these segments of size one has one cost and that cost is g i1, g i2, etc.

And we are defining new variables z i key, which are zero or one, depending if we take the segment k of the item i or we don't take it, one or zero. So the Excel formulation is this one,

the binary formulation. We have to sum the cost of all the segments that we are taking. We need to cover all the demand. And if we are going to use the segment key plus one, then we need to take all the previous segments of the same item.

So basically if we want to take this segment because it has cost zero, we need to take this segment before. The knapsap cover inequalities now look a little different because we are not considering subsets of the set of items that are taken or not. For each item, we need to see

how many have we taken yet. So for each a, that's a vector that has one coordinate per item, each a is telling us how much have we taken so far. So in this example, we have taken two of the first item and zero of the second item. And for each a, we need that the rest of the items

are enough to cover the residual demand. And again, we are going to truncate with respect to the residual demand. So if the second item, so in this case, the total demand was five. So the residual demand is three. So in the second item, if the second item have a capacity of four,

well, the fourth segment is now out of the problem because we are never going to take it. So now we are only going to look at these three segments. So how can we cover the residual demand three? We can take theta one three, theta one four,

theta one to two to three. And instead of considering that theta one four has to be, theta one three has to be one in order to this guy to be one, we are going to replace this by inequalities. So to cover three,

what we covered with item one and what we covered with item two, this is what we covered with one and what we covered with item two. And instead of considering the inequalities between theta one four and theta one three, we're not going to require that theta one four is not larger than theta one three. What we're going to do is to replace theta one four

by this mean. So please note that when we optimize, it is exactly the same because you will never take theta one four larger than theta one three, because it makes no sense. Because eventually in this minimum, in that case, we're going to use theta one three. So you will be paying more than what you could pay.

So it's the same. And of course, the same thing is valid for the second item. So these are the linear inequalities. So the second item has this, the contribution of the second item has this form. And what we're going to do to linearize these minimums

is to consider a bunch of new inequalities. So this is the first one. So the contribution of item one, plus we are selecting these variables at each minimum. So plus theta two one, theta two or theta two three.

A different inequality is to consider theta two one, theta two one again, as theta two three. So now in this minimum, we are selecting theta two one. It's iterate, it's iterate. So we have now a lot of inequalities because we are first indexing by A. And for each A, we need to consider all the possible selections of this minimum.

So it's really, really exponential. And the relaxation looks like this. So we need to minimize the cost of the segments that we are taking, subject to the fact that we are covering the residual demand for all A, so all A we have already explained

and F basically is showing how we are selecting the indices in these minimums. The exact meaning is not relevant, so I'm not going to say it. Of course, it is detailed in the paper. What I want to focus a little is in this tau. So tau is the number of times the variable zeta ij appears in the inequality.

So in this case, the three zetas has tau equal to one, but in this case, tau for zeta two one is two, tau for zeta two two is zero because it doesn't appear, and tau for zeta two three is one.

And the straightforward computation gives us the dual. So the dual is basically interchanging the constraints for the cost parameters. And we are highlighting this G here because it's going to be crucial for the filling water algorithm

that we are going to explain now. So we are going to explain it with an example. So imagine that we have a total demand of four, and these are the two items that we can select from which we can select some segments. So at the beginning, so we have one bucket per segment.

Each bucket has a capacity or a height that is equal to the cost of the respective cell. And at the beginning, all the buckets are receiving water, and they are all receiving water at a rate of one, basically because tau is one.

So the relationship between the primal-dual and the filling water is that the filling rate of the buckets is exactly tau. So at the beginning, they are all receiving one. And what happens? Well, these four buckets were the cheapest ones, so they get full very quickly. So what happens when that's the case?

It means that in the dual problem, these inequalities became tight. So we need to update A or F in order to keep feasibility in the dual. And in this case, we cannot update A

because we cannot take these segments as these buckets are not full yet. So we cannot take them. So what we do is to update F, and updating F means that we are updating the taus. So what we are doing is that we are going to change the filling rates, but the nice interpretation is that now these buckets are,

the water that is splitting over these buckets is poured over the inferior bucket. So the water falls here, but because this one is full, the water splits to the first bucket. And from here, it splits here and then there.

So now this bucket is filling at a rate of three. The same happens with this one, and this one keeps a filling rate of one. And these buckets are full, so they are filling rate, of course, is now zero. So before we continue with the algorithm, please notice that the trade-off that we were talking about some minutes ago is clearly faced here,

because when we want to take D11 to reach these cheap buckets that are above it, well, basically when it gets full, not only with its water, but with the water that it's falling precisely from these cheap buckets. So that's why the interpretation,

we like it so much because you can really see that having superior cheap buckets is going to increase the filling rate of the inferior buckets, and they are going to get a full faster. So what happens now? Well, the following bucket that becomes full is this one with the water from these guys also.

And now we can take this bucket because it's the first one. And if we are going to take it, of course, we also take this one and this one because they were also full. So now we have taken three buckets, A is three comma zero, and the residual demand is just one. And because the residual demand is just one,

these guys are now out of the solution because we truncate the capacity, the remaining capacity of both items. But in this case, that doesn't mean anything. These buckets, of course, stop receiving water because they are already in the solution. So that would be meaningless. And so again, this guy has a filling rate of one,

and the same happens with this first bucket. But the water from these buckets remains here, okay? So what happens now? This bucket becomes full before this one because the remaining capacity here was lower.

And we take this bucket, so the final solution is three comma one. Please note that actually this cost was lower than this cost. So why did we take this bucket first? Well, because the water from these buckets during some period of time poured here,

poured onto here, and that encouraged the algorithm to select this bucket instead of this one. So basically not choosing these buckets is something like an empty promise. We filled this bucket quickly in order to arrive to reach to these superior buckets,

but when we took this bucket, it was already too late, and these buckets were meaningless because they were not necessary to fulfill the residuality. So that's the algorithm. The main lemma that we proved,

the approximate complementary slackness, is that, okay, if a dual variable is positive, then, well, this is not equal, which would be the traditional complementary slackness, but it is not so far from being equal. So that's why it's approximate complementary slackness, and this is a standard way to prove

that the primal-dual algorithm is actually an approximation. And how do we prove this? Okay, just an intuition. Well, this sum here is the filling rates

of during a stage of the algorithm for a particular A and F, for all the buckets that are in the final solution, because their zeta is one and not zero. So the filling rate of these buckets is the sum of the filling rate of the buckets

in the final solution of the last item for which we included some segments and for all the other items. And what we show is that they are both bounded by the residual demand. Why is this? Well, in all the other items, this is true, because all the buckets that are pouring

onto the ones in the final solution are also in the final solution. So they are a subset of all the buckets that are finally taken, which is D of A. And in the second one, that's true because in one, only one item, this is always lower than D of A because of the truncation.

But in the second item, some pouring buckets are not in the final solution. So in our example, in this, this is the first item that the first sum that we are bounding by D of A.

So this is actually three. And why is this? Because the three buckets are in the final solution. So this is always lower than four. And in this case, it was lower than four because the filling rate is always lower than the residual demand. But as we said, there were empty promises here.

The nice thing is that we are able to show that the empty promises here are not that bad because we end up with two approximations. So I think this is again of our main results. If you can see, they're not the simplified version

that I have just shown you, but generalized version for each increasing function, then we only lose a factor of epsilon. And in the unspeakable flow on the path, we achieve an approximation that is 4%. So thank you very much for watching this video. And I hope to see you in the questions and answers

session in this iCalc conference in this very weird times. So take care and see you there. Bye-bye.