## 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.

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