Video 2-9: Optimization problems

0:00 [Music] uh in the last section here um I want to come back a little bit to the different notions of problems that we've been talking about. When I was explaining the problems in the last section, you may already have seen that sometimes um I didn't explain what's on the slide, but I explained the more intuitive optimization version. And so um let's let's pull that straight because this is something that's often relevant and there's a few little details to point out um to make sure that we're uh that we can deal with optimization problems in the same way. Uh so so far everything has be a decision version. a problem was a language and then something can be in the language or not or uh to say the same thing you're given an input and you can say yes or no. Um it it does make sense to also define the more general problems where we try to find the best possible solution for the hardness uh theory will stick with the lang with the decision versions. Uh but there's an an easy way to uh put the problems into context and and connect them and that's what I want to do in this in this part. So formally an optimization problem uh has a bunch of of different components. There's an input alphabet.

1:26 We somehow have to encode the input again. But this time we also produce an output. So we also have to say how that looks like. Uh then there's a certain language over this input alphabet of allowable instances. So these are valid encodings of some problem. [Music] Um again if if we want uh to make this uh more concrete say we look at TSP as our running example again then the allowable instances would be distance matrices and the input alphabet would be some way to encode the distance matrices. Maybe it's just a binary alphabet and we write down the numbers in binary. Maybe we allow a third symbol to say this is the end of one number and the beginning of the next. Makes it a bit easier to to read. Uh then um maybe not all of these instances uh are really uh relevant for this problem. I guess for TSP the two would be the same but maybe you want to restrict uh TSP to a certain variant. Uh to make this clear here let me say it's metric TSP um where the distances have to satisfy the triangle inequality. So it has to be when you go metric means if you have cities here ABC and you go from A to B that cannot take you longer than going from A to C and then to B. So the distance from A to B should be at most the distance to go via C the detour.

3:29 Okay, this is a very natural condition. But if you just specify a matrix of numbers, this is not guaranteed, right? It may not be satisfied.

3:42 [Music] Um, I didn't want to zoom. Okay, so in general this may be violated but let's suppose we look at metric tsp where we only allow instances that satisfy this. So the actual problem instances would be metric distance thereof. And now you already see we need some way of uh checking that something is an actual instance. Uh then um we have this function n that tells us uh what are possible solutions for a given instance and uh these have to be defined uh for all of the allowable instances. So for TSP this would be all possible around trips limitations of the cities. Okay. And then we have a a cost function which uh given some some allowable problem instance and a solution. where this is uh one of the possible solutions tells us what's the cost of this and I keep the terminology neutral because we can use the same for minimizing and maximization. Now cost sounds like you want to minimize but uh well depends whose cost I guess uh the important bit is this has to be a function um that's uh computable we'll come to that. So this is so far this is a a general definition for any kind of optimization problem. Uh there's no mention at this point about efficiency and how fast we can do things.

5:55 Okay. Okay. And in general this cost function can be any real number. Now good luck with representing exact real numbers on your touring machine. So probably it will be rational or maybe even an integer. Okay. And the goal is minimization or maximization. So clear so far. Now in general this is uh it's a very broad definition. Um what does it mean to solve such a problem? We're given such an optimization problem. Then we say that a solution some Y in the solution set for X is optimal. If the cost of this specific Y minimizes or maximizes depending on the problem, right? Goal is this uh part of the input uh minimizes or maximizes the cost among all possible solutions for this instance. That's the very natural definition. Okay, an optimal solution is one that minimizes cost if you're minimizing and maximizes reward if you're maximizing. Okay, we we'll always deal with consistent algorithms. An algorithm is consistent with a optimization problem if it always puts outputs something that is an allowable solution for this instance. Again, in principle, if you specify an arbitrary program, it might do whatever nonsense. um we're not usually interested in this. So consistent means it has to be in this in this set of possible solutions. But the important bit is an algorithm solves this optimization problem if it's consistent and it all outputs the optimal solution for all instances. Okay. And here um let me stress again we're only u requiring this for the actual instances.

