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:
MAT 127A 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.
* For the topics marked with an asterisk, supplementary material should be provided.