This is an archived version of a class I taught at the University of Illinois Urbana-Champaign. For a while after I left, it remained on UIUC's website, but it was taken down when some subdomains got shuffled around. I think these are pretty okay lecture notes, and I know some people found them useful later, so I've decided to archive them on my personal webpage. If you spot any mistakes, please let me know.
This is actually not the latest version of linear programming, as taught by me; here is the linear programming class I taught at Kennesaw State University in the fall semester of 2022. The notes there are, broadly speaking, more polished but cover less material.
The course grade will be calculated as follows, out of 660 points total:
You can check your grades via Moodle.
Your grade total will be converted to a letter grade according to the following scale:
| A+ | ≥ 630 | B+ | ≥ 520 | C+ | ≥ 450 | D+ | ≥ 380 |
| A | ≥ 570 | B | ≥ 490 | C | ≥ 420 | D | ≥ 350 |
| A- | ≥ 540 | B- | ≥ 470 | C- | ≥ 400 | D- | ≥ 330 |
It is possible to take the course for 4 credits rather than 3, at the cost of extra homework questions and more difficult exams. If you want to do this, you need to register at the math office in Altgeld Hall soon after the start of the course.
There will be 10 homework assignments, to be turned in at the beginning of class the day they are due. Of these homework assignments, the top 8 homework scores will determine your grade. Each assignment is graded out of 20 points, for a total of 160.
If you cannot attend class (for example, if class is being held online for some reason), you can submit a scanned copy or a photo of your homework as a single PDF file by e-mail before class begins.
If the homework assignment is received after class on the due date, but before the next class, it will be accepted as late, for a 2-point penalty. Homework will not be accepted after the next class for any reason.
There will be three evening midterm exams: Wednesday 2/19, Wednesday 3/11, and Wednesday 4/15 from 7pm to 8:30pm in 341 Altgeld Hall. Correspondingly, three lectures will be canceled, not necessarily in the same week as the midterm exams. These will be marked in the syllabus below. (Update: the third exam will be a take-home exam; you will have 24 hours to work on it on Wednesday 4/15.
The final exam will be a take-home exam on Tuesday 5/12, in the same style as the third exam.
This course is based on several textbooks with a lot of overlap; read whichever ones help, none are required. In the syllabus, I will refer you to sections of the textbooks below that cover the relevant material.
The syllabus below will initially describe a tentative plan for what topics will be covered when. As the semester progresses, I will update the syllabus with information about what actually happened in class, adjustments to my plans for the future, and links to homework assignments.
| Date | Chapter | Details | References | Homework/Exams |
| Wed January 22 | Background | Intro to linear programs | GM 1.1; V 1.1-1.2 | |
| Fri January 24 | Constraints in LPs | GM 4.1, 4.3; PS 1.5, 2.1 | ||
| Mon January 27 | The Simplex Method | Basic solutions; pivoting | GM 4.2; PS 2.2, 2.4; V 2.1 | |
| Wed January 29 | Objective functions | GM 5.1; PS 2.5-2.6; V 2.1 | ||
| Fri January 31 | Simplex method example | GM 5.2-5.3; PS 2.9; V 2.2 | HW 1 due | |
| Mon February 3 | Two-phase simplex method | GM 5.4, 5.6; PS 2.8; V 2.3 | ||
| Wed February 5 | Pivoting rules | GM 5.7-5.8; PS 2.7; V 3.1-3.4 | ||
| Fri February 7 | Corner points | GM 4.2, 4.4; PS 2.2 | HW 2 due | |
| Mon February 10 | Simplex tableau formulas | GM 5.5 | ||
| Wed February 12 | Revised simplex method | GM 5.6; PS 4.1-4.2 | ||
| Fri February 14 | No class | |||
| Mon February 17 | Worst cases | GM 5.9; PS 8.6; V 4.4 | HW 3 due | |
| Wed February 19 | Exam review (Exam topics) | Exam: 7pm in 341 AH | ||
| Fri February 21 | Duality | Intro to duality | GM 6.1-6.2; PS 3.1; V 5.1-5.4 | |
| Mon February 24 | Complementary slackness | GM 6.4; PS 3.2; V 5.5 | ||
| Wed February 26 | Duality in the tableau | GM 6.3; PS 3.5; V 5.4 | ||
| Fri February 28 | The dual simplex method | PS 3.6-3.7; V 5.6-5.7 | HW 4 due | |
| Mon March 2 | Sensitivity analysis I | V 7.1 | ||
| Wed March 4 | Sensitivity analysis II | V 7.1 | ||
| Fri March 6 | Zero-sum games I | GM 8.1; V 11.1 | HW 5 due | |
| Mon March 9 | Zero-sum games II | GM 8.1; V 11.2-11.3 | ||
| Wed March 11 | Exam review (Exam topics) | Exam: 7pm in 341 AH | ||
| Fri March 13 | Fourier-Motzkin elimination | GM 6.7 | ||
| Mon March 16 | Spring break: no class | |||
| Wed March 18 | ||||
| Fri March 20 | ||||
| Mon March 23 | Graph Theory | Zoom practice (optional) (Slides) |
||
| Wed March 25 | Bipartite matchings I
(Slides) |
GM 8.2; PS 10.1, 13.2; CCZ 4.2 | ||
| Fri March 27 | Bipartite matchings II
(Slides) |
GM 8.2; PS 10.1, 13.2; CCZ 4.2 | HW 6 due | |
| Mon March 30 | Network flows
(Slides) |
PS 4.3; V 14.1, 15.5 | ||
| Wed April 1 | Max-flow min-cut theorem
(Slides) |
PS 6.1; V 15.5 | ||
| Fri April 3 | Augmenting paths
(Slides) |
PS 6.2 | HW 7 due | |
| Mon April 6 | Ford-Fulkerson algorithm
(Slides) |
PS 6.2-6.3 | ||
| Wed April 8 | Max-flow extensions
(Slides) |
external source | ||
| Fri April 10 | Minimum cost flows
(Slides) |
V 14.1-14.4 | HW 8 due | |
| Mon April 13 | Exam review (Exam topics) Min-cost flow example | |||
| Wed April 15 | Take-home exam | |||
| Fri April 17 | Primal-Dual Method | Primal-dual algorithm I
(Slides) |
PS 5.1-5.3 | |
| Mon April 20 | Primal-dual algorithm II
(Slides) |
PS 5.1-5.3 | ||
| Wed April 22 | Primal-dual algorithm III
(Slides) |
PS 5.1-5.3 | ||
| Fri April 24 | Integer Programming | Integer constraints
(Slides) |
PS 13.1; CCZ 1.1, 2.10-2.11 | HW 9 due |
| Mon April 27 | Branch-and-bound method
(Slides) |
PS 18.1; V 23.5; CCZ 1.2.1 | ||
| Wed April 29 | Cutting plane method
(Slides) |
PS 14.1; CCZ 1.2.2 | ||
| Fri May 1 | Traveling salesman problem
(Slides) |
V 23.2; CCZ 2.7 | ||
| Mon May 4 | Approximation algorithms
(Slides) |
PS 17.1-17.2 | HW 10 due | |
| Wed May 6 | Exam review (Exam topics) | |||
| Tue May 12 | Take-home final exam | |||