# Network Flows

## Course Syllabus

### Course Objective

This is an advanced course on network models and algorithms in Operations research. The emphasis is on algorithm development and efficiency of algorithms. The follow-up course for this one is the course OPRE 7314: Combinatorial Optimization.

### Office Hours

Jonsson 4.926
214-883-2032
TA: To be announced in Class

### Text

• Network Programming, by Katta G. Murty, Prentice Hall, 1992.
• Network Flows, by R.K. Ahuja, T.L. Magnanti, J.B. Orlin, Prentice Hall, 1993.

### Prerequisites

OPRE 6310; or consent of the instructor.

Homework and two take-home exams

### Course Outline

1. Graph Theory
• Definitions and Concepts
2. Matrices Associated with Graphs
• Node-Arc Incidence Matrix
• Arc Chain Incidence Matrix
• The Loop or Mesh Matrix
• The Node-Edge Incidence Matrix
• The Cut-set Matrix
• Orthogonolity
3. Single Commodity Maximum Flow Problem
• Formulation as an LP
• Max-Flow-Min-Cut Theorem
• Labeling Algorithm
• Finite Termination of Maximum Flow Algorithm
• Ford-Fulkerson Example
• Queyranne Example
• Strongly Polynomial Algorithms
• Edmonds-Karp
• Dinic
• Karzanov
• Maheshwari et al.
• Special Cases
• Undirected Networks
• Parallel Arcs
• Multiple Origins/Destinations
• Node Capacities
• Arc Chain Formulation and Chain Decomposition of Flows
• Lower Bounds and Exogeneous Flows
• Picard-Queyranne work and Structure of Cuts
• MIT Work
4. Single Commodity Multi-terminal Flows
5. Spanning Tree Problem
6. Shortest Path Problem
• Structure
• Specified Pair of Nodes
• One Origin Several Destinations
• All Pairs
• Acyclic Graphs
• Undirected Graphs
• Data
• Nonnegative Distances
• Time Dependent Distances
• Non-negative Cycles
• Methods Used
• Linear Programming Formulation
• Dynamic Programming
• Inductive Algorithm
• Analog Devices
• Matching Formulations
• Objective Functions
• Negative Cycle Detection
• Ratio Functions
• Ratio Functions on Cycles
• kth Shortest Paths
• Shortest Paths Through Specified Nodes
• Odd and Even Shortest paths
• Applications
• PERT
• Reliability
• Ship Routing
• Investments in Blocking Systems
7. Minimum Cost Flows
• Transportation and Primal Dual Algorithm
• Out-of-kilter Algorithm
• Klein's Algorithm
• Edmonds-Karp Scaling
• Strongly Polynomial Algorithms
• E. Tardos
• Fujishige
• Simplex
• Goldberg-Tarjan
• PERT-CPM
8. Unimodularity and Integrality
9. Matching
• Bipartite
• General
• Applications
• Chinese Postman Problem
• Scheduling
• Odd and Even Shortest Paths
• Shortest Paths in Undirected Networks with no Negative Cycles
• Geometric Applications
• Applications to Chemistry
• Ellipsoid Algorithm and the Odd-Cut Problem
• T-joins and T-cuts
10. Blocking Systems and Polyhedra
• Bottleneck Problems
• Blocking Systems
• Blocking and Antiblocking Polyhdera
• Perfect Graph Theorem
11. Multicommodity Flows
• General Problem
• Two Commodity
• T.C. Hu's work
• M. Sakarovitch
• Rothschild and Whinston
• H-Graphs
• Single Star
• Two Stars
• Complete Graph and its Equivalents
• Cut Based Problems
• (2,3)-Metric Based Problems
12. Matroids
• Introduction
• Equivalent Axioms
• Independence
• Circuits
• Bases
• Rank Function
• Hyperplanes, flats etc.
• Greedy Algorithm
• Optimization Problems and Algorithms
• Covering
• Partition
• Intersection
• Parity
• Polyhedral Charecterizations
• Operations
• Union
• Deletion
• Contraction
• Truncation
• Minors
• Duals
• Splitters
• Decomposition and Composition
• Applications
• Testing Graphicness
• Testing Regularity (Total Unimodularity)
• Max-Flow-Min-Cut Matroids
• Pseudomatroids
13. Total Dual Integrality
• General Theory
• Integer Rounding
• General Algorithm for Solving TDI Optimization Problems
• Testing
• Special Cases
• Hilbert Basis
14. Geometry of Numbers
• Introduction
• Lattice Basis Reduction Techniques
• Lenstra's Algorithm
• Scarf's Work
• Tardos - Frank Simultaneous Approximation
• Other Applications