IE 631 Integer Programming

IE 631 Integer Programming, Spring 2023

TTh 9:00 - 10:15 am, E2-2 #1122

Instructor: Dabeen Lee (E2-2 #2109)
Email: dabeenl [at] kaist [dot] ac [dot] kr
Office hours: TBD

Teaching Assistant: Seungyoon Choi (Email: csyoon08 [at] kaist [dot] ac [dot] kr)

Text: We will use and closely follow the following textbook throughout the course.

Syllabus (pdf)

Many real-world decision-making problems require decisions over a discrete set of available choices. For example, on/off constraints and decisions for inclusion/exclusion can be modeled with binary variables. Moreover, one would face scenarios where we choose a decision from disjunctive and disjoint sets of choice options. Integer programming provides a general and comprehensive framework to model such decision-making settings. This course will cover the fundamental subjects of integer programming that are relevant to both theory and practice. Students will learn the mathematical theory behind integer programming, integer programming formulations, cutting plane algorithms, and decomposition-based algorithms, all of which are implemented in state-of-the-art commercial software.

Announcements

Lecture notes

  1. Tue 2/28: Introduction (lecture note)
  2. Thu 3/02: Terminologies and Complexity of integer programming (lecture note)
  3. Tue 3/07: Convex hull and Valid inequalities (lecture note)
  4. Thu 3/09: Deriving the convex hull of a two-variable mixed integer set, Branch-and-cut method (lecture note)
  5. Tue 3/14: Hermite normal form, Solving the equality constrained integer feasibility problem (lecture note)
  6. Thu 3/16: Integer programming formulation I: {Knapsack problem, Minimal Covers} (lecture note)
  7. Tue 3/21: Integer programming formulation II: {Cutting stock problem, Set packing, partitioning, and covering, Stable set problem, st-paths and st-cuts, Airline crew scheduling} (lecture note)
  8. The 3/23: Integer programming formulation III: Mixing set, Two-stage inventory planning, Chance-constrained programming, Union of Polytopes (lecture note)
  9. Tue 3/28: Polyhedral theorey I: {Fourier-Motzkin elimination, Farkas' lemma, {linear, convex, conic, affine} combinations, Minkowski-Weyl theorem for cones} (lecture note)
  10. Thu 3/30: Polyhedral theorey II: {Minkowski-Weyl theorem for general polyhedra, Recession cones, Lineality space, Implicit equalities} (lecture note)
  11. Tue 4/04: Polyhedral theorey III: {Faces, Redundant inequalities and Facets, Extreme points and extreme rays} (lecture note)
  12. Thu 4/06: Minimum cost flow problem, Total unimodularity, Ghouila-Houri's bicoloring theorem (lecture note)
  13. Tue 4/11: Shortest path, Maximum st-flow, Minimum st-cut, Max-flow Min-cut theorem (lecture note)
  14. Thu 4/13: Bipartite matching (unweighted and weigthed), Uncapacitated lot-sizing (lecture note)
  15. Tue 4/25: Chvátal-Gomory cuts, Chvátal's rounding procedure, Odd-set inequalities for the matching polytope (lecture note)
  16. Thu 4/27: Chvátal closure, Gomory's fractional cuts (lecture note)
  17. Tue 5/02: Split cuts, Gomory's mixed-integer cuts (lecture note)
  18. Thu 5/04: Lift-and-project, Lovász-Schrijver hierarchy, Sherali-Adams Hierarchy (lecture note)
  19. Tue 5/09: Lagrangian relaxation, Lagrangian dual (lecture note)
  20. Thu 5/11: Lagrangian relaxation for the uncapacitated facility location problem, Subgradient algorithm for Lagrangian dual (lecture note)
  21. Thu 5/18: Row and column generation for large-scale models (lecture note)
  22. Tue 5/23: Dantzig-Wolfe decomposition, Column generation for the Dantzig-Wolfe reformulation (lecture note)
  23. Thu 6/01: Branch-and-price method, Benders decomposition (lecture note)
  24. Thu 6/08: Ellipsoid algorithm and equivalence between optimization and separation (lecture note)

Assignments

  1. Assignment 1: Exercises 1.8, 1.10, 1.12, 1.14, 1.15, 1.25
  2. Assignment 2: Exercises 2.1, 2.16, 2.17, 2.18, 2.26, 2.33
  3. Assignment 3: Exercises 3.7, 3.22, 3.33, 4.5, 4.6, 4.12
  4. Assignment 4: Exercises 4.20, 5.1, 5.3, 5.4, 5.8, 5.10