Derrick Stolee, Assistant Professor
Department of Mathematics
Department of Computer Science
Iowa State University

MATH 566 - Discrete Optimization
Course Information
 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

Since the early days of combinatorics, we have been asking ourselves questions, such as

Why are some problems harder than others?

What is the difference between finding a solution and an optimal solution?

This problem is hard.'' How can I solve it anyway?

In this course, we will aim to answer this question for a variety of combinatorial problems by investigating the relationship between combinatorial algorithms, linear and integer programming, and matroids. Along the way, we will discuss several algorithms and investigate connections between them. For instance, we will develop polynomial-time algorithms for Maximum Flows, Maximum Matchings, and related problems. By investigating Integer Programming and the Traveling Salesman Problem, we will find that some problems do not have known polynomial-time algorithms, but we can solve them (sometimes) using cutting planes and branch-and-bound. Finally, we show that whenever a greedy algorithm works for a given problem, it is usually due to the existence of a related matroid.
Homework
Homework provides short problems that allow you to demonstrate knowledge of the course material. Problems are given during lecture and will be listed here. Every other Monday, a list of the problems will be marked as assigned, due the following Wednesday. All assigned solutions should be typed.

Due to Labor Day, Homework 1 will be assigned Wednesday 09/04 and due Friday 09/06.

 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 Reports
Implementation reports are a way for you to gain experience using computers to solve optimization problems and reporting your solution to someone else. Quality of writing is as important as the technical content. An example assignment and report is given for your benefit.

 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

Sage Worksheets
To install Sage, go to http://sagemath.org/ and follow the download links. Some warnings: for Mac OS X users, the "App" version may require you to first install and run the command-line version first. Don't forget to look to the bottom of this page for resources on how to use Sage.

 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.

Lecture Notes
Week 1
Week 2
Week 3
Week 4
Week 5
Week 6
Week 7
Week 8
Week 9
Week 10
Week 11
Week 12

Exams
Midterm Exam: October 25, 9:00-9:50am.

24-Hour Take-Home Final Exam: December 19, 5:00pm-December 20, 5:00pm.

Topic List
 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: Example 1: (Sage) Example 2: (Sage) F 11/08 Branch-and-Bound for TSP Sage Examples: Example 1: (Sage)Example 2: (Sage)Example 3: (Sage)
Other Resources
T. S. Ferguson, Linear Programming: A Concise Introduction.

J. H. van Lint and R. M. Wilson, A Course in Combinatorics, Cambridge Univ. Press.

Traveling Salesman Heuristic Animations.

Bipartite Matching Algorithm Video Tutorials:
The Augmenting Paths Algorithm for Bipartite Matching
The Augmenting Paths Algorithm for Bipartite Matching (Example)
The Hungarian Algorithm
An Example of the Hungarian Algorithm

The Simplex Method Video Tutorial:
Setup and Notation
Relative Cost
Organization of a Tableau
Organization of a Tableau (Example)
Performing a Pivot in the Tableau
Performing a Pivot in the Tableau (Example)

The Single-Stage Simplex Algorithm
The Single-Stage Simplex Algorithm (Example)

Sage
Graph Theory
Linear Programming in Sage, by Nathann Cohen
Linear Programming
Mixed integer linear programming

GNU Linear Programming Kit

Wikipedia
Linear Programming
Duality
Farkas' Lemma
Simplex Algorithm
LP Relaxation
Integer Points in Convex Polyhedra
Semidefinite Programming