Integer Optimization - Lecture Notes and Videos

Math 567 (Spring 2019)  - Lecture Notes and Videos on Integer Optimization

Scribes from all lectures so far (as a single big file)

Lec # Date Topic(s) Scribe Panopto
1 Jan   8 syllabus, optimization in calculus, 2D linear program example, convex set and function, $$\max_i f_i(\mathbf{x})$$ is convex when $$f_i$$ are so scribe video
2 Jan 10 piecewise linear (PL) convex function, MIP, IP, and binary IP (BIP), assignment, knapsack, fixed charge, interactive fixed charge scribe video
3 Jan 15 $$\max\{\cdot\} \leq b$$ as LP, uncapacitated lot sizing (ULS), smallest $$M_t$$ (forcing constraint), general PL function, semicontinuous variable scribe video
4 Jan 17 model with 0-1 vars, conjunctive normal form (CNF); 0-1 and continuous vars, big-M representation of disjunction, recession cone scribe video
5 Jan 22 sharp representation of disjunction, b-MIP-r sets, formulation, representing function $$f$$, graph$$(f)$$, epi$$(f)$$, hypo$$(f)$$, b-MIP-r epi$$(f)$$ scribe video
6 Jan 24 Farkas' lemma, projection, comparing formulations, projection cone, aggregated and disaggregated formulations, sharp formulation scribe video
7 Jan 29 convex hull, sharp formulation $$\Leftrightarrow$$ integral corner points, $$n$$ linearly independent constraints, examples of sharp formulation scribe video
8 Jan 31 formulations for TSP, subtours, node variables $$u_i$$, MTZ, subtour constraint: $$\sum_{i,j \in W} x_{ij} \leq |W|-1$$, comparing MTZ and subtour scribe video
9 Feb  5 Proj$$_{\mathbf{x}}(P_{\rm MTZ})$$, circulations, finitely generated by cycles, proving sharpness of formulation for disjunction using valid inequalities scribe video
10 Feb  7 definitions and results on polyhedra, polyhedral cone, Motzkin's decomposition, implicit equality, face, facet, dimension of polytope scribe video
11 Feb 12 integral polyhedra, unimodular, $$\{\mathbf{x} | A \mathbf{x} = \mathbf{b}, \mathbf{x} \geq \mathbf{0}\}$$ integral$$\Leftrightarrow A$$ is unimodular, total unimodularity (TU), checking TU in poly time scribe video
12 Feb 14 make-up: operations preserving TU, sufficient condition for TU, min-cost flow on directed network, node-arc incidence matrix scribe video
13 Feb 19 LP duality review, totally dual integral (TDI) system, $$P$$ integral $$\Rightarrow$$ can describe by a TDI system, max flow as circulation (updated!) scribe video
14 Feb 21 intro to AMPL, knapsack feasibility problem, generic branch-and-bound (BB) algorithm scribe video
15 Feb 26 correctness of BB algo, details for $$k=2$$, prune node by optimality, bound, infeasibility; illustration, best-node-first (BNF) strategy scribe video
16 Feb 28 disadvantages of BNF, depth-first search (DFS), example, reduced cost fixing, types of branching: binary, integer branching on var scribe video
17 Mar  5 binary and integer branching on constraint, Jeroslow's IP, feasibility version, cutting planes, Chvatal-Gomory (CG) cut, integer case scribe video
18 Mar  7 Hiker's tour project, mixed integer rounding (MIR), mixed integr Gomory (MIG) cut, knapsack cover inequality, extension of cover scribe video
Mar 19 no lecture
19 Mar 21 extension of a cover, lifting, lifting bound from LP, separation problem, separating $$\mathbf{x}^*$$ using cover inequality scribe video
20 Mar 26 make-up: disjunctive cuts, Lovasz-Schrijver procedure, odd-hole inequality, $$Q_j(K) =$$ conv$$([K \cap (x_j=0)]\cup [K \cap (x_j=1)])$$ scribe video
21 Mar 28 proofs for $$P_j(K) \subseteq Q_j(K)$$, lifting inequality for face to whole polytope, disjunctive convexification, disjunctive programming (DP) scribe video
22 Apr   2 DP: theoretical cutting plane algo, "bad" instance for algo, facial disjunction, practical algo, rank of cuts, example on complete graph scribe video
23 Apr   4 semidefinite relaxation (SDR), example, heuristics for large-scale receiver location problem (facility location): greedy algo, clean-up scribe video
24 Apr   9 receiver location: $$t$$-hard to cover, generalized scoring function, preprocessing, complete heuristic, IP formulation, heuristics steps scribe video
25 Apr 11 variants of setcover: budget constraint, existing/new facilities, $$p$$-center/median problems, relax integrality of $$y_{ij} \in \{0,1\}$$, heuristics scribe video
26 Apr 16 absolute $$p$$-center, local center (l.c.), conditions for existence of l.c., hard knapsack problem, decomposable knapsack: $$\mathbf{a}=\mathbf{p}M + \mathbf{r}$$ scribe video
27 Apr 18 lattices, basis, shortest and closest vector problems (SVP, CVP), reduced basis, Gauss reduction, Korkine-Zolotarev reduction scribe video
28 Apr 23 setcovering project, Lenstra-Lenstra-Lovasz (LLL) reduction, properties, Hermite normal form (HNF), elementary column operations scribe video
29 Apr 25 proof of IP "Farkas' Lemma", BR in IP, rangespace reformulation, $$\mathbf{y} = U^{-1} \mathbf{x}$$, cascade knapsack problems scribe video