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