Math 567 (Spring 2019) - 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 8
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 10
piecewise linear (PL) convex function, MIP, IP, and binary IP
(BIP), assignment, knapsack, fixed charge, interactive fixed
charge
scribe
video
3
Jan 15
\(\max\{\cdot\} \leq b\) as LP, uncapacitated lot sizing (ULS),
smallest \(M_t\) (forcing constraint), general PL function,
semicontinuous variable
scribe
video
4
Jan 17
model with 0-1 vars, conjunctive normal form (CNF); 0-1 and
continuous vars, big-M representation of disjunction, recession
cone
scribe
video
5
Jan 22
sharp representation of disjunction, b-MIP-r sets, formulation,
representing function \(f\), graph\((f)\), epi\((f)\),
hypo\((f)\), b-MIP-r epi\((f)\)
scribe
video
6
Jan 24
Farkas' lemma, projection, comparing formulations, projection
cone, aggregated and disaggregated formulations, sharp
formulation
scribe
video
7
Jan 29
convex hull, sharp formulation \(\Leftrightarrow\) integral
corner points, \(n\) linearly independent constraints, examples
of sharp formulation
scribe
video
8
Jan 31
formulations for 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 5
Proj\(_{\mathbf{x}}(P_{\rm MTZ})\), circulations, finitely
generated by cycles, proving sharpness of formulation for
disjunction using valid inequalities
scribe
video
10
Feb 7
definitions and results on polyhedra, polyhedral cone, Motzkin's
decomposition, implicit equality, face, facet, dimension of
polytope
scribe
video
11
Feb 12
integral polyhedra, unimodular, \(\{\mathbf{x} | A \mathbf{x} =
\mathbf{b}, \mathbf{x} \geq \mathbf{0}\}\)
integral\(\Leftrightarrow A\) is unimodular, total unimodularity
(TU), checking TU in poly time
scribe
video
12
Feb 14
*make-up*: operations preserving TU, sufficient condition
for TU, min-cost flow on directed network, node-arc incidence
matrix
scribe
video
13
Feb 19
LP duality review, totally dual integral (TDI) system, \(P\)
integral \(\Rightarrow\) can describe by a TDI system, max flow
as circulation
**(updated!)**
scribe
video
14
Feb 21
intro to AMPL, knapsack feasibility
problem, generic branch-and-bound (BB) algorithm
scribe
video
15
Feb 26
correctness of BB algo, details for \(k=2\), prune node by
optimality, bound, infeasibility; illustration,
best-node-first (BNF) strategy
scribe
video
16
Feb 28
disadvantages of BNF, depth-first search (DFS), example, reduced
cost fixing, types of branching: binary, integer branching on
var
scribe
video
17
Mar 5
binary and integer branching on constraint, Jeroslow's IP,
feasibility version, cutting planes, Chvatal-Gomory (CG) cut,
integer case
scribe
video
18
Mar 7
Hiker's tour
project, mixed integer rounding (MIR), mixed integr Gomory (MIG)
cut, knapsack cover inequality, extension of cover
scribe
video
Mar 19
*no lecture**
*
19
Mar 21
extension of a cover, lifting, lifting bound from LP, separation
problem, separating \(\mathbf{x}^*\) using cover inequality
scribe
video
20
Mar 26
*make-up*: disjunctive cuts, Lovasz-Schrijver procedure,
odd-hole inequality, \(Q_j(K) = \) conv\(([K \cap (x_j=0)]\cup
[K \cap (x_j=1)])\)
scribe
video
21
Mar 28
proofs for \(P_j(K) \subseteq Q_j(K)\), lifting inequality
for face to whole polytope, disjunctive convexification,
disjunctive programming (DP)
scribe
video
22
Apr 2
DP: theoretical cutting plane algo, "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 9
receiver location: \(t\)-hard to cover, generalized scoring
function, preprocessing, complete heuristic, IP formulation,
heuristics steps
scribe
video
25
Apr 11
variants of setcover: budget constraint, existing/new
facilities, \(p\)-center/median problems, relax integrality of
\(y_{ij} \in \{0,1\}\), heuristics
scribe
video
26
Apr 16
absolute \(p\)-center, local center (l.c.), conditions for
existence of l.c., hard knapsack problem, decomposable knapsack:
\(\mathbf{a}=\mathbf{p}M + \mathbf{r}\)
scribe
video
27
Apr 18
lattices, basis, shortest and closest vector problems (SVP,
CVP), reduced basis, Gauss reduction, Korkine-Zolotarev
reduction
scribe
video
28
Apr 23
setcovering
project, Lenstra-Lenstra-Lovasz
(LLL) reduction, properties, Hermite normal form (HNF),
elementary column operations
scribe
video
29
Apr 25
proof of IP "Farkas' Lemma", BR in IP, rangespace reformulation,
\(\mathbf{y} = U^{-1} \mathbf{x}\), cascade
knapsack problems
scribe
video

Last modified: Sun Apr 28 16:40:37 PDT 2019