Math 567 (Spring 2025): Lecture Notes and Videos on Integer Optimization
|
Copyright: I (Bala Krishnamoorthy) hold the copyright
for all lecture scribes/notes, documents, and other
materials including videos posted on these course web
pages. These materials might not be used for commercial
purposes without my consent.
|
Scribes from
all lectures so far (as a single big file)
| Lec | Date | Topic(s) | Scribe | Video |
| 1 |
Jan 7 |
syllabus,
optimization in calculus, 2D linear program example,
convexity, piecewise linear (PL) convex function, min-max
problem as LP
|
Scb1
|
Vid1
|
| |
Jan 9 |
no
lecture
|
| 2 |
Jan 14 |
knapsack with \(P \cap \mathbb{Z}^2 = \emptyset\), general
forms: MIP, IP, binary IP (BIP); assignment, knapsack, fixed
charge MIP, integactive fixed charge
|
Scb2
|
Vid2
|
| 3 |
Jan 16 |
\(\max\{\cdot,\cdot\} \leq b\) as LP, uncapacitated lot
sizing (ULS), smallest \(M_t\), nonconvex PL function,
semincontinuous var, model with 0-1 vars
|
Scb3
|
Vid3
|
| 4 |
Jan 21 |
conjunctive normal form (CNF); 0-1 and continuous vars,
big-\(M\) representation of disjunction, recession cone,
sharp rep. of disjunction
|
Scb4
|
Vid4
|
| 5 |
Jan 23 |
b-MIP-r sets, formulation, representing function \(f\),
graph/epi/hypo\((f)\), graph\((f)\) is b-MIP-r iff
epi\((f)\)+hypo\((f)\) both are, Farkas' lemma
|
Scb5
|
Vid5
|
| 6 |
Jan 28 |
projection, comparing formulations, projection cone, find
\(\mathbf{x} \in P_2 \setminus P_1\) to show \(P_1 \subset
P_2 \), dis/aggregated formulation, sharp formulation
|
Scb6
|
Vid6
|
| 7 |
Jan 30 |
sharp formulation\(\Leftrightarrow\)integral corner points,
examples of sharp formulation, \(\cap_{(i,j)} P_{ij}\) not
sharp for \(\cap_{(i,j)} S_{ij}\), TSP
formulations, subtours
|
Scb7
|
Vid7
|
| 8 |
Feb 4 |
node position vars \(u_i\), MTZ formulation of TSP, subtour
constraint: \(\sum_{i,j \in W} x_{ij} \leq |W|-1\),
comparing MTZ and subtour, Proj\(_{\mathbf{x}}(P_{\rm
MTZ})\)
|
Scb8
|
Vid8
|
| 9 |
Feb 6 |
circulations, subtour is sharper for TSP, proving sharpness
for disjunction using valid inequalities, definitions and
results on polyhedra
|
Scb9
|
Vid9
|
| 10 |
Feb 11 |
Motzkin's decomposition: polyhedron \(P = Q + C\)
(polytope+cone), implicit equality, face(t), dimension of
polytope, integral polyhedra
|
Scb10
|
Vid10
|
| 11 |
Feb 13 |
unimodular, \(\{\mathbf{x} | A \mathbf{x} =
\mathbf{b},\mathbf{x} \geq \mathbf{0}\}\)
integral\(\Leftrightarrow\)\(A\) unimodular, total
unimodularity (TU), checking TU in poly time, operations
preserving TU
|
Scb11
|
Vid11
|
| 12 |
Feb 18 |
TU sufficient condition, min-cost flow on directed
graph, node-arc incidence matrix is TU, LP duality
review, total dual integrality (TDI)
|
Scb12
|
Vid12
|
| 13 |
Feb 20 |
TDI system \(\Rightarrow P\) integral, \(P\) integral but
system not TDI, \(P\) integral \(\Rightarrow\) can describe
by a TDI system, AMPL: knapsack
feasibility IP
|
Scb13
|
Vid13
|
| 14 |
Feb 25 |
generic branch-and-bound (BB), correctness of BB algo,
details for \(k=2\), pruning nodes, BB for
knapsack: illustration
using AMPL
|
Scb14
|
Vid14
|
| 15 |
Feb 27 |
best-node-first and depth-first search BB strategies,
reduced cost fixing, types of branching: binary & integer
branching on variable
|
Scb15
|
Vid15
|
| 16 |
Mar 4 |
binary and integer branching on constraint, Jeroslow's IP,
feasibility version, cutting planes, Chvatal-Gomory (CG)
cut, integer case
|
Scb16
|
Vid16
|
| 17 |
Mar 6 |
mixed integer rounding (MIR), mixed integer Gomory (MIG) cut,
Hiker's
tour project, knapsack cover inequality, extension of
cover
|
Scb17
|
Vid17
|
| 18 |
Mar 18 |
extension of a cover, lifting, lifted cover cut,
lifting bound from LP relaxation, separation problem,
separating \(\mathbf{x}^*\) using cover inequality
|
Scb18
|
Vid18
|
| 19 |
Mar 20 |
disjunctive cuts, Lovasz-Schrijver (LS) procedure,
odd-hole inequality, \(Q_j(K) = \) conv\(([K \cap
(x_j=0)]\cup [K \cap (x_j=1)])\) with proof
|
Scb19
|
Vid19
|
| 20 |
Mar 25 |
lifting inequality for polytope, disjunctive
convexification, disjunctive programming (DP),
theoretical cutting plane algo, "bad" instance
|
Scb20
|
Vid20
|
| 21 |
Mar 27 |
facial disjunction, practical algo for DP, rank of
cuts, example on complete graph, LS rank is \(k-2\),
semidefinite relaxation rank is 1
|
Scb21
|
Vid21
|
| 22 |
Apr 1 |
heuristics for large-scale receiver (facility) location:
greedy algo, clean-up, \(t\)-hard to cover, generalized
scoring function, preprocessing
|
Scb22
|
Vid22
|
Last modified: Tue Apr 01 18:00:37 PST 2025
|