Math 3272: Linear Programming (Fall 2022)
General Information
Instructor: Mikhail Lavrov
Location: Mathematics 112
Lecture times: 5:00pm to 6:15pm on Tuesday and Thursday
Textbook: Linear Programming: Foundations and Extensions by Robert Vanderbei. You can access it online via SpringerLink (you will have to click Log in, in the top right, and access it via KSU's subscription).
Office hours: Tuesday 12:00pm to 1:00pm, Wednesday 4:00pm to 5:00pm in Mathematics 245.
D2L page: https://kennesaw.view.usg.edu/d2l/home/2672229
During the scheduled office hours, you are welcome to stop by my office without an appointment: answering your questions is the reason I'm there! Outside that time, please email me at mlavrov@kennesaw.edu and I will either answer your question by email, or we will find a different time to meet. (However, it is difficult for me to adjust my schedule on very short notice, so please email me the day before if you want to set up a meeting.)
D2L will be used to submit assignments (these will be posted both here and on D2L, for convenience) and to view grades. The syllabus is also posted on D2L.
Homework and Exams
There will be eight homework assignments, two midterm exams, and one final exam; the dates are marked below. (I may change the midterm exam days by ±1 lecture if I have to adjust the pace of the class, but I'll announce this in advance if it must happen.)
I will post the homework assignments here and on D2L; they are always due on Friday at 11:59pm, via D2L.
Exams will be given in person during our ordinary 75-minute class period.
Textbooks
Our official textbook for the course is Robert Vanderbei's Linear Programming: Foundations and Extensions. I will not go entirely in the same order, and sometimes I will cover topics this textbook does not cover. In any case, all the material covered will be in the lecture notes posted on this page.
Detailed Schedule
A label like RV 12.34 indicates that we will cover Chapter 12, section 34 of the textbook. (We might not always cover exactly the material in that section.)
Lecture notes will be available on the day of the lecture or earlier.
Some of you might be interested in the .tex source files for the lectures. (I've gotten several questions like: "How do you make these diagrams?" It's all TikZ.)
-
DateTopic CoveredOther details
-
Tue 8/16Intro to linear programs
Lecture notesRV 1.1-1.2 -
Thu 8/18Constraints in LPs
Lecture notesRV 1.2,2.1 -
Tue 8/23
-
Thu 8/25Basic solutions; pivoting
Lecture notesRV 2.1
HW1 due Friday -
Tue 8/30Objective functions
Lecture notesRV 2.1-2.2 -
Thu 9/1The simplex method
Lecture notesRV 2.4-2.5 -
Tue 9/6Two-phase methods
Lecture notesRV 2.3 -
Thu 9/8Pivoting rules
Lecture notesRV 3.1-3.4
HW2 due Friday -
Tue 9/13Corner points
Lecture notesRV 6.1 -
Thu 9/15Revised simplex method
Lecture notesRV 6.2-6.3 -
Tue 9/20Worst cases
Lecture notesRV 4.1-4.4 -
Thu 9/22Simplex method reviewHW3 due Friday
-
Tue 9/27Exam 1
-
Thu 9/29Duality
Lecture notesRV 5.1-5.3, 5.8 -
Tue 10/4Complementary slackness
Lecture notesRV 5.4-5.5 -
Thu 10/6The dual simplex method
Lecture notesRV 5.6-5.7
HW4 due Friday -
Tue 10/11Uses of dual simplex
Lecture notesRV 5.6-5.7 -
Thu 10/13Sensitivity analysis
Lecture notesRV 7.1 -
Tue 10/18Zero-sum games
Lecture notesRV 11.1-11.3 -
Thu 10/20Solving zero-sum games
Lecture notesRV 11.1-11.3
HW5 due Friday -
Tue 10/25Network flows and cuts
Lecture notesRV 14.1, 15.5 -
Thu 10/27The Ford-Fulkerson method
Lecture notes -
Tue 11/1The integral flow theorem
Lecture notes -
Thu 11/3Transversals
Lecture notesHW6 due Friday -
Tue 11/8Duality + network review
-
Thu 11/10Exam 2
-
Tue 11/15Integer programming
Lecture notesRV 23.1, 23.3 -
Thu 11/17Branch-and-bound
Lecture notesRV 23.5
HW7 due Friday -
Tue 11/22No class
-
Thu 11/24No class
-
Tue 11/29Cutting planes
Lecture notes -
Thu 12/1The traveling salesman problem
Lecture notesRV 23.2
HW8 due Friday -
Tue 12/6Final exam (6:00pm - 8:00pm)