Integer Optimization - Lecture Notes and Videos

Math 567 (Spring 2017)  - 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 10 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 12 piecewise linear (PL) functions, min-max problem as LP, general forms: MIP, IP, BIP; assignment, knapsack, fixed charge problem scribe video
3 Jan 17 uncapacitate lot sizing (ULS), general piecewise linear function using slopes and "piece of $$x$$ in $$[v_{i-1},v_i]$$", semicontinuous variable scribe video
4 Jan 19 model with 0-1 vars, literal, clause, conjunctive normal form (CNF); 0-1 and continuous vars, big-M representation of disjunction scribe video
5 Jan 24 recession cone, sharp formulation of disjunction, bounded-MIP-representable sets, definition of formulation, $$\rm{grapf}(f), \rm{epi}(f), \rm{hypo}(f)$$ scribe video
6 Jan 26 Farkas' lemma, projection, cone, projection cone of $$\rm{Proj}_{\mathbf{x}}(P)$$, comparing formulations, aggregated/disaggregated formulation scribe video
7 Jan 31 definition of sharp formulation, convex hull, integral corner points, $$n$$ linearly independent constraints, examples of sharp formulation scribe video
8 Feb  2 formulations for the 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  7 Proj$$_{\mathbf{x}}(P_{\rm MTZ})$$, circulations, finitely generated by cycles, proving sharpness of formulation for disjunction using valid inequalities scribe video
10 Feb  9 definitions and results on polyhedra, polyhedral cone, Motzkin's decomposition, implicit equality, face, dimension of polytope, facet scribe video
11 Feb 14 minimal face, pointed polyhedra, integral polyhedra, unimodular, $$\{\mathbf{x} | A \mathbf{x} = \mathbf{b}, \mathbf{x} \geq \mathbf{0}\}$$ integral$$\Leftrightarrow A$$ is unimodular, totally unimodular scribe video
12 Feb 16 checking total unimodularuity (TU), TU and integrality, operations preserving TU, sufficient condition for TU, network matrix, duality scribe video
13 Feb 21 "normal" variables/constraints, totally dual integral (TDI), $$P$$ integral $$\Rightarrow$$ can be described by a TDI system, max flow as circulation scribe video
14 Feb 23 intro to AMPL, AMPL handout, knapsack feasibility problem; generic branch-and-bound (B&B) scribe video
15 Feb 28 generic B&B algo, updates to $$z_{\ell}, z_u$$, proof of correctness; pruning by infeasibility, bound, and optimality; illustration on knapsack scribe no vid
16 Mar  2 node selection strategies (B&B): best node first (BNF) and depth first search (DFS), (dis)advantages of strategies, reduced cost fixing scribe video
17 Mar  7 types of branching: binary and integer branching on variables and constraints, Jeroslow's IP, feasibility version, hiker's tour project scribe video
18 Mar  9 cutting planes, Chvatal-Gomory (CG) cut, integer case, mixed integer rounding (MIR), mixed integer Gomory (MIG) cut, example scribe video
19 Mar 21 knapsack cover inequalities for binary IPs: $$\mathbf{x}(C) \leq |C|-1$$, extension of a cover, lifting, lifting bound from LP, separation problem scribe video
20 Mar 23 separating $$\mathbf{x}^*$$: example, disjunctive cuts, Lovasz-Schrijver procedure, odd-hole inequality, conv$$([K \cap (x_j=0)]\cup [K \cap (x_j=1)])$$ scribe video
21 Mar 28 two proofs for $$P_j(K) \subseteq Q_j(K)$$, lifting inequality for face to whole polytope, disjunctive convexification, disjunctive programming (DP) scribe video
22 Mar 30 theoretical cutting plane algo for DP, "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   6 receiver location problem: $$t$$-hard to cover meter, generalized scoring function, preprocessing, complete heuristic algorithm scribe video
25 Apr 11 IP formulation for setcover, implementing heuristics, variants: budget constraint, existing/new facilities, $$p$$-center/median problems scribe video
26 Apr 13 relax integrality of $$y_{ij}$$, binary search heuristic for $$p$$-center, greey heuristic for $$p$$-median, absolute $$p$$-center, local center (l.c.) scribe video
27 Apr 18 conditions for existence of l.c., optimal solution using l.c.'s, set covering project, hard knapsack, decomposable knapsack: $$\mathbf{a}=\mathbf{p}M + \mathbf{r}$$ scribe video
28 Apr 20 lattices, basis, shortest and closest vector problems (SVP, CVP), reduced basis, Gauss reduction, Korkine-Zolotarev reduction scribe video
29 Apr 25 Lenstra-Lenstra-Lovasz (LLL) reduction, properties, Hermite normal form (HNF), elementary column operations, IP "Farkas' Lemma" scribe video
30 Apr 27 proof of IP "Farkas' Lemma", BR in IP, rangespace reformulation, $$\mathbf{y} = U^{-1} \mathbf{x}$$, cascade knapsack problems scribe video