Network Flows and Graphs (Spring 2011)

This page contains the course materials for Network Flows and Graphs, OA4202.

The sidebar contains the class calendar.  The calendar simply lists relevant dates for exams and homework assignments.  You are also invited to read the class syllabus.

Lecture Contents

Here, we list the completed lecture contents.

  1. Review Big-Oh, Review data structures.  Graph terminology.  Start storing graphs in a computer.
  2. Storing graphs in a computer.  Intro to shortest path as an LP.  Graph terminology.
  3. Go over HW 0.  Breadth first search.
  4. Go over GAMS prep.  Depth first search.  Cycle Detection.
  5. Go over HW 1.  Topological Sort.  Strongly Connected Component.
  6. DAG shortest path.  Critical path method.  Dijkstra's algorithm.
  7. A* search.  Unimodularity and shortest path as an LP.
  8. Exam0.
  9. Go over HW 2.  Introduce HW 3.  Interdicting shortest paths.
  10. Shortest path dual.  Solving shortest path interdiction: MIP, Benders.
  11. GAMS basics.  Interdicting shortest paths.  Max-flow problem and definitions.
  12. Max-flow / Min-cut duality and theorem.  Ford-Fulkerson algorithm.  Producer/Consumer.  Flows with lower bounds.
  13. More on Ford-Fulkerson.  Tanker scheduling.  HW 4.
  14. Exam1.
  15. Go over HW 3.2, 3.3.  Discuss project.
  16. HW 4.  Min-cost flow introduction.  Multi-commodity flow introduction.
  17. Min-cost flow relationship to Max-flow, shortest path.  Min-cost flow applications.
  18. Project modeling techniques.  HW 5.

Upcomming Topics

  • Applicatoins of max-flow.
  • Interdicting max-flow.
  • Min-cost flow.
  • Applications of min-cost flow.
  • Successive shortest path algorithm.

Homework Assignments

You are welcome to use the Sakai website to discuss, or ask questions on the homework assigments and class material.

  • Project 0 -- Creating a team and selecting a real-world problem.
  • Project 1 -- Model the real-world problem.
  • Project 2 -- Project deliverables.

Lecture Notes

Some hand written notes on the course material:

  • 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 -- Dijkstra's Algorithm.  DAG shortest path.  A* search.
  • Notes 4 -- Interdicting shortest path.  Shortest path dual.  Benders for interdicting shortest path.
  • Notes 5 -- Max-flow.  Ford-Fulkerson.  Applications of max-flow.
  • Notes 5.1 -- Interdicting max-flow.
  • Notes 6 -- Minimum-cost flows:  Introduction and applications.
  • Notes 7 -- Multi-commodity flows.

© Copyright 2004-2020 - Ned Dimitrov