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.

Here, we list the completed lecture contents.

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

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

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

- Homework 0 -- Introduction to graphs. Storiing graphs in a computer.
- Homework 1 -- BFS and DFS.
- Homework 2 -- Shortest paths.
- Homework 3.1 -- Introducing the Drug Lord. 3-1-files.zip
- Homework 3.2 -- Computing roadblock locations. 3-2-files.zip
- Homework 3.3 -- A more realistic Drug Lord.
- Homework 4 -- Max-flow models.
- Homework 5 -- Min-cost flow models.

- GAMS prep -- A shortest path modeling problem. Outside data processing solution. GAMS data processing solution.
- GAMS 0 -- A project prerequisite graph problem. Shortest completion time. Latest start time.

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

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.

**This is a completed course.**