Thursday, May 28 (PDF):
combinatorial optimization overview and examples, linear programming
intro example, LP formulation, “anatomy” of an LP, solving
an LP with Maple.
Friday, May 29 (PDF): LP
terminology, possible outcomes of solving an LP, graphical solution
process, matrix form of LP, basic feasible solutions. (Updated
June 5—now with color!)
Monday, June 1 (PDF): convex
combinations and extreme points, geometry of basic feasible solutions,
simplex tableau and pivoting.
Tuesday, June 2 (PDF): rules for
pivoting, objective row of tableau, choosing pivot column, essential
outline of the simplex algorithm.
Wednesday, June 3 (PDF): nonstandard
variable domains, general constraints in the simplex algorithm,
two-phase simplex algorithm.
Thursday, June 4 (PDF): introduction
to duality, form of the dual for general LPs.
Friday, June 5 (PDF): weak and
strong duality theorems, complementary slackness, dual solution in the
optimal simplex tableau. (Updated June 16.)
Monday, June 8 (PDF): critical path
method, CPM network, earliest and latest times, floats, critical
activities and paths, crash times, LP formulations.
Tuesday, June 9 (PDF):
transportation problem, primal and dual LPs, theorems about optimality,
test values.
Wednesday, June 10 (PDF):
transportation algorithm, transportation tableau, initial basic
feasible solution, calculation of dual variables and test values,
pivoting, example.
Thursday, June 11 (PDF):
shortest-path problem, node-arc incidence matrix, LP formulation and
its dual, optimal solutions, preview of primal-dual algorithm.
Friday, June 12 (PDF): primal-dual
algorithm, admissible columns, restricted primal and its dual,
adjustment of dual solution.
Monday, June 15 (PDF): primal-dual
algorithm for shortest-path problem, example, observations.
Tuesday, June 16 (PDF):
Dijkstra’s algorithm, example, definitions from graph
theory.
Wednesday, June 17 (PDF):
simple results about vertex degrees, minimum spanning tree problem,
Prim’s algorithm, Kruskal’s algorithm.
Thursday, June 18 (PDF): max-flow
problem, LP formulation, application of primal-dual method, augmenting
paths, auxiliary network, example.
Friday, June 19 (PDF): max-flow LP
and its dual, max-flow min-cut theorem, Ford–Fulkerson algorithm,
example.
Monday, June 22 (PDF): bipartite
graphs, maximum matching problem, augmenting paths for matching,
bipartite matching via augmenting paths and via max flow.
Tuesday, June 23 (PDF): integer
programming, LP relaxation, example showing that rounding is not
sufficient, IP formulation for knapsack problem, domains in IPs,
solving IPs in Maple, IP formulation guidelines, IP formulations for
set covering and start-up costs.
Wednesday, June 24 (PDF): IP
formulation examples, minimum batch size, piecewise linear functions,
Boolean satisfiability problem.
Thursday, June 25 (PDF):
branch-and-bound algorithms for IPs and the knapsack problem.
Friday, June 26 (PDF): some hard
problems and their IP formulations: traveling salesman, Hamiltonian
circuit (and contrast with Eulerian circuit), independent set, maximum
clique, chromatic number, minimum vertex cover, minimum dominating set,
subset sum, bin packing, betweenness, minimum set cover.
Monday, June 29 (PDF): introduction
to computational complexity, problems vs. instances, time bounds,
elementary operations, asymptotic notation.
Tuesday, June 30 (PDF): more
asymptotic notation, comparison of common functions, the size of an
instance, analysis of algorithms, polynomial-time algorithms.
Wednesday, July 1 (PDF): three
versions of a combinatorial optimization problem (optimization,
evaluation, and decision), binary search for solving the evaluation
version, P and NP, certificates and verifiers.
Thursday, July 2 (PDF): examples of
problems in NP (2- and 3-COLORABILITY, HAMILTONIAN CIRCUIT,
SAT, ILP), complement of a decision problem, the class co-NP,
polynomial-time reductions and transformations, NP-completeness.
Monday, July 6 (PDF): Turing
machines, NP defined with Turing machines as verifiers, Cook’s
theorem.
Tuesday, July 7 (PDF): more
NP-complete problems: CNF-SAT, ILP, 0–1 ILP, 3-SAT, CLIQUE,
INDEPENDENT SET.
Wednesday, July 8 (PDF): still more
NP-complete problems: HAMILTONIAN CIRCUIT, TSP, HAMILTONIAN PATH,
LONGEST PATH; NP-hardness, approaches to NP-hard problems.
Problem set 5 (PDF,
TeX, MetaPost;
compiled MPS figure): assigned Monday,
June 15; due Thursday, June 18. (Updated June 16:
“directed” in Problem 4 should have been
“undirected.”)