Theory of Linear Optimization (16:711:614 and 01:640:453)

Fall 2008

Syllabus

Announcements

• The FINAL EXAM is on December 19, from 8am to 11am, in Rutcor 166 (the regular classroom).
• Another exam time is available, in case of conflict, on the last week of classes: December 8, from 1pm to 4pm.

Past announcements

• The second midterm was on November 25, Tuesday, in class.
• The first midterm was on October 14, Tuesday, in class.
• There is a football match on September 11, shortly after our class. Expect long delays if you are coming to class from a different campus.

Class materials

• Types of optimization problems, the notion of a linear program (LP).
• Some simple models using LP.
• HOMEWORK 0. Read this handout.

• Different forms of LP and their equivalence.
• The geometry of LP; definition of a convex polyhedron.
• Vertices, extreme points, basic feasible solutions, and their equivalence (in polyhedra).

• Characterization of polyhedra with vertices and without vertices.
• Polyhedra in standard or canonical form always have vertices.
• Canonical form polyhedra and basic feasible solutions.
• Download HOMEWORK 1 for undergraduate students and for grads. The deadline is September 16, Tuesday.

• The simplex method, algebraic description.
• Important issues raised: initialization, termination, is it correct, implementation?

• Cycling in the simplex method. When does it happen and how to avoid it: perturbation, lexicographic rule, Bland's (smallest subscript) rule.

• The full tableau implementation of the simplex method.

• The big-M method.
• The two-phase simplex method.
• Download HOMEWORK 2 for undergraduate students and for grads. The deadline is September 30, Tuesday, in class.

• Duality I: the definition of the dual LP, and its interpretations.
• Weak Duality in Linear Programming.

• Duality II: the Strong Duality of Linear Programming.

• Discussion of homeworks.

• Optimality conditions.
• Complementary slackness.
• Applications of duality -- theoretical and practical.

• Review class before the midterm.

• Midterm 1.

• The dual simplex method and its applications.
• One particularly interesting application: how to resolve an LP after adding a new inequality constraint, without having to redo everything from scratch.

• Discussion of Midterm 1.

• Matrix Games: von Neumann's theorem on the existence of Nash Equilibria, and its simple proof via LP duality.
• Farkas's Lemma.
• Strong separation of a convex polyhedron and a point in the exterior, weak separation of two closed convex non-intersecting sets.

• Download HOMEWORK 3 for undergraduate students and for grads. The deadline is November 4, Tuesday.
• Variations of Farkas's Lemma
• Some applications of Farkas's Lemma: "no arbitrage = state prices", etc.
• The importance of separation in nonlinear optimization.
• Large scale optimization: Delayed column generation.

• Example for delayed column generation: the cutting stock problem.
• The Primal-Dual framework, and an application: the Primal-Dual simplex method.

• Integer Programming - Examples.

• Integer Programming - More examples, including Networks and Flows.
• The Maximum Flow problem.

• Download HOMEWORK 4 for undergraduate students and for grads. The deadline is November 18, Tuesday.
• The algorithm of Ford and Fulkerson, and its proof of correctness based on the primal-dual method.
• The Minimum Cut problem, and its solution.

• The max flow-min cut theorem.
• The Integrality Lemma in networks.
• Applications of the above theorems in combinatorics.

• Review session before the midterm; discussion of homework solutions.

• Second midterm exam -- postponed owing to the power cut :( .

• Second midterm exam.

• Integer Programming algorithms I: Branch-and-Bound.

• Discussion of the second midterm solutions.
• LP relaxations of IPs, weaker and stronger formulations.
• Integer Programming algorithms II: Gomory cutting planes.

• The last class: final exam review session.