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

Last modified: Thu Apr 27 18:32:37 PDT 2017