- Introduction
Explain the advantages of network formulations over mathematical
programming formulations.
Identify similarities and differences between minimum cost flow, shortest
path, maximum flow, transportation and assignment problems.
Use network and graph terminology accurately.
Navigate data structures used to represent networks on a computer.
Perform transformations on networks.
- Algorithm Design and Analysis
Perform worst-case complexity analysis on a simple algorithm.
Explain the difference between polynomial and exponential time complexity
and its practical implications.
Follow simple algorithms for searching, topological ordering, and
decomposing flows on networks.
- Formulation (note: this is a semester-long theme and the
particular focus of the semester project)
Model a real life optimization problem as a network optimization problem;
i.e., define nodes with their supplies/demands, arcs with their costs and
capacities, and specify an appropriate objective function.
- Shortest Paths
Perform reaching, Dijkstra's, label-correcting, and Floyd-Warshall
algorithms.
Identify when each of the above algorithms is most appropriate.
Formulate a sequential decision problem as a dynamic program by
identifying stages, states, decisions, and a recursive optimal value
function along with a boundary condition, then solve by backward recursion.
- Maximum Flows
Perform the flow-augmenting algorithm and the preflow-push algorithm.
Apply the max flow/min cut theorem.
- Minimum Cost Flows
Perform cycle-canceling, successive shortest path and network simplex
algorithms and explain the relationships, similarities and differences
between them.
Understand residual networks, reduced costs and complementary slackness
and their role in defining optimality conditions.
- Assignments and Matchings
Solve bipartite cardinality matching as a maximum flow problem.
Solve bipartite weighted matching (assignment) as a minimum cost flow
problem.
- Minimum Spanning Trees
Perform Kruskal's and Prim's algorithms and explain their similarities
and differences.
