Math 482: Linear Programming (Spring 2020)

Mikhail Lavrov

Archiving note

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.

Detailed syllabus

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)
Wed March 25 Bipartite matchings I
GM 8.2; PS 10.1, 13.2; CCZ 4.2
Fri March 27 Bipartite matchings II
GM 8.2; PS 10.1, 13.2; CCZ 4.2 HW 6 due
Mon March 30 Network flows
PS 4.3; V 14.1, 15.5
Wed April 1 Max-flow min-cut theorem
PS 6.1; V 15.5
Fri April 3 Augmenting paths
PS 6.2 HW 7 due
Mon April 6 Ford-Fulkerson algorithm
PS 6.2-6.3
Wed April 8 Max-flow extensions
external source
Fri April 10 Minimum cost flows
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
PS 5.1-5.3
Mon April 20 Primal-dual algorithm II
PS 5.1-5.3
Wed April 22 Primal-dual algorithm III
PS 5.1-5.3
Fri April 24 Integer Programming Integer constraints
PS 13.1; CCZ 1.1, 2.10-2.11 HW 9 due
Mon April 27 Branch-and-bound method
PS 18.1; V 23.5; CCZ 1.2.1
Wed April 29 Cutting plane method
PS 14.1; CCZ 1.2.2
Fri May 1 Traveling salesman problem
V 23.2; CCZ 2.7
Mon May 4 Approximation algorithms
PS 17.1-17.2 HW 10 due
Wed May 6 Exam review (Exam topics)
Tue May 12 Take-home final exam

Last updated May 6, 2020. Mikhail Lavrov <>