Skip to main content
Loading Explore guides…
Linear Optimization Introduction · Acedra
Home
Explore
Mathematics
Linear Optimization Introduction
Sign in to save
Chat
If YouTube asks you to sign in, open the video on YouTube.
Watch on YouTube
Reload player
Transcript
64 segments
Copy
Hide video
0:00
Welcome to the linear optimization course of the University of Wisconsin-Madison. My name is Alberto Del Pia. And in this video, I want to give you a brief introduction about this course. Mainly, I want to tell you what this course is about, and I also want to give you the technical details of this course. Let's start with the name of this course, which is linear optimization. For now, let's forget about linear, and let's focus on the word optimization.
0:26
The field of optimization is all about taking decisions. As the name suggest, in optimization, we don't want to take just any decision, but we want to take optimal decisions. Every day in your life, you take a huge number of decisions. For example, when you go to class, you want to go from home to your lecture room. And to do so, you're already have to take multiple decisions regarding which way to take. If you are a true optimizer, you're interested in taking the shortest path possible.
0:59
However, in this example, it's not really necessary to use optimization because you can just use common sense to get to your classroom. With common sense, maybe you will not take the shortest possible route, but you will take one that takes maybe 1 minute longer. And that's not a big deal. So common sense is often sufficient in everyday life. However, common sense is not sufficient to make decisions in complex systems. With complex systems here, I mean optimization problems
1:29
that are much more complicated than simply finding the shortest path. In fact, for this complex optimization problems, if you use common sense, often, you will end up with a solution that is very, very far from optimal. Moreover, complex systems often arise in situations where there is a huge amount of money involved. Think about the optimization problems that Amazon has to solve in order to deliver to you what you have bought. You can easily imagine that a very little change
1:59
in their logistic can end up saving them millions of dollars every year. So the message so far is that, in general, one does not simply make decisions without optimization. Let me convince you of this factor by giving you an example that seems relatively simple. So it doesn't even seem like a very complex system but where optimization is really needed. This example is what we're going to call later in the course the assignment problem. Let's say we have 70 people and 70 jobs.
2:32
We can visualize these 70 persons as the 70 white dots here on the left. And similarly, we can visualize our 70 jobs as 70 blue dots here on the right. Next, for every pair of person and job, we're going to put a link between the two of them if and only if that person can perform that job. And for every such link, we can also write down in numerical value that represents how well this person can perform this job. For simplicity, in this picture, I'm not going to write this numerical values.
3:10
Now our task is to find the best possible assignment. And we can visualize any assignment by just highlighting the link connecting each person to the corresponding job that he or she has to perform. We have an example of an assignment here on the right. In particular, you can see that every person has only one highlighted link touching it, and the same thing holds for every job. Now, this problem doesn't seem too complicated. In fact, we can give a trivial algorithm to solve it.
3:42
Namely, we can just enumerate all the possible assignments. For each one of them, we can see how good it is by just summing the numerical values on the highlighted links. Then we simply need to keep the best, and that will be our optimal solution. Of course, this is not an algorithm that we want to run by hand, but with the powerful computers that we have nowadays, it shouldn't be too hard. So let's try to implement this algorithm and see how long it takes us to run it.
4:11
And we will not simply just use any computer to solve this problem. We're going to use a supercomputer like the IBM BlueGene/L. So remember, we have 70 people and 70 jobs. But let's first test our algorithm with fewer peoples and jobs. We start with three persons and three jobs. In this case, it's easy to see that the total number of assignments to check is just 6. How can you see that? Well, we'd pick the first person, and we can assign to this person three jobs.
4:43
Then we take the second person, and we're left with a choice among the two remaining jobs. And then the third person will be left with the only remaining job. So in total, we have to make 3 times 2 times 1 choices. This is a 3-factorial, which is equal to 6. Our supercomputer, of course, has no problem in evaluating only these 6 solutions, and it's going to take to 0 seconds. So let's make things a little bit more challenging, and let's try with the 10 people and 10 jobs.
5:13
In this case, we have 10 factorial solutions to check. And this is roughly 10 to the 6. But again, thanks to our supercomputer, it just takes 0 seconds to solve this problem. Great, so let's try now with 15 people and 15 jobs. In this case, we have around 10 to the 12 solutions to check. And finally, our supercomputer is going to take one second to solve this problem. Great, now we're really confident that our algorithm works very well. So let's try with 30 people and 30 jobs.
5:44
Now, the solutions to check is a 30-factorial, which is roughly 10 to the 32. How long do you think it's going to take our IBM BlueGene/L to solve this problem? Maybe 10 seconds, maybe few minutes, maybe an hour or a few days, actually, it's going to take 14 billion years. And this is four times the age of the universe. So you're definitely not going to see the output of your algorithm. This is staggering. Just doubling the number of people from 15 to 30
6:19
makes the problem from trivial to completely unsolvable with our algorithm. If you remember, though, in our original problem, we had 70 people and 70 jobs. In this case, I'm not going to even calculate how much time it's going to take to solve this problem with our algorithm. But what I can tell you is that the number of solutions to check is a 10 to the 100, which is more than the number of particles in the observable universe. At this point, I hope I have convinced you that we really
6:51
need to study optimization. Optimization is not only needed in problems that are clearly complex, but those same problems like this one, which seemed easy, had a first glance but turned out to be very difficult to solve in practice. The next thing that I want to do is to take a step back and discuss how to approach an optimization problem in the real world. When you deal with the real word optimization problem, the first thing to do is to analyze the real world problem and to model it.
7:22
This is done by writing real world relationship with math relationships. Once we have modeled our real world problem, we obtain a mathematical optimization problem, which take this form. Minimize a function f of x subject to x in a Set, capital S. f is called the objective function, and capital S is called the feasible set. Of course, in your real world problem, you will have a very specific function f and a very specific feasible set S. Once we have written down our model, we need
8:01
to perform a model analysis. And this means that we want to study some mathematical properties of the model. Why are we interested in these mathematical properties? Well, this is not just for fun. The main reason behind this is that later on, we want to be able to exploit these properties to come up with an efficient solution method, such as solution method is, in other words, an algorithm. Once we have designed such an algorithm, then we can use it to solve our optimization problem,
8:34
mean f of x subject to x in S. At this point, we have obtained an optimal solution, but we are not really done. The next step is to understand if this optimal solution is indeed what we were searching for, and this is what we do in the validation part of our modeling approach. Often at this point, we realize that our optimal solution is not OK because it doesn't satisfy some constraints, which we forgot to write down among the constraints defining the set S. This happens all the time in practice
9:07
because normally, when the problem is given in words, it's very difficult to write down all the math relationship that need to be satisfied. And so in this case, what happens is that we go back to the modeling stage. We update our feasible set or our objective function to better represent the real world problem, and we repeat the whole process. The process will be repeated until the optimal solution, x star, that we obtain satisfies all the constraints of our real world problem.
9:38
And this concludes my description of the modeling approach. Later on in this video, I will get back to this slide to tell you more in detail how the content of this course fits in this diagram. In this slide, I only want to give you a little remark or a heads up regarding the field of optimization. In fact, often, optimization is also called programming or mathematical programming. In fact, throughout the course, the words optimizations and programming will be interchangeable.
10:10
Essentially, every time I say programming, I mean optimization. At this point in time, programming is a little bit anachronistic. It's a term that was used instead of optimization starting from the 30s. So this word was used before computers even existed, so there was no confusion with computer programming or with programming languages. Originally, the word programming meant planning. And this is based on the military definition of program.
10:40
So from the 30s, the field that now we call optimization was called a mathematical programming. But to avoid confusion, lately, the word programming is getting replaced by optimization. In any case, you still find plenty of books and courses on linear optimizations, which are called the linear programming. And now you know that all these courses and books really talk about linear optimization. Speaking of which, let's get back to the name of this course, linear optimization.
11:13
I told you a few things about optimization, so let me now focus on the word linear in the name of the course. Linear comes from linear functions, like this linear function from our 2 to r in this picture. Let us formally define a linear function f from Rn to R. f is linear if it satisfies two properties. First, f of x plus y is equal to f of x plus f of y for every xy in Rn. The second property is that f of lambda x is equal to lambda f of x for every x in Rn and for every scalar lambda.
11:55
It can be shown that f is a linear function if and only if it can be written as the sum of Ci Xi for some Ci in R. This means that it can be written as C1 X1 plus C2 X2 and so on and so forth until plus Cn Xn. This is the scalar product between the vector C and the vector X. And throughout the course, we are going to denote this inner product up by C transposed X. Now, let's get back to our diagram of our modeling approach. We discussed that in the modeling stage,
12:28
we write down our real world problem with math relationship. And we obtain an optimization problem of the form of min, f of x subject to x in S. Now, linear programming is the special case where all the functions appearing in these problems are linear functions. Namely, f is a linear function, and S is given by means of linear inequalities. In other words, the objective function can always be written in the form of C transpose X. And the fact that X belongs to the set
13:04
S it can be written with a system of linear inequalities, which in matrix form is written as A x greater than or equal to b. Now, let's see our first example of a linear programming problem. As indicated by the title of these slides, I will always use LP denote Linear Programming. In this linear programming problem, my objective function is a 2 x1 minus x2, plus 4 x3. And we want to minimize the subjective function. My linear constraints are x1 plus x2,
13:41
plus x4 less than or equal to 2, 3 x2 minus x3 equal to 5x, 3 plus x4 greater than or equal to 3, x1 greater than or equal to 0, and x3 less than or equal to 0. All the functions that appear here are linear functions, and you can see that because we never multiply two variables with each other. So there is no x1 times x2 or similar products. We also don't have, for example, any x1, the square, or x1 to the cube, which would be also nonlinear. Next, note that all our constraints are of the form
14:20
less than or equal to, equal to or greater than or equal to. And these are the only three types of constraints that we are allowed to used in linear programming. In particular, strict inequalities like x3 plus x4 strictly larger than 3 are never allowed. A big chunk of this course is devoted to algorithms for linear programming. To discuss this, let's get back to our modeling diagram. Earlier on, we said that in the model analysis stage, we obtained some fundamental properties
14:53
of our problem, which then we exploit to develop a solution method. In example of these fundamental properties for linear programming are optimality conditions and duality. So in our course, at some point, we will develop some theoretical results, including this tool, which will allow us to develop the simplex algorithm. The simplex algorithm is considered by many one of the most important algorithms developed in the last 100 years. Now, that we have a better understanding
15:26
of linear optimization, let's get back to our assignment problem that we discussed a few slides ago. If you remember, the problem was to find the best assignment of 70 people to 70 jobs. And we saw that a trivial algorithm where we enumerate every possible assignment as no chance of terminating in a reasonable amount of time. We will see how this problem can be formulated as a linear programming problem. Surprisingly, if we apply the simplex algorithm
15:56
to solve the obtained linear programming problem, we can solve it in only a few seconds. Throughout this course, we will understand how this can happen. Essentially, the theory behind linear programming and the simplex algorithm drastically reduces the number of solutions that must be checked. This is just one example that shows how linear programming is by now a technology. And with this, I mean that it can be solved efficiently both in theory and in practice.
16:27
Finally, let me point out how linear programming is everywhere. In fact, many practical problems in operations research can be expressed as linear programming problems. This happens essentially in every application area, including engineering, computer science, physics, biology, finance, economics, and so on and so forth. Some examples are listed here and include network problems, scheduling, microeconomics, company management, planning, production, transportation technology
17:00
and even military operations. And the importance of linear programming lies even outside of the realm of linear programming. In fact that even in other types of optimization problems, linear programming problems are solved as a sub problems, for example, in integer optimization. This concludes my brief introduction of linear optimization. In the remaining part of the video, I will tell you all the details about the format of this course.
17:31
All this information can also be found on the course syllabus. The purpose of this course is to give you a solid understanding of linear optimization. And the focus is on the theory of linear optimization. In most of this course, we will study the available solution methods. We will see how these algorithms work, and more importantly, we will see why they work. So I will not simply give you an algorithm and tell you that this works for linear programming.
18:02
But together, we will derive such an algorithm and understand and prove why it works correctly. Throughout the course, we will always focus on the interplay between algebra and geometry. This is fundamental because ideas require a geometric view and the geometric understanding of the problems. But then we need to translate these ideas in algebra. In fact, only algebraically we can describe our algorithms and prove that they are correct. On the other hand, in this course,
18:36
we will not talk about software or about implementations. Also, we will not spend much time on how to model real world problems as linear programming problems. If you're interested in modeling, I suggest that you take the course 323. The recommended textbook is "Introduction to Linear Optimization" by Dimitris Bertsimas and John Tsitsiklis. This is a fantastic book, which has been developed for a course at MIT. You can buy new for $85. And if you want to spare some bucks,
19:10
you can also buy it used or rented. Most of the material that we will cover is present also in this book. Of course, the book contains much more, so it is a great resource if you want to know more than what I present in this course. To encourage going back and forth between slides and the book, I will use the same notation. I will also use the same numbering of the sections and of all the results, like for example, theorem numbers. In this slide, I summarized the topic that we will cover.
19:40
As you can see, we will study the first four chapters and then chapter 7 and 8. In the first chapter, we're going to introduce linear programming, and we're going to see few examples. In chapter 2, we will develop our geometric intuition of linear programming by discussing polyhedra and their properties. Then in chapter 3, we will develop the simplex method, which is the main method that we will see to solve in our programming problems. Then in chapter 4, we will discuss duality theory.
20:10
The dual of a linear programming problem is a different linear programming problem that has some very special relationship with the original one. In particular, this will allow us to obtain a different version of the simplex method that is called the dual simplex method. Then we would jump to chapter 7, where we discuss network flow problems. These are very special linear programming problems, and we will see how the simplex method can be specialized for these type of problems.
20:39
Finally, in chapter 8, we discuss computational complexity, and we see the ellipsoid method. The ellipsoid method is a completely different algorithm to solve linear programming problems. The importance of this algorithm is that it is the first known algorithm that is able to solve linear programming problems efficiently in theory. Before proceeding, let me tell you very clearly that this is a challenging course. Much of the material in this course is deep. It requires serious math.
21:11
In the lectures, we will see several proofs, and they expect you to be able to come up with the similar proofs by yourselves. The way I like to put it is that this course is hard but rewarding, just like my favorite video games. What about prerequisites? There is some essential background that will be assumed throughout the course. The first is a working knowledge of linear algebra. For example, you need to know set-theoretic notation, vectors
21:39
and matrices, matrix inversion, sub-spaces and bases, a fine sub-spaces, linear independence, and the rank of a matrix. If you want to refresh your knowledge of linear algebra, I suggest that you study section 1.5 of the textbook. This section is only six pages long and describes all these concepts that we will use heavily throughout the course. The next prerequisite is basic proof techniques. Essentially, I need you to know what is a proof, how to write a proof, and what are
22:11
the different types of proofs, which are essentially a direct proof, a proof by contradiction, and a proof by induction. I also need you to know basic concepts from logic like the contrapositive. To refresh your memory about basic proof techniques, I strongly recommend that you study the "Document Introduction to Mathematical Arguments" by Michael Hutchings, which is available for you in Canvas. Finally, you need to know mathematical notation so that you understand all the symbols that I'm going
22:42
to write throughout the course. I have written a short math symbols cheat sheet describing the meaning of all the symbols that I will use, and you can find these in Canvas as well. I have already set up a way for you to test both your linear algebra knowledge and your math skills. to test your linear algebra, you should complete the assignment 0, which is already available in Canvas. And to test your math skills, you should instead take the quiz 0, which is also available in Canvas.
23:15
Both the assignment 0 and the quiz 0 are ungraded. They're due on September 9 because I want to see how you perform in order to better calibrate the course. So please do them as soon as possible. If you're interested in optimization, in this slide, I listed a few other optimization courses that are available at UW-Madison. The course 425 is about combinatorial optimization. In this video, we've already seen an example of a combinatorial optimization problem. And this is the assignment problem.
23:49
Combinatorial optimization problems are optimization problems that are somewhat described implicitly. And this is very different from linear programming, which is always described with an explicit objective function and an explicit system of linear inequalities. Of course, combinatorial optimization is strongly linked with linear optimization, and throughout the course, I'm going to discuss this connection several times. The course 524 instead is called Introduction to optimization.
24:19
The course 524 is much broader than this course 525, but then the drawback is that, of course, it's not as deep as 525. In particular, 524 introduces several types of optimization problems, so not only linear optimization, and gives several types of five grains to solve this optimization problems, including also the simplex method. However, in the course 524, it is not shown, for example, why the simplex method works. The course 524 is much more interested
24:51
in how this optimization problems can be solved and is instead not particularly interested in explaining why these methods work. Then the course 526 covers more advanced concepts in linear programming, so you should take the course 526 only after taking this course 525. The course 726 instead is called the nonlinear optimization 1. And as the title says, it doesn't only deal with linear functions but also with more general nonlinear functions. Finally, the course 728 is integer optimization.
25:27
And integer optimization problem is very similar to a linear optimization problem, but it allows for a new type of constraints, which is that the variables must be integer numbers. This makes the problem much more difficult but is very useful from a practical perspective because, in several real-world problems, we only want our variables to be integer. Think about if you want to decide how many planes you want to build or how many floors your building should have.
25:56
This, of course, should be integer number. An optimal solution shouldn't be a fraction of number. Finally, let me mention that UW-Madison has an extremely good and wide optimization group. So if you're interested in optimization, this is the right place to be. And please consider applying to our graduate programs. We're always looking to hire smart students. Now, let me get to the technical details about this course. The lectures will be provided via pre-recorded videos.
26:26
They will be available both on YouTube and in Kaltura. In YouTube, the captions are by some automatic YouTube algorithm. While in Kaltura, the captions are made by the McBurney Disability Resource Center. The table in the slide summarizes all the videos, which will be a total of 34 videos, the corresponding topic, and the deadline by which you should learn the corresponding material. In this table, the videos are divided by chapter except for chapter 3, which is divided into two parts
27:00
because it's by far the longest chapter that we will study. The videos will be available for you well in advance online in order to give you ample time to learn the material. In particular, in the syllabus, you can find a table that tells you when each video will be available on YouTube. The videos are topic-based. Therefore, their length varies widely from as little as five minutes to more than one hour. My office hours are on Tuesday and Thursday
27:29
from 9:30 AM to 10:30 AM, and they will take place in Zoom. The course has a home page in Canvas. In Canvas, you can find everything about this course except for the video lectures. So you can find a syllabus, the lecture slides, the introductory material, the homework and their solutions, and also the grades. If you have questions about the course, don't send me an email but use the discussion section so that other students can also see your question and the corresponding answer.
28:00
Don't ask me to give you access to the Canvas web page. I cannot do that. You're given access automatically when you are enrolled. The syllabus contains all the information about the scores that you possibly need and is available in Canvas. Let's briefly talk about expectations. I am expected to prepare lectures, of course, be at my office hours, and guide your learning process through homework. Finally, I should give you feedback on how you're doing in a timely fashion.
28:30
And here, I am talking about grades for your homework and exams. On the other hand, you're expected to learn the material that I present. You should do the homework. And you're expected to know and follow the academic conduct the guidelines. What about homework? Homework will be assigned approximately every two weeks. In this table, you can already see that there are a total of seven homework. The first is homework 0, which I already discussed because it consists of assignment 0 and quiz 0.
28:59
Then you have one homework per chapter except for chapter 3, which is, again, divided into two parts. In the table, you can also see the due date of the homework. Now, like homework 0, every homework consists of one quiz and one assignment. The quiz is available directly in Canvas and should be completed individually there. On the other hand, the assignment is also available in Canvas, but it is a PDF file. And for assignments, you are strongly encouraged to work in groups of two people.
29:32
We do not enforce that you work in groups of two people, but I think it's of extreme importance that you do so. This is because in most assignments, you will need to write proofs. And especially at the beginning when you're not familiar with proofs, it's hard to understand if actually you prove that what you were supposed to prove or not. And now. Working with a partner allows you to have one person that can listen to your proof or read your proof.
29:58
And this person will tell you if he or she is able to follow it and to understand it or not. This will allow you to find holes in your proof and to fix it. In any case, you should submit your solution to the assignments in Canvas, only one submission per group. You can type your solution, for example, with LaTeX, or you can also write your solution by hand and then scan it. But please write in a way that we can understand easily your solution. I don't want you to waste points because of these.
30:28
Assignments will not be completely graded, so only a subset of the compulsory exercises will be graded. In any case, the complete solution will be published on Canvas. Different students will need to solve the different problems in their assignments. This depends if you're an undergraduate student, a graduate student, or honors student, and everything will be clearly explained in the assignment. Also, every assignment contains a bunch of optional exercises for keen students.
31:00
I strongly recommend that you take the time to try to solve also the optional exercises. This will greatly help you for the exams. All the homework will be graded except for homework 0, which is only there to test your linear algebra and your math skills. The late submission policy is minus 20% of the total points per hour. The TA of this course is the Dekun Zhou, and he's responsible for the assignments and any question regarding the assignments. His office hours are Monday from 4:00 to 5:00
31:33
PM and Wednesday from 1:00 to 2:00 PM. Please let the crew know this week if you have a conflict with his office hours. What about grading? The components of grade are as follows. 40% is from your homework, more in detail, 15% from the quizzes, and 25% from the assignments. 30% of the grade is due to the midterm and 30% to the final. The midterm exam takes place on October 29, 2020, from 9:30 to 10:45 AM, and it's online. The final exam takes place during the course slot in the final week.
32:13
And it's also online. Please let me know this week if you have a conflict with exam times. The content that will be tested in the midterm consists of chapter 1, chapter 2, and chapter 3, part 1. In the final exam, potentially, all the material of this course will be tested. But of course, it will be more focused on the material not tested in the midterm. Every year, both undergraduate and graduate students take this course. You will be graded separately using two different curves that
32:46
will be applied at the end of the semester. In the rest of the video, I only want to tell you a little bit about myself, and I want to ask you a few things about you. I studied in Italy in the University of Padova, where I took both my bachelor, my master, and my PhD. In mathematics. Then for a few years, I was a postdoc working on optimization, first, in the Ott-von-Guericke University of Magdeburg, then at ETH Zurich, and then at the IBM, Watson Research Center in New York.
33:14
In 2014, I joined the University of Wisconsin-Madison. I am part of the Wisconsin Institute for Discovery, and my home department is the Department of Industrial and System Engineering. By courtesy, I am also affiliated with the Department of Mathematics and Computer Sciences. My main research areas are integer optimization, combinatorial optimization, and theory of machine learning. So my research is strongly connected with this course.
33:40
And so don't hesitate to ask me any kind of advanced question. I can always tell you that I just don't know. Now, that you know a few things about me, I want to know more about you. In Canvas, you can find a student survey quiz that you should take by September 9. Also, this survey will help me in calibrating the rest of the course. This concludes our introductory video to the course 525. If you have any questions, please post them in the discussion section in Canvas.
Here to help you learn
Sign in to keep a private conversation with your course tutor.
Ask me anything about the material…
Sign in to chat