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