8:06 Okay. Uh we've seen many examples in the list previously where we had a threshold usually called K. And if you uh say I'm not giving you this threshold but I'm asking for the best possible solution then you naturally get an optimization problem for many of the problems we've seen before. And we can very briefly run through back uh closest string you can ask what's the smallest K so that you can find a string satisfying this max cut you optimize for the the many number of edges here you want to maximize uh exact cover is different there's not really a question of maximization um maybe you can ask for the fewest elements but this problem remains hard if if it's as is uh t SP of course you can minimize the cost of the tour. You can minimize the number of colors you need for graph coloring. Minimize the number of sets and set cover and minimize the cost. Uh dominating set. So most problems are actually like this that they're optimization problems. Hamiltonian cycle is an exception and exact cover is an exception. All the others are optimization problems naturally.

9:25 Uh here's a somewhat less immediate example, but one that will also come back at some point. Um the maximum satisfiability problem. It's a bit awkward, but it has technical reasons why why it's useful to look at. So let me introduce it here. Um we're given a CNF formula. So conjunctive normal form. This popped up earlier, but um I skipped over that part. So let me say it again here. It's a a form a boolean formula. So something comprised of of variables and and or not conjunctions. Uh but it has a specific form here. It's one big and of different parts. And then each of these clauses each CI is uh some X I or not XJ or X K and so on.

10:17 Um you remember three set was exactly three of these variables or literals. Uh if we just say C and F it's un unrestricted. Now the total number of variables is N. Um now max asks to satisfy as many of the clauses as possible. Normal satisfiability means all all need to be satisfied because we take the and uh but here we're asking just to satisfy as many as possible. So formally this would be uh the allowable and actual instances are all the encodings of such formulas um maybe listing the clauses in some form. Uh then solutions are assignments of all the variables. So you can write them down as 01 strings where the i position gives you the value of the i variable. And then the cost of a of a combination of an input and a solution is the number of clauses that are satisfied. Here's really a reward not a cost, right? Because we maximize. Okay, is the problem clear? As a boolean formula, this is a bit nonsensical like either the formula is true or not. It doesn't help to satisfy all but one clauses. But let's um let's pretend it's still useful and it'll come up as a reduction part here later. Yep.

11:41 This is a conjecture for and we are finding next set and everything is at how can others not be true. Yeah, that's what I said as a boolean formula. It doesn't make sense but you can still define I want to satisfy at least as many of the clauses. Uh again this is a bit of a um an artificial problem. Um, but it turns out it has for forget about the the meaning of the formula. Maybe it's just different conditions and you'd like to at least meet as many of them. If it's not possible to satisfy everyone, you want to make as many people happy as possible. Um, but it's yeah, it's a bit unnatural, but turns out to be a a useful intermediate problem. Okay. So uh so far optimization problems were very general. Now let's try to pin down um the the efficiency. Um do we have NP first? Yeah. Okay. So uh the first restriction is the equivalent of of NP and NPO is the equivalent optimization problems class.

13:01 Uh so these are optimization problems where first of all I can efficiently decide whether an instance is one that I'm actually interested in. So these were the actual instances. If I can't even if you give me something and I can't even efficiently tell whether I'm allowed whether I'm supposed to solve it, it's a bit pointless. So formally this is um ENP. Um and second there must be an efficient way to decide whether something is a solution. So um there's some polomial uh and for every allowable instance and for every possible solution first of all the solution shouldn't be too big if I were asked to produce solutions that are exponentially long there's no way I'm I'm going to do that efficiently. Um and secondly, uh there should be an algorithm that decides for all short enough strings whether or not that is a valid solution. That's also just a sanity check really. So if if someone claims here's here's an in here's a a TSP input and here's a a round trip, you should at least be able to check whether the round trip is is a correct permutation of the cities. Otherwise, we're completely lost.

