Network flow models¶
Part 3 · Flows · Chapter 4 · Lecture notes, volume 3 (PDF) · Exercises: Flow models
-
4.1 Networks and flows
-
4.2 The minimum cost flow model
-
4.3 Feasibility conditions
-
4.4 Removing the lower bounds
-
4.5 Unbalanced instances
-
4.6 Total unimodularity and integrality
-
4.7 The dual model and the reduced costs
-
4.8 Special cases
-
4.9 A transshipment instance
The certificate of optimality
Prerequisites
-
From this module, Chapter 1 «Graphs»: directed graphs, the node–arc incidence matrix, spanning trees and the rank of the incidence matrix.
-
From the module Linear Programming, Chapter 9 «Duality theory» and Chapter 15 «The geometry of Linear Programming»: the dual of an LP, weak and strong duality, vertices of a polyhedron.
-
Determinants: the Laplace expansion along a column and Cramer's rule.
Objectives
At the end of this chapter you will be able to:
-
describe a network with balances, lower bounds, capacities and costs, and write the minimum cost flow model, also in matrix form with the incidence matrix;
-
check the necessary conditions for the existence of a feasible flow, and build counterexamples;
-
remove the lower bounds by a substitution, and balance an instance with a dummy node;
-
prove that the incidence matrix is totally unimodular, and deduce that the model has integer optimal solutions when the data are integer;
-
write the dual with the potentials \(\pi_i\), compute the reduced costs and certify the optimality of a flow;
-
recognize the shortest path, the maximum flow, the transportation and the assignment problems as minimum cost flow models.
Next: 4.1 Networks and flows
Exercises on this chapter: Flow models