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. |

- Problem Set 1, due September 5.
- Problem Set 2, due September 12.
- Problem Set 3, due September 19.
- Problem Set 4, due September 26. (.tex)
- Problem Set 5, due October 3. (.tex)
- Problem Set 6, due October 10. (.tex)
- Problem Set 7, due October 17. (.tex)
- Problem Set 8, due October 31. (.tex)
- Problem Set 9, due November 7. (.tex)
- Problem Set 10, due November 14. (.tex)
- Problem Set 11, due November 21. (.tex)
- Problem Set 12, due December 5. (.tex)