Video 6-3: LP Reformulations
CS 627 – Advanced Algorithms (Winter 2026-27) · unit page
· YouTube
2026-11-16, 6:50
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:03 We'll next look at some standard tricks of the trade for working with LPS. None of that is really deep. I just want to list them quickly so that you've seen them. Um they're just uh repeatedly useful when when working with them. Um maybe to motivate this is a bit like uh the usual construction. You you have a problem, you transform it to a different world. in this case formulated as as an LP and then you can apply some abstract simplifications in this LP world that may not have a direct correspondence in your original problem but they're still valid because you follow the rules here and then sometimes you can go back and get a a better solution for your original problem that way. That's that's the idea. um for both theory and and practice it's useful and the first thing is um to fix a specific uh normal form for LPS at least to think about how to solve them algorithmically. If you had to build a solver yourself, the first thing you would probably want to do is not deal with the general mess of LPS that I allowed earlier. This is convenient if you have to write one down, but there's a mechanic way to get to a a con um more restricted form.
1:26 Um this is just repetition of the notation from before. Uh what we can always do um okay one step before the simplification that's a lot of variables on that slide and uh you can express many of these things much more concisely I don't know whether it's more simply but um without writing as much using just linear algebra vectors and and matrices u you'll find this all over the place and maybe it's natural enough after a file. So the variables you can write as one vector column vector. Same for the cost coefficients. So I'll I'll always write these as column vectors. So the objective function is for me crpose that is of course just the scalar product. Okay. So it's transpose C and then they have the same dimension. You do the usual the tiny matrix multiplication where the output is a single number. And they can do the same trick to the constraints.
2:36 Um for equality constraints, okay, we can have different constraints. So you can treat them separately and have a different matrix each. So you put the coefficients for the constraint of the first row, you put that in the first row of your matrix and so on. Same for the right hand sides, you put those all in columns. And then you can can concisely write the constraints as a as a vector matrix product that element wise equals this vector B. That's what's meant here.
3:16 I guess for equality that's kind of the usual notion of what you would understand. Uh and we'll just do the same for the inequalities. And here I guess the comment is is more uh more needed. Lesser equal could mean many things if you compare whole vectors. Here what we mean is really every single component component wise needs to be smaller. Okay. So then um but if you ever need to express a specific constraint you can say I'm I'm picking out the certain row of the matrix and the entry of B.
3:53 With that we can write the whole thing more concisely and now we can reformulate a few things. These are all rather superficial. If you um if you have a maximization problem you might recast it as a minimization problem by just double negating. So now we're uh we're minimizing the negative function and then at the end take take minus again. So this this is not formally part of the LP but I guess you can keep that in mind. uh if you have greater equal constraints then you can multiply them by minus one and that flips the sign over right we we never said often we think of the variables as weakly positive but for a and b there's no constraints uh the coefficients a and b they can be positive or negative that's fine uh then um for equality constraints uh for for um lesser equal inequality constraints we can turn them into equality constraints by adding what's called a slack variable. If this thing on the left is supposed to be less or equal bi, well, either it's equal or it's less than this by something. You can just give that something a name. So, there's a new variable wasn't used before. And we'll we'll call this SI for slack and I for the E constraint. And then you have an equality constraint plus a variable that now needs a non- negativity constraint. And sometimes it's more convenient to have these instead of that. As you'll see, um, if you have variables that are not constrained, we can turn them into two variables that are both weekly positive.
5:31 These turn turn out to be more convenient to work with. And of course, a general number can always be written as a positive part and a negative part. Um, in principle here, you allow that they're both non- negative. doesn't make a big difference but clearly by making either this or this bigger you can represent any positive or negative number. Okay with that um yeah you can also go backwards if if you want um an equality constraint you can reexpress but we'll we'll not do this here. This in principle is possible. what we'll what we'll use is um one of these two normal forms. Um so we'll always minimize uh and we'll just have one sort of constraints and always these non- negative variables uh I think for the solver um depends depends on your view. Okay. So in the literature both are studied as the normal form for LPS. So I think there's no no complete agreement on um which is the right one.
← Video 6-2: LP Basics & TerminologyVideo 6-4: The Simplex Algorithm →