14:23 But these are still very weak requirements. Uh the last one is is also important. The cost has to be efficient to be computed. So again polomial time also very natural. If I can't given some input uh tell you how how costly it is how am I supposed to optimize for it? Okay. So these are all very weak requirements. That's all for a class to for a problem to be an NPO. In particular, it tells you nothing about how to find the solution. But that's the same for for problems in NP. Uh the the problems where we have a a chance to solve them uh is this class PO. So here it's everything that NPO requires all of these three plus there should be an algorithm that in polinomial time computes an optimal solution. Okay. And then together with this I can also verify that it's indeed optimal if I'm if I'm asked to. I think most of the definitions is very natural is is what you would think.

15:35 uh NPO is all the problems where I can at least verify that the solution is correct if you give me the solution already and PO is the ones where I can find it efficiently without being uh requiring your your help to start. Um so it's not not very surprising how these things are formalized but uh I think it's it's worth doing so that for example you don't forget that the cost has to be efficiently evaluable and so on. It's easy sometimes to write down a problem that sounds enticing to solve but this not even in NPO because you can't even compute the cost for Okay. Uh at this point I think it's it's worth uh recapping the different types of problems we had um specifically because we had the Turing machines with their languages and NP in the original definition um but then also this BP definition and now we have optimization problems. [Music] Um so I would organize this as what is the output either we just do a a single value yes or no or we have to provide uh a solution or a certificate.

17:13 And the other axis is whether we're checking a given threshold or whether we have to find the optimal value. And so what we've just defined would be the the bottom right. These are optimization problems. I'm given nothing but I'm supposed to find the optimal value myself and also provide a a certificate of solution alongside with it.

17:59 Right now uh the other extreme was the decision problems. This is where we started. That's the same as languages. So here we're just given a string and we asked yes no. Now we've also had um this corner below here which is sometimes called the search problem. Uh so this is effectively um what we wanted for VP. Um I'm I'm still asking a yes no question. Uh but instead of uh I mean VP requires this as input. Instead of just uh claiming yes no I'm I'm supposed to prove that my answer is correct. And so you could say uh this is the problem in uh satisfiability. I'm asked a yes no question. Is the formula satisfiable? And then the decision problem I said yes and you were happy with that. Now in the search problem I say yes. And then you ask me okay fine what's the satisfying uh assignment?

19:18 Okay. And this corresponds to the optimization problem how we defined it on the previous slides. where I'm also supposed to provide you with the concrete uh concrete answer. And then the last bit um also sometimes makes sense to talk about and that's often then called the evaluation problem. Uh that's an optimization problem. You're not actually interested in finding the optimal solution itself. You're just asking for the threshold. uh what's the best possible cost that you can achieve but I don't have to provide you a proof I don't have to provide you the the solution itself okay and so uh the reason why I'm I'm drawing this uh this matrix is that you can go from one collection of problems to the other and some directions are easy for example you can always uh go this direction essentially by using that the cost function is efficiently computable and otherwise by essentially forgetting the certificate. Right? That's easy. If you can solve one of the bottom row, you can solve the top row by just not outputting the certificate. Um the interesting question is whether you can go top down.

20:48 Uh the other thing you can also do very easily is this easy right if I if I'm given a threshold and I can find the optimal value I just check the optimal value against the threshold and output whether it's better or not. Uh the interesting bits are can I go from left to right and then you can basically always do a binary search for the right cutff point. So you can use as a black box that you can decide whether something is above or below the threshold. You can use a binary search on the numbers that make up the cost function uh to at least get us as close to the optimal value as possible. And uh if the cost function is efficiently computable, it can't be an arbitrary real number. So you'll you'll have to converge eventually. Um it's also true because the number of possible solutions is not arbitrary. They have to be bounded in size, right? Uh so this this uh this works. And even though the search space is is very big is exponential you're taking binary search you're taking the log of the search space. So that's that's back to [Music] polomial. So that's actually a general reduction um specifically if the costs are discrete.

