Network Flows and Graphs (Fall 2011)

This website contains handouts, lecture notes, and other helpful material for the OA 4202 course, Network Flows and Graphs.

You are invited to read the class syllabus.  Also, students are welcome to ask questions and discuss homework assignments on the Sakai forum for the class.

Student Projects

This quarter we had a lot of excellent student projects.  Here are the projects from all the groups, in alphabetical order by author.

Homeworks

  • HW 0 -- Graph terminology, Storing graphs in a computer.
  • HW 1 -- Search algorithms.
  • HW 2 -- Shortest path problems.
  • HW 3.1 -- Introducing the Drug Lord.  3-1-files
  • HW 3.2 -- Placing road blocks. 3-2-files
  • HW 3.3 -- A more realistic Drug Lord.

Notes

  • Notes 1 -- Review big-Oh, data structures, graph terminology, storing graphs in a computer.
  • Notes 2 -- Intro to shortest path as an LP, graph search (BFS, DFS), applications of search.
  • Notes 3 -- Shortest path algorithms.
  • Notes 4 -- Interdicting shortest paths.
  • Notes 5 -- Maximum flow.
  • Notes 5.1 -- Interdicting max flow.
  • Notes 6 -- Minimum cost flow.
  • Nodes 7 -- Multi-commodity flow.
  • Notes 8 -- Constrained shortest path.
  • Notes 9 -- Network simplex algorithm.

Lecture Contents

  1. Class content overview.  Review big-Oh, data structures.  Start graph terminology.
  2. Finish graph terminology.  Storing graphs in a computer.  Shortest path as an LP.
  3. Graph structure terminology.  Search algorithms.
  4. Go over GAMS Prep.  Go over HW 0.
  1. Applications of search algorithms.  Dijkstra's algorithm.
  2. Go over HW 1.  DAG shortest path.  Critical path method.
  3. A*.  Shortest path as LP.  Shortest path dual.
  4. Exam 0
  1. No class.
  2. Interdicting shortest path.  Benders for shortest path.
  3. Go over HW 2.  Go over GAMS 0.
  4. Benders for shortest path interdiction.  Max-flow, min-cost flow, multicommodity flow.
  1. Max flow.  Max flow dual.  Ford-Fulkerson algorithm.
  2. Go over 3.2.  Ford-Fulkerson as an LP solver.  Producer/consumer.  Flows with lower bounds.
  3. Tanker scheduling. Network reliability.  Job selection.
  4. Exam 1
  1. In-class max-flow modeling.
  2. Go over HW 3.3.  Some general LP modeling tools.
  3. Min-cost-flows.  Min-cost-flow applications.
  4. In-class min-cost-flow modeling.
  1. Constrained shortest path.  Networks simplex algorithm overview.
  2. Quiz.  Nuclear Smuggler Interdiction.
  3. Project presentations.
  4. Project presentations.

This is a completed course.

Related Pages


© Copyright 2004-2017 - Ned Dimitrov