Instructor: | David P. Williamson |
---|---|
Office: | Rhodes 236 |
Office hours: | M 2:30-3:30, Wed 11-12, and by appointment in Rhodes 236 |
Office phone: | 255-4883 |
Email: | My three initials AT cs.cornell.edu |
Teaching Assistant: | Chaoxu Tong |
Office: | Rhodes 296 |
Office hours: | T 3-4, Th 4:30-5:30, in Rhodes 424 |
Email: | ct423 AT cornell.edu |
The course meets Tuesdays and Thursdays in Hollister 320 from 1:25-2:40 PM. There is a recitation section that meets Wednesdays 3:30-4:30PM in Hollister 320.
This course gives a rigorous treatment of the theory and computational techniques of linear programming and its extensions, including formulation, duality theory, algorithms, sensitivity analysis, network flow problems and algorithms, theory of polyhedral convex sets, systems of linear equations and inequalities, Farkas' lemma, and exploiting special structure in the simplex method and computational implementation. Topics covered will include the ellipsoid method, interior-point methods, and computational complexity issues related to optimization problems.
Aug 27 | Linear algebra review. |
---|---|
Sept 3 | The facility location dual. |
Sept 10 | No recitation. |
Sept 17 | Feasibility and unboundedness. |
Sept 24 | Pointed polyhedra. |
Oct 1 | The transportation problem and network simplex. |
Oct 8 | Uncapacitated network flow and network simplex. |
Oct 15 | A bound on the diameter of a polyhedron. |
Oct 22 | No recitation. | Oct 29 | Approximation algorithms for the knapsack problem. |
Nov 5 | The traveling salesman problem. |
Nov 12 | The minimum-cost spanning tree problem. |
Nov 19 | Lagrangean relaxation and the traveling salesman problem. |
Dec 3 | Approximation algorithms for the traveling salesman problem. |