Network Flows

Course Syllabus

See "course Outline" below

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
972-883-2032
chandra@utdallas.edu
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.

    Grading Scheme

    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
      • Zadeh's Examples
      • 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
      • Claw-free Graphs
    10. Blocking Systems and Polyhedra
      • Bottleneck Problems
      • Blocking Systems
      • Blocking and Antiblocking Polyhdera
      • Perfect Graph Theorem
    12. 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
    13. 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
    14. Total Dual Integrality
      • General Theory
      • Integer Rounding
      • General Algorithm for Solving TDI Optimization Problems
      • Testing
      • Special Cases
      • Hilbert Basis
    15. Geometry of Numbers
      • Introduction
      • Lattice Basis Reduction Techniques
      • Lenstra's Algorithm
      • Scarf's Work
      • Tardos - Frank Simultaneous Approximation
      • Other Applications

    Assignments

    Click here to go back ...