Video 6-2: Linear program normal forms

0:03 In the next sub section, we'll look at some some tricks to modify a given LP so that it still produces the same value or solves the essentially same problem but has a different shape. And often times that's the key to making making progress on a problem. If all you're doing is modeling a problem and then passing it to a solver, that's not necessary. Um but we'll see often times we use LPS as part of an algorithm and then want to do something with the output from the LP solver. Uh and there it's helpful to be able to do uh some modifications to the problems. So we'll we'll still use of uh think of this as mostly a tool. Um but another reason for looking at some of these reformulations is that they are also key to make uh LP solvers in the first place. And uh as I said, we're not the goal is not for you to make your own. Um but I think it's good to have a a little bit of an insight how things work.

1:07 Um you can always uh any tool as good as it may be is only as effective as the uh the cleverness with which you apply it. So we'll we'll briefly uh look at at least the conceptual ideas um for the more basic algorithm for solving LPS. So first of all uh recall this was the general form that we've just discussed. there's uh n variables and then you can have constraints of different forms. Um so I'll always have n variables from now on and m constraints and so the variables are called xj. The constraints have coefficients for the variables aig. So i is the uh constraint. It's the i constraint and then j is the coefficient in the i constraint for the j variable. as you can see in the examples above. Uh and it'll have a right hand side which is just a number bi. And also the objective function all of these have to be linear functions. So they have to look like this. Now I guess for the objective function or general linear functions you could have a a constant term. But here for these you could uh fold it into b and for the objective function a constant term doesn't make the diff the problem different. So no no no uh reason to allow that here.

2:34 Um okay uh as before I hope this is explained wherever it's used. If if set occurs it's supposed to stand for the um objective function the objective value. The first step is uh to get rid of all these long sums and use concise linear algebra notation. So um for now that's just an abbreviation. If you've ever uh done uh programming in numpy or matlab or any of these tools they use this all the time where everything is is vectorzed and at least in the olden days that was the way to get speedups in Python by using the automatic uh faster routines that these libraries provided.

3:23 Um, nowadays you still do that, but you also rely on kernels that execute things on a GPU. But even if not, I mean, if you don't care about that part, ignore it. Um, but you'll have to uh be able to read the matrix vector product notation for so many things in uh in data science as well. I think it's worth uh getting used to. Um, on the slides, I tried to be diligent to put a bold face. uh variable whenever it's a matrix or a vector just as a little signal. Ah uh remember this is not actually just a number. I'll stop doing that after these sections because in general um it's not actually that helpful but uh and people don't consistently do it. Uh but for the introductory parts um I was diligent with doing it. Right. So we have the variables and instead of x1 to xn I'll write the column vector vector x bold x for the cost function we have the coefficients uh that's another vector c they have the same dimensions but they're both column vectors so if I want to take if I want to get back the uh objective function I should take the scala product or dotproduct and so I have to take the transpose of the C vector because then right then C lies lies here and X is a vector there. That's how you uh you can do dot productducts put one or well I guess from your perspective put that on top of the other as in matrix products and you get back a number. So uh you can call this a scalar product if it's vectors um a vector space or in general a dot productduct is the more general algebraic term. That was the easy bit. That's the objective function. Then for the constraints, um, we can do both. We can fold the scalar product between the coefficient of one constraint and the vector of variables into a a vector product. But we can also fold all the constraints in the other dimension into a matrix. So we'll write all the uh coefficients of all the constraints in one matrix. Here I'm just picking the equal constraints for now.

5:44 uh we'll we'll come back to the different types of constraints. So you have one one big matrix with all the coefficients. You have one vector of the right hand sides. And then you can write the constraints as uh the coefficient matrix times the vector of variables equals the right hand sides. That's expressing the same as as this line where we iterated for i from one to p. So you should imagine p copies of that. uh I noted down the dimensions of these matrices. So that's the assumption that there's P equality constraints as up here. But the other two types of constraints we do the same. Um just note that when you write some vector less or equal some other vector, you have to tell tell me what the lesser equal really means. But it's standard here to mean element-wise comparisons. So a vector is smaller than another vector if it's smaller in every component. It's smaller in the first component and the second and the third and so on. And same for greater equal. That's this standard notation for equal is actually the same like uh a vector is equal to another vector if the first component is equal and the second is equal and so on.

6:59 Right? It's always an and between the element wise um comparisons. Okay? So that's how we can express the constraints. If we want to talk about a single constraint, you basically have to take out take a a row of the matrix of the coefficient matrix. And uh the notation I'm going to use for that is just put a bullet where there's um the don't care comp dimension of the matrix. So I is the i row, but then the columns I'm saying take all of them. So you write this as this. So, you know, Python notation would probably be something like a and then I colon. Um, and most most languages have some way to say this. So, uh, colon instead of the bullet, but this is a bit in the mathematical notation. This is more standard. And you can do the same for columns. Is that notation clear so far? Okay, so we can very compactly now write our LPS. Uh there's a few other little really shallow tricks we can do. The one is uh we don't need maximization and minimization. You can always write a max as min of the negative. You just negate the cost function and minimize the negate it or if you want to maximize uh revenue, you minimize loss. Um, if you have greater equal constraints, you just multiply them with minus one and they turn into a lesser equal constraints. That's also like a I'm not going to say elementary school, but high school at best. Uh, there's a few um more tricky tricks um to get rid of the lesser equal constraints. If you want to, you can introduce a new variable. So it's the same to to ask for your variables to satisfy this constraint as these two together. So you introduce a new slack variable which essentially uh quantifies how far is this away from the upper bound and you uh request that that is not negative.

9:19 That's the same. So you uh you can move between equality and lesser equal constraints that way. And lastly, we can force all variables to be non- negative variables by uh splitting up the variable into two parts. Uh essentially the positive and the negative part and again forcing both to be positive. It's not enforced that either of that that always one of the two is zero. Turns out you don't need you don't need that. Um but you can replace XJ with this difference wherever it occurs. and now get rid of XJ and then all the remaining variables are non- negative. Okay, so you can always uh eliminate these these unconstrained variables and with these rules you can get your LPS to have one of those two normal forms. Um which one is more convenient depends on the way you look at it. either you have uh only lesser equal constraints with only non- negative variables or you have equality constraints with only non- negative variables. In both cases, we'll write a as this matrix uh m * n and b is as big as we have constraints. C is as big as the number of variables n for the cost function. Um but in these two regimes so if you think about this case uh with equalities you probably want uh fewer constraints than might you might have more constraints than variables potentially is not it's not enforced on this side. If you have more more constraints than variables then essentially uh you're constrained to a single point or it's infeasible. So most of the time here you'll have a lot of variables maybe coming from slack variables. Uh whereas here you could have a lot more constraints and you take the intersection of all those half spaces.