Time and place | Monday through Friday, 1:30–3:00, in Wean Hall 7218 |
---|---|

Instructor | Brian Kell |

bkell@cmu.edu | |

Office | Wean Hall 6211 |

Office hours | Monday through Friday, 12:30–1:30 and 3:00–4:00, or by appointment |

Teaching assistant | Michael Druggan |

- Syllabus (PDF, TeX): updated Monday, June 1.
- Analysis of a simplex tableau (PDF, TeX).
- Pivot a simplex tableau.
- Transportation problem example, in detail (PDF, TeX, MetaPost, TeX macros; compiled MPS figures: 1, 2, 3, 4).
- IP formulation examples (PDF, TeX).
- Makefile for all of the PDFs here.

- 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.
- Thursday, July 9 (PDF): the halting problem.

- Problem set 1 (PDF,
TeX): assigned Thursday, May 28; due
Monday, June 1.
- Solutions (PDF, TeX, figure for Problem 2).

- Problem set 2 (PDF, TeX): assigned Monday, June 1; due Thursday, June 4.
- Problem set 3 (PDF, TeX): assigned Thursday, June 4; due Monday, June 8.
- Problem set 4 (PDF, TeX): assigned Tuesday, June 9; due Friday, June 12.
- 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.”)
- Midterm exam (PDF, TeX; rules: PDF, TeX; common TeX include file): released Thursday, June 18; due Monday, June 22.
- Problem set 6 (PDF, TeX, MetaPost; compiled MPS figures: 3, 5): assigned Monday, June 22; due Thursday, June 25.
- Problem set 7 (PDF,
TeX): assigned Friday, June 26; due
Wednesday, July 1. (Updated June 30: the objective function
in Problem 5 should be
2
`x`_{1}+ 3`x`_{2}.) - Problem set 8 (PDF, TeX): assigned Thursday, July 2; due Thursday, July 9.
- Final exam (PDF,
TeX, MetaPost; compiled
MPS figures:
1, 2):
given July 14.
- Solutions (PDF, TeX, MetaPost; compiled MPS figures: Ford–Fulkerson, new flow).

Last updated 22 July 2015. Brian Kell <bkell@cmu.edu>