Department of Mathematics Syllabus

This syllabus is advisory only. For details on a particular instructor's syllabus (including books), consult the instructor's course page. For a list of what courses are being taught each quarter, refer to the Courses page.

MAT 258B: Discrete and Mixed-Integer Optimization
Approved: 2011-01-04, Matthias Koeppe

Suggested Textbook: (actual textbook varies by instructor; check your instructor)
Bertsimas, Weismantel: Optimization over Integers, Dynamic Ideas, $95

Prerequisites:

25 and 167, or consent of the instructor

Suggested Schedule:

Lecture(s) Sections Comments/Topics
2 1.1—1.2 Introduction. Classification of Integer Optimization problems. The branch-and-cut algorithm. Principles of modeling. Facility location problem, disaggregated and aggregated formulation. Convex hull and ideal formulations.
1.5 1.3 Modeling with exponentially many constraints: Minimum spanning tree problem, traveling salesperson problem.
1 1.3, 2.1, 3.4 Introduction to methods of enhancing formulations. Matching problem: Valid inequalities from integer rounding, proof of the complete description.
1 2.1, 4.2 Superadditive cuts. Review of linear optimization duality. Superadditive duality.
0.5 2.1, 13.5 Mixed integer rounding.
1 2.2 Stable set problem: Facet-defining inequalities. Lifting.
2 2.3, 3.2 Independence systems, matroids, polymatroids: valid inequalities. Integrality of polymatroids.
1.5 6.1, 8.1, 8.2 Point lattices and their bases, integer normal form, integer Farkas lemma. Integer generating sets of cones.
1.5 8.6 Review of total unimodularity. Total dual integrality. Construction of TDI systems. Intersection of 2 polymatroids.
1 9.1—9.4 Finiteness of cutting-plane procedures based on integer rounding. Construction of the integer hull.
1 5.4 Separation algorithms for TSP cutset inequalities, lifted knapsack covers, and the Chvátal–Gomory closure.
1 5.4 Polynomial-time equivalence of separation/augmentation and optimization.
1 4.3—4.4 Lagrangean duality, subgradient approach to TSP.
1 1.4, * Modeling with exponentially many variables. Dantzig— Wolfe reformulation, column generation, branch-and-price.
1 * Benders decomposition. Generating Benders cuts.
1.5 * Nonlinear integer programming: Generalized Benders, Outer Approximation, Convexification and Spatial Branch-and Bound

Additional Notes:

The indicated number of lectures refers to 80-minute lectures.

* For the topics marked with an asterisk, supplementary material should be provided.