Computational Discrete Optimization
CO 353, Winter 2016
Class meets in DWE 3518, Tuesday+Thursday 2:30--3:50
Textbook: In Pursuit of the Traveling Salesman + Class Notes
Course covers problem formulations, greedy algorithms, local-search heuristics, approximation algorithms, LP duality, cutting planes, branch-and-bound, column generation, dynamic programming, problem reductions and NP-hardness.
All topics will be introduced using the traveling salesman problem (adopting material in the textbook), followed by a general treatment in the next lecture (adopting material from suggested readings or class notes).
|
Tentative Schedule
Lecture 1: Introduction -- January 5, Chapters 1 and 2
Lectures 2+3: Problem Formulations -- January 7/12, Chapter 3
Lectures 4+5: Greedy Algorithms -- January 14/19, Chapter 4, pages 62-70
Lectures 6+7: Approximation Algorithms -- January 21/26, Chapter 4, pages 70--75
Lectures 8: Local-Search Heuristics I -- January 28, Chapter 4, pages 75-84
Midterm 1: February 2, covers Lectures 1-7
Lecture 9: Local-Search Heuristics II -- February 4, Chapter 4, pages 84-93
Lectures 10+11: LP Duality -- February 9/11, Chapter 5
Reading Week: February 15-19
Lectures 12+13: Cutting Planes -- February 23/25, Chapter 6
Lectures 14+15: Branch-and-Bound -- March 1/3, Chapter 7
Midterm 2: March 8, covers Lectures 8-14
Lectures 16+17: Column Generation -- March 10/15, class notes
Lectures 18+19: Dynamic Programming -- March 17/22, Chapter 9, pages 180-182
Lectures 20+21: Complexity -- March 24/29, Chapter 9
Lecture 22: Review -- March 31, Chapter 12
Final Exam: April 12, 9:00-11:30AM, covers Lectures 1-22
Optional Computational Project (Generalized TSP)