Integer Optimization - Lecture Notes and Videos

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

Scribes from all lectures so far (as a single big file)
Lecture videos from AMS (WSU ID+password required)

Lec # Date Topic(s) Scribe Tegrity
1 Jan 13 syllabus, optimization in calculus, 2D example of linear programming (LP), graphical solution, convex sets and functions scribe video
2 Jan 15 piecewise linear function, min-max LP, assignment and \(0\)-\(1\) knapsack problems, logical constraints, fixed charge problem scribe video
3 Jan 20 interactive fixed charge, uncapacitated lot sizing, piecewise linear function,\(A \Rightarrow B \equiv \mbox{not}A \mbox{ or }B\), semicontinuous variable scribe video
4 Jan 22 notes on Homework 1, modeling with \(0\)-\(1\) vars, notation: \(\bigvee,\bigwedge,\Rightarrow,\Leftrightarrow,\neg\); literal, clause, conjunctive normal form (CNF) scribe video
5 Jan 27 \(0\)-\(1\) and continuous vars models, arbitrary disjunctions, recession cone, sharp formulation, b-MIP-r sets, graph/epi/hypo\((f)\) scribe video
6 Jan 29 Farkas' lemma, projection of \(P\), comparing formulations, (dis)aggregated formulation(s), sharp formulation, convex hull scribe video
7 Feb   3 checking all corner points, examples of sharp formulations, bipartite matching, node cover, traveling salesman problem (TSP) scribe video
8 Feb   5 node position vars \(u_i\), Miller-Tucker-Zemlin (MTZ) formulation, subtour formulation, \(\mbox{Proj}_{\mathbf{x}}(P_{\tiny \mbox{MTZ}})\), circulation scribe video
9 Feb 10 subtour formulation is stronger, sharp formulation of disjunction, valid inquality, polyhedral cone, supporting hyperplane scribe video
10 Feb 12 implicit inequality, dim\((P)\), full-dimensional, facet, minimal face, pointed, \(1\)-skeleton of \(P\), intro to AMPL scribe video
11 Feb 17 AMPL: session, Farmer Jones LP: model and data files, knapsack example; well-solved IPs, integral polyhedra scribe video
12 Feb 19 unimodularity and total unimodularity (TU), integrality and TU, sufficient condition for TU: each column has \(\leq\) 2 nonzeros scribe video
13 Feb 24 node-arc incidence matrix of directed network, LP duality, total dual integrality (TDI), TDI of circulation version of max flow scribe video
14 Feb 26 TDI examples:\(P_1\) is nonintegral but TDI; \(P_2\) is integral, not TDI, has TDI representation \(P_3\); generic branch-and-bound (BB) scribe video
15 Mar   3 B&B details for 2 branches, pruning by optimality, bound, infeasiblity, AMPL: hard knapsack problem (data), B&B demo scribe video
16 Mar   5 node selection in B&B, best-node-first (BNF) and depth-first-search (DFS) strategies, reduced cost fixing in B&B for \(0\)-\(1\) IP scribe video
17 Mar 10 hiker's tour problem - project 1, binary and integer branching, branching on constraints, Jeroslow's IP (feasibility version) scribe video
Mar 12 no class
18 Mar 24 Chvatal-Gomory (CG) cuts, mixed integer rounding (MIR), mixed-integer Gomory (MIG) cut, knapsack cut, (minimal) cover scribe video
19 Mar 26 extension of a cover, "lifting" the coefficient of a variable, lifting using LP relaxation, separation problem for \(\mathbf{x}^* \not\in \rm{conv}(X)\) scribe video
20 Mar 31 Lovász-Schrijver (LS) procedure, odd-hole inequality for vertex packing, \(P_j(K) = \rm{conv}([K \cap (x_j=0)] \, \bigcup \, [K \cap (x_j=1)] ) \) scribe video
21 Apr   2 proof for \(P_j(K) \subseteq Q_j(K)\) using lifting, disjunctive convexification and program (DP), theoretical cutting plane algorithm scribe video
22 Apr   7 facial disjunction, a practical cutting plane algorithm, rank of cuts, node packing on complete graph, semidefinite relaxation scribe video
23 Apr   9 receiver location problem, greedy and modified greedy algorithms, hard-to-cover meter, \(t\)-hard to cover, preprocessing scribe video
24 Apr 14 heuristic algorithm, matrix implementation of preprocessing, variants of set covering, covered \(\geq\) twice, existing/new facilites scribe video
25 Apr 16 \(p\)-center and \(p\)-median problems, binary search (\(p\)-center), greedy heuristic (\(p\)-median), absolute \(p\)-median, local center scribe video
26 Apr 21 absolute \(p\)-median example, setcover project, decomposable knapsack problem (DKP) - 2D example, lattice, basis, sublattice scribe video
27 Apr 23 shortest and closest vector problems (SVP,CVP), Gauss reduction (2D), Gram-Shcmidt (GSO), KZ-reduction, LLL-reduction scribe video
28 Apr 28 properties of LLL-reduction, Hermite normal form (HNF), elementary column operations (ecos), a "Farkas' lemma" for IP scribe video
29 Apr 30 proof of "Farkas' lemma" for IP, rangespace reformulation, illustration on 2D DKP, cascade knapsack problems (CKPs) scribe video


Last modified: Thu Apr 30 16:22:37 PDT 2015