22:48 Now an interesting question is uh whether we can go from top down from threshold search. And in general it seems this is not always possible but it for uh for any concrete problem you look at it seems usually easy. So uh you look at this on on the tutorial [Laughter] sheet but most of the time you can do it. So if you put this together by and large all four uh corners are are not as far away from each other. In most problems the complexity of those four corners is the same in terms of polomial versus uh exponential. Okay. Uh questions on this on this terminology. Is that clear?

24:14 uh there's there's even some uh depending on on who teaches undergraduate modules sometimes people work everything from search problems um I don't know if anyone has uh experienced that is it's not so uh commonly done okay a few of these things um there's a few definitions that formulize some of what I've just Good. Um I'll go over those bit a bit more quickly. Uh so if we have a an optimization problem in the way we've defined it before then um let's denote this is I guess in general so worth worth pointing out. uh I'll write opt subscript the problem and then an input so an instance x with the uh the value of the optimal cost. Uh then we can define um threshold languages which is turning an optimization problem into a decision problem uh by using pairs of an input and a value a threshold and then you include in the language all the pairs where the optimal value is better than the threshold and you have these two distinctions for for min and max. Uh the only thing here worth pointing out K subscript 2. This is supposed to mean the string K is a binary string and so I'm just reading this as a binary number.

25:53 Okay. I think here I'm I'm assuming that the cost is an integer to make life a bit easier. So is it clear what the threshold language is? You take an optimization problem and uh you turn it into the threshold language by taking all the pairs of instances and the threshold where the optimal value is better than the threshold. Okay. um we say such a an optimization problem now is np hard when this threshold language is np hard formally we have only defined np hardness for languages that's why we need this definition to lift it to optimization problems and uh it's not not hard to prove that then if you have an optimization problem which is Um the other way around uh if the threshold language is NP hard and we assume as usual P is not equals NP then the optimization problem cannot be efficiently solvable okay intuitive statement I guess um but I let's briefly spell out the proof uh we prove this by contraosition so assume that U would be efficiently solvable then we have a polinomial time algorithm that computes the optimal solution in all cases for all instances, right? Uh in particular, we can compute the optimal value of that solution because cost is computable and that means we can decide whether the optimal value is better than any threshold in polomial time. So we've decided whether the language uh whether an element is in the language that means the threshold language is in P. that if the language is np hard n is in p that means p equals np which is a contradiction to our assumption that's what uh we have this one for all all for one lema and earlier in this unit so that means uh rang you uh cannot be n pari that's a contradiction so you cannot have been in po okay so it just means that if the threshold language examp the optimization problem will not be efficiently solvable. It's one of the the easy directions in the table. Um and as a concrete example we can show that this max problem is np hard and also here formally we can um we can do a reduction to the threshold problem. So just to spell that out once we take the threes problem a known np hard problem that we've worked on before np complete problem and we reduce it to this uh threshold language for max and this is actually very easy because it's kind of a a special case of max set if you look at it. So given any three set instance uh X and suppose it has M clauses then we just produce this pair X comma M which means can I satisfy all clauses in my formula. That's exactly satisfiability. So uh the rest is uh is kind of just this chain of of equivalences. X is a three set is a yes instance if and only if it's satisfiable which means all of its clauses m clauses are satisfiable that means XM is in the threshold language.

29:53 Okay, that's a tiny and very simple example of how you can use this this definition to prove that optimization problems are np hard so that we can talk about those being np hard not just the language their threshold languages or decision problems uh that's an alternative most of the time we'll be happy with just proving that the decision version is hard and that the optimization version is then even harder is kind of proven once for all. Okay. Uh let's wrap up this this intro section. Much of this supposedly uh is covered in in some undergrad uh TCS modules. Um maybe not the same in the same kind of uh form of setup. So we formalized what it means to have a polytime algorithm which we call efficient. uh we've looked at decision problems and these other forms of problems during machines as a way to compute things and uh we showed how we can establish this theory of intractability. So we can now rigorously prove that some problems are NP hard which means they probably don't have a solution. Uh but we set out to kind of solve problems despite this fact. Right?

31:16 This was all a prelude to what do we do now? And so let's get started with that part.