Topic

No. of hours

Lecture

Tutorial/Practical

Introduction.

Graphs and Flows.

Paths and Cycles.

Flow and Divergence.

Path Flows and Conformal Decomposition.

Network Flow Models – Examples.

The Minimum Cost Flow Problem.

Network Flow Problems with Convex Cost.

Multicommodity Flow Problems.

Discrete Network Optimization Problems.

3

3

-

Network Flow Algorithms – An Overview :-

Primal Cost Improvement.

Dual Cost Improvement.

Auction.

Good, Bad, and Polynomial Algorithms.

Shortest Path Problems :-

Problem Formulation and Applications.

A Generic Shortest Path Algorithm.

Label Setting (Dijkstra) Methods.

Performance of Label Setting Methods.

The Binary Heap Method.

Dial's Algorithm.

3

3

-

Label Correcting Methods :-

The Bellman-Ford Method.

The D'Esopo-Pape Algorithm.

The SLF and LLL Algorithms.

The Threshold Algorithm.

Comparison of Label Setting and Label Correcting.

Single Origin/Single Destination Methods.

Label Setting.

Label Correcting.

Auction Algorithms.

Multiple Origin/Multiple Destination Methods.

3

3

-

The Max-Flow Problem :-

The Max-Flow and Min-Cut Problems.

Cuts in a Graph.

The Max-Flow/Min-Cut Theorem.

The Maximal and Minimal Saturated Cuts.

Decomposition of Infeasible Network Problems.

The Ford-Fulkerson Algorithm.

Price-Based Augmenting Path Algorithms.

A Price-Based Path Construction Algorithm  A Price-Based Max-Flow Algorithm.

3

3

-

The Min-Cost Flow Problem :-

Transformations and Equivalences.

Setting the Lower Flow Bounds to Zero.

Eliminating the Upper Flow Bounds.

Reduction to a Circulation Format.

Reduction to an Assignment Problem.

Duality.

Interpretation of CS and the Dual Problem.

Duality and CS for Nonnegativity Constraints.

3

3

-

Simplex Methods for Min-Cost Flow :-

Main Ideas in Simplex Methods.

Using Prices to Obtain the In-Arc.

Obtaining the Out-Arc.

Dealing with Degeneracy.

The Basic Simplex Algorithm.

Termination Properties of the Simplex Method.

Initialization of the Simplex Method.

Extension to Problems with Upper and Lower Bounds.

Implementation Issues.

3

3

-

Dual Ascent Methods for Min-Cost Flow :-

Dual Ascent.

The Primal-Dual (Sequential Shortest Path) Method.

The Relaxation Method.

Solving Variants of an Already Solved Problem.

Implementation Issues.

Auction Algorithms for Min-Cost Flow :-

The Auction Algorithm for the Assignment Problem.

The Main Auction Algorithm.

Approximate Coordinate Descent Interpretation.

Variants of the Auction Algorithm.

Computational Complexity – Scaling.

Dealing with Infeasibility.

3

3

-

Extensions of the Auction Algorithm :-

Reverse Auction.

Auction Algorithms for Asymmetric Assignment.

Auction Algorithms with Similar Persons.

The Preflow-Push Algorithm for Max-Flow.

Analysis and Complexity.

3

3

-

Implementation Issues.

Relation to the Auction Algorithm.

The -Relaxation Method.

Computational Complexity – Scaling .

Implementation Issues.

The Auction/Sequential Shortest Path Algorithm.

3

3

-

Nonlinear Network Optimization :-

Convex and Separable Problems.

Problems with Side Constraints.

Multicommodity Flow Problems.

Integer Constraints.

Networks with Gains.

Optimality Conditions.

Duality.

Algorithms and Approximations.

Feasible Direction Methods.

Piecewise Linear Approximation.

Interior Point Methods.

Penalty and Augmented Lagrangian Methods.

Proximal Minimization.

Smoothing.

Transformations.

3

3

-

Convex Separable Network Problems :-

Convex Functions of a Single Variable.

Optimality Conditions.

Duality.

Dual Function Differentiability.

Algorithms for Differentiable Dual Problems.

Auction Algorithms.

The _-Relaxation Method.

Auction/Sequential Shortest Path Algorithm.

Monotropic Programming.

3

3

-

Network Problems with Integer Constraints :-

Formulation of Integer-Constrained Problems.

Branch-and-Bound.

Lagrangian Relaxation.

Subgradients of the Dual Function.

Subgradient Methods.

Cutting Plane Methods.

Decomposition and Multicommodity Flows.

Local Search Methods.

Genetic Algorithms.

Tabu Search.

Simulated Annealing.

Rollout Algorithms.

3

3

-