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

MATH 566 - Discrete Optimization
Course Information

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

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 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 Solutions (Sage)
match1.csv match2.csv match3.csv match4.csv
IR 4 (PDF) (TeX) W 11/20
IR 5 (PDF) (TeX) W 12/11 (Sage)
tsp1.csv tsp2.csv tsp3.csv tsp4.csv

Sage Worksheets
To install Sage, go to 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.

Here are some example sage worksheets to help you with your computer implementations.

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

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/26Course Syllabus, Intro to Linear and Combinatorial Optimization, Linear Programs in Canonical, Standard, and General Form.
W 08/28Conversions between forms of LP, Shortest Paths as an LP.
F 08/30Solving standard-form LPs, bases, basic feasible solutions, a bit about simplex.
M 09/02Labor Day. No Class.
W 09/04Forming duals of standard and canonical form LPs. Weak Duality. The SOB(V) Method.
F 09/06Forming dual of general form LP. Combinatorial interpretation of duality for Diet Problem and Shortest Paths.
M 09/09Proof of Strong Duality from the Farkas' Lemma.
W 09/11Flow networks, Maximum flows, linear programming formulations: edge-centric and path-centric.
F 09/13Equivalence of edge-centric and path-centric formulations. Dual of maximum flows: Combinatorial dual and linear dual.
M 09/16Cuts and their capacity, Max-Flow, Min-Cut Theorem, Augmenting Paths.
W 09/18Augmenting Paths, Performing augmentations on flows, Auxiliary graph, proof of max-flow/min-cut.
F 09/20The Augmenting Path algorithm, Breadth-First-Search, Solutions to In-Class Worksheet.
M 09/23Applications of max flows: matchings and vertex covers, Kónig's Theorem.
W 09/25Optimal closures in digraphs, flow feasibility problems..
F 09/27Generalized flow feasibility problems, Hoffman's Circulation Theorem.
M 09/30Connectivity in undirected graphs, local and global edge-connectivity.
W 10/02Multi-commodity Flows, Matchings in general graphs.
F 10/04Matchings in general graphs. Deficiency and the Berge-Tutte Formula (proof later).
M 10/07Matchings and covers in weighted bipartite graphs and duality.
W 10/09The Augmenting Paths algorithm for max matching, the Hungarian algorithm for max weighted perfect matching, and min weighted vertex cover.
F 10/11Matchings 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/16Edmonds' Blossom algorithm for perfect matchings in general graphs, maximum matchings.
F 10/18Stable matchings given preferences between balanced sets, Gale-Shapely Proposal Algorithm.
M 10/21Unimodularity and total unimodularity, integrality of linear programs.
W 10/23More on total unimodularity, total unimodularity of shortest paths, weighted perfect matching, and max flows.
F 10/25Integer programming. What makes it special? A bit of complexity theory.
M 10/28Strength of Integer Programming. Reduction from CNF-SAT to IP. TSP as MILP.
W 10/30Encoding logic into an IP. Start of Branch-and-Bound.
F 11/01More on branch-and-bound. Customized Branch-and-Bound for TSP.
M 11/04Local search for TSP.
W 11/06Branch-and-Bound Sage Examples:
F 11/08Branch-and-Bound for TSP Sage Examples:
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)

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

GNU Linear Programming Kit

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