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


Last modified: Sun Apr 28 16:40:37 PDT 2019