|
Lecture Time: MWF 9:00-9:50am Room: 1071 Black Eng. |
Office Hours Office: 416 Carver Time: M 10:00-10:50am T 12:00-1:00pm |
| Syllabus |
| Homework | Due Date | Files | Solutions |
| HW 1 | 09/06 | PDF TeX | PDF TeX |
| HW 2 | 09/20 | PDF TeX Figures: 1 2 3 4 5 | PDF TeX |
| HW 3 | 10/09 | PDF TeX Figures: (Zip) | Solutions |
| HW 4 | 10/23 | PDF TeX Figures: 1 2 | Solutions |
| HW 5 | 11/11 | PDF TeX Figure: 1 | Solutions |
| HW 6 | 12/05 | PDF TeX Figure: 1 |
| Implementation Report | Due Date | Files | Example Report |
| IR 0 (PDF) | (Example) | reach1.txt reach2.txt | (PDF) (TeX) (Sage) |
| IR 1 (PDF) (TeX) | F 09/13 | lp3.txt lp4.txt | Solutions (Sage) |
| IR 2 (PDF) (TeX) | W 10/02 | I1 I2 flow3.txt flow4.txt | Solutions (Sage) |
| IR 3 (PDF) (TeX) | W 10/30 | match1.py match2.py match3.py match4.py | Solutions (Sage) |
| match1.csv match2.csv match3.csv match4.csv | |||
| IR 4 (PDF) (TeX) | W 11/20 | ||
| IR 5 (PDF) (TeX) | W 12/11 | tsp1.py tsp2.py tsp3.py tsp4.py | (Sage) |
| tsp1.csv tsp2.csv tsp3.csv tsp4.csv |
| Worksheet | Posted | Covered Topics |
| LP Example | 09/04 | How to set up a linear program, solve it, and display the final answer. How to handle exceptions when the program is unbounded or infeasible. |
| M 08/26 | Course Syllabus, Intro to Linear and Combinatorial Optimization, Linear Programs in Canonical, Standard, and General Form. |
| W 08/28 | Conversions between forms of LP, Shortest Paths as an LP. |
| F 08/30 | Solving standard-form LPs, bases, basic feasible solutions, a bit about simplex. |
| M 09/02 | Labor Day. No Class. |
| W 09/04 | Forming duals of standard and canonical form LPs. Weak Duality. The SOB(V) Method. |
| F 09/06 | Forming dual of general form LP. Combinatorial interpretation of duality for Diet Problem and Shortest Paths. |
| M 09/09 | Proof of Strong Duality from the Farkas' Lemma. |
| W 09/11 | Flow networks, Maximum flows, linear programming formulations: edge-centric and path-centric. |
| F 09/13 | Equivalence of edge-centric and path-centric formulations. Dual of maximum flows: Combinatorial dual and linear dual. |
| M 09/16 | Cuts and their capacity, Max-Flow, Min-Cut Theorem, Augmenting Paths. |
| W 09/18 | Augmenting Paths, Performing augmentations on flows, Auxiliary graph, proof of max-flow/min-cut. |
| F 09/20 | The Augmenting Path algorithm, Breadth-First-Search, Solutions to In-Class Worksheet. |
| M 09/23 | Applications of max flows: matchings and vertex covers, Kónig's Theorem. |
| W 09/25 | Optimal closures in digraphs, flow feasibility problems.. |
| F 09/27 | Generalized flow feasibility problems, Hoffman's Circulation Theorem. |
| M 09/30 | Connectivity in undirected graphs, local and global edge-connectivity. |
| W 10/02 | Multi-commodity Flows, Matchings in general graphs. |
| F 10/04 | Matchings in general graphs. Deficiency and the Berge-Tutte Formula (proof later). |
| M 10/07 | Matchings and covers in weighted bipartite graphs and duality. |
| W 10/09 | The Augmenting Paths algorithm for max matching, the Hungarian algorithm for max weighted perfect matching, and min weighted vertex cover. |
| F 10/11 | Matchings in general graphs, proof of Berge-Tutte Formula from Tutte's Theorem, $M$-Alternating trees |
| M 10/14 | $M$-alternating trees, $M$-augmenting paths, tight cycles and shrinking cycles. |
| W 10/16 | Edmonds' Blossom algorithm for perfect matchings in general graphs, maximum matchings. |
| F 10/18 | Stable matchings given preferences between balanced sets, Gale-Shapely Proposal Algorithm. |
| M 10/21 | Unimodularity and total unimodularity, integrality of linear programs. |
| W 10/23 | More on total unimodularity, total unimodularity of shortest paths, weighted perfect matching, and max flows. |
| F 10/25 | Integer programming. What makes it special? A bit of complexity theory. |
| M 10/28 | Strength of Integer Programming. Reduction from CNF-SAT to IP. TSP as MILP. |
| W 10/30 | Encoding logic into an IP. Start of Branch-and-Bound. |
| F 11/01 | More on branch-and-bound. Customized Branch-and-Bound for TSP. |
| M 11/04 | Local search for TSP. |
| W 11/06 | Branch-and-Bound Sage Examples: |
| F 11/08 | Branch-and-Bound for TSP Sage Examples: |
