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.

The Sakai forum for the class is an excellent place for students to discuss homework assignments and ask questions.

We had a number of outstanding projects this quarter, both technically, and in terms of analysis. Below are all the class projects, in alphabetical order by topic.

- Afghanistan Drug Traffic by Bethany, Kauffman, Stephen Felts, Daniel Ryan (presentation)
- Computer Network Design by Fatih Yildiz (presentation)
- Golf by Stephen Lantz, William Bickel (presentation)
- Illegal Product Distribution in California by Dan Mintzer, Jason Ross, Isaac May (presentation)
- Maritime Drug Interdiction by Sly Campos, Monica Schneider, Mike Dickenson (presentation)
- Network Diversion by David Risius, Christopher Wood (presentation)
- New York Subways by Lewis Anderson, Dustin Crawford, Sean McCrink (presentation)
- North Korean Escape by Krysta Anthony, Kevin Kerno (presentation)
- Nuclear Fuel Distribution by Christian Seymour, Jesse Nessbitt, Adam Gable (presentation)
- SF Drug Network by Yuchia Wang, Adam Haupt (presentation)
- San Diego Visit by Joe Snel, Lee Eubanks (presentation)
- Social Network by Tobias Kuhn, Paul Ortiz (presentation)
- US Coast Guard Assignments by Jose M. Rosario (presentation)
- United Airlines Network by Andy Olson, Mike Brisker (presentation)
- Visiting SF Events by Nick Ulmer, Bryan Rex (presentation)
- Volcano Evacuation by Cardy Moten, Volkan Sozen (presentation)

View or download the entire class worth of lectures from the Networks lecture videos page.

Look for assignment due dates on the calendar on the right.

- GAMS Prep -- Solve a real-world problem using a shortest path. solution files, in_class_files morning afternoon
- GAMS 0 -- Shortest path modeling. solution files morning afternoon
- GAMS 1 -- Critical path method. latest_start_time shortest_completion_time

- HW0 HW0Solutions -- Describing graphs mathematically, storing graphs in a computer. sparse_matrix_python
- HW1 HW1Solutions -- Graph Search
- HW2 HW2Solutions -- Shortest Path
- HW3.1 HW3.1Solutions -- The Drug Lord 3-1-files 3-2-files
- HW3.2 HW3.2Solutions -- A More Realistic Drug Lord
- HW4 HW4Solutions -- Max Flow
- HW5 HW5Solutions -- Min Cost Flow

- Project 0 -- Create your team, and pick your network.
- Project 1 -- Create a back story, start CSV files.
- Project 2 -- Start creating a basic LP model.
- Starting points: shortest_path max_flow min_cost_flow multi_commodity_flow

- Project 3 -- Project deliverables and timeline.
- Interdiction starting points: shortest_path max_flow min_cost_flow multi_commodity_flow

- Project 4 -- Checklist and guidance.
- Project 5 -- Turn in instructions.
- Writing Style Guide -- Some brief guidelines on technical writing.
- Talk Style Guide -- Some briief guidelines on preparing good presentations.

- 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 3.1 -- Overview of network models.
- 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.