Linear Optimization (01:640:354)
Spring 2008
Time: Mondays and Thursdays, 8:40-10:00 AM
Place: ARC 110
Course webpage: http://rutcor.rutgers.edu/~dpapp/354.html
Instructor: David Papp
E-mail: dpapp at rutcor followed by dot rutgers dot edu
Please include the course number (640:354) in the subject line of emails.
Office hours: Regular office hours: Mondays, 10:30-12:00, at RUTCOR #143.
(Check the campus map to find the building.)
I'm frequently available by appointment, too.
Syllabus
The syllabus of the course is available here.
Announcements
- It's over! Find your grade in your RU transcript online. (Let me know if your grade doesn't appear by
the end of the exam period.)
Previous announcements
- EXAM DATE: May 5 (Monday) 8:40am-10am. (during the last class).
- An extra credit homework problem (computational) is posted.
- Midterm dates: March 10, April 21.
- See my office hours above!
- Theorems 1.6 and 1.7 in the textbook are FALSE! Don't learn them, consult the class notes for correct statements.
- Homework 4 is posted.
- Check the Prerequisites section of the syllabus. I'm serious about it!
- Reminder: "exercises" are problems for you to practice, you need not turn in the solutions.
If you have any questions about them, of course, feel free to ask, for example after class, or during office hours.
Class materials
January 24.
- Notion of a linear optimization problem, or linear program (LP).
- Special forms of LP, and their equivalence.
- Some simple models using LP.
- HOMEWORK 0. Skim through the handout given in class.
- EXERCISES. Section 1.1: problems 1-11. These are modelling problems, i.e. turn a word problem into LP form.
(The book has solutions to the odd numbered ones.)
January 28.
- The geometry of LP; convex polyhedra.
- Possible "outcomes" of an LP: infeasible and unbounded problems, problems with finite optima.
- Vertices, extreme points, basic feasible solutions, and their equivalence.
- Characterization of polyhedra with vertices and without vertices.
- EXERCISES. Section 1.1: problems 1-11, if you haven't done them already. Section 1.2: problems 12-16. Section 1.5: problem 1.
January 31.
- More on basic feasible solutions, and vertices of polyhedra.
- Polyhedra in canonical form always have a vertex.
- The simplex method.
- HOMEWORK 1 is here. Due on Thursday, February 7.
February 4.
- Cycling in the simplex method, and how to avoid it.
- The full tableau implementation of the simplex method.
- EXERCISES. There are plenty of exercises in Chapter 2 (both solved and unsolved) to practice the simplex
method with.
February 7.
- The two-phase simplex method.
- EXERCISES. There are plenty of exercises in Chapter 2 (both solved and unsolved) to practice the simplex
method with.
February 11.
- Practicing the two-phase simplex method.
- EXERCISES. SIMPLEX, SIMPLEX, SIMPLEX! Practice a lot, Phase I, Phase II, everything. A homework is coming up!
February 14.
- Duality I.
- HOMEWORK 2 is here. Due on Thursday, February 21. Late homeworks will NOT
be accepted.
- EXERCISES. Write up arbitrary LPs, and find their duals. Some more practice on simplex won't hurt either.
February 18.
- Discussion of Homework I solutions.
- A little bit of duality.
- Write up arbitrary LPs, and find their duals. Some more practice on simplex won't hurt either.
February 21.
- Duality II.
- Optimality conditions and complementary slackness.
- Applications of duality -- theoretical and practical.
February 25.
- The dual simplex method and its applications.
- EXERCISES. Practice the most important dual simplex application: take an LP whose optimal BFS, and
the corresponding tableau, is known. Then add an inequality constraint, and resolve the problem.
February 28.
- Modelling exercises.
- EXERCISES. Solve all the modelling problems from Chapter 1 that you haven't solved for HW 1.
March 3.
- Some more examples of simplex method phase I, phase II, and the dual simplex method.
- NO HOMEWORK this week, study for the midterm instead!
March 6.
- Review session before Midterm 1.
- The midterm is CLOSED BOOK, with a 1-page (two sided) "cheat sheet" allowed. You may use a calculator,
but not one which is programmable to do the simplex method for you. (This includes most popular TI calculators.)
March 10.
March 13.
- LP software demo. We saw (a little bit of) CPLEX, MINOS, AMPL, and NEOS. Further solvers
to check out are the glpkit, lp_solve, and COIN-OR. (All of these are free.)
March 24.
- We discussed the solutions to the first midterm.
March 27.
- Final words on LP.
- Integer programming: intro with many examples.
- Start reading Chapter 4!
- HOMEWORK 3 is here. Due on
Thursday, April 3. Late homeworks will NOT
be accepted.
March 31.
- Complexity Theory crash course.
April 3.
- Complexity Theory continued: polynomial time solvable problems vs. NP-har problems.
- LP is "easy", IP is "hard".
April 7.
- Total unimodularity.
- HOMEWORK 4 is here. Due on
Thursday, April 17. Late homeworks will NOT
be accepted.
April 10.
- Finished total unimodularity.
- The Branch-and-bound method.
- HOMEWORK 4 is here. Due on
Thursday, April 17. Late homeworks will NOT
be accepted.
April 14.
- Cutting plane methods.
- Gomory cuts.
April 17.
- Discussion of Homework III solutions.
- Review session before the midterm.
- The solutions to Homework IV can be found here
- EXTRA CREDIT HOMEWORK (a small computational problem for big extra credit)
is posted here. Deadline: by the day of the final exam, May 5.
April 21.
April 24.
April 28.
- Network Flows II.
- Finding the maximum flow using augmenting paths (Ford-Fulkerson and Edmonds-Karp).
- The max flow-min cut theorem.
May 1.
- Network Flows III.
- The integrality lemma.
- Course wrap-up
- Solutions to selected problems of Midterm 2 are posted here.
Email me here: dpapp at rutcor followed by dot rutgers dot edu
Always include the course number (640:354) in the subject line of emails.