298. Multi-Commodity Network Flow
298.1. Minimum Cost Network Flow (MCNF)
- Maximum Flow
- Shortest Path
IP LP Relaxation Integer Solution
Network
-
Nodes ()
-
Edges
-
Directed
-
Undirected
Path
Path from node to node is the set of arcs:
such that and are connected
- : source
- : destination
Cycle: Path whose source and destination are the same node
Simple path: A path that is not a cycle
Acyclic network: Network containing no cycle
Flow: actions of sending items through an edge
Flow size: Number of units sent through an edge
Weight: Property on an edge (e.g., distance, cost per unit, etc.)
Weighted network: network whose edges are Weighted
Capacity: Edge constraint
Capacitated network: network whose edges have capacities
Consider the weighted capacitated network
-
For node there is a supply quantity
- : is a supply node
- : is a demand node
- : is a transhipment node
- : Total supplies equal total demands
-
For edge , the weight is the cost of each unit of flow
Objective: Satisfy all demand while minimizing cost
LP Formulation
- The number of edges and constraints are equal
- Each variable appears in two constraints (coefficient 1 and coefficient −1)
Example
Decision variables:
: Flow size of edge
for all
Objective function:
Capacity Constraints
Flow Balancing Constraints
- Supply node
- Transhipment nodes
- Demand nodes
Complete Formulation
As long as
- Supply quantities
- Upper bounds
are integers, the solution will be an integer solution
The LP relaxation of the IP formulation always gives an integer solution
Total unimodularity gives integer solutions
For a standard form LP , if
- is totally unimodular and
- ,
then an optimal bfs obtained by the simplex method must satisfy
Proof:
Where:
- : adjugate matrix of
- : determinant of the matrix obtained by removing row and column from
If A is totally unimodular, will be either 1 or −1 for any basis . is then an integer vector if is an integer vector.
- If a standard form LP has a totally unimodular coefficient matrix, an optimal bfs will always be integer
- If a standard form IP has a totally unimodular coefficient matrix, its LP relaxation always gives integer solutions
Sufficient conditions for total unimodularity: For matrix , if:
- all its elements are 1, 0, −1
- each column contains at most two nonzero elements
- rows can be divided into two groups so that for each column two nonzero elements are in the same group if and only if they are different (+ and -)
Then is totally unimodular
Example
- All its elements are 1, 0, −1
- Each column contains at most two nonzero elements
Constraints:
For simplex:
- Rows can be divided into two groups so that for each column two nonzero elements are in the same group if and only if they are different (+ and -)
298.2. Transportation Problems
A firm owns factories that supply one pruduct to markets
- : Capacity of factory ,
- : Demand of market ,
Between factory and market there is a route
- : Unit cost for shipping one unit from factory to market
How to produce and ship the product to fulfill all demands while minimizing the total cost?
if
- : Shipping quantity on arc ,
This is a MCNF problem:
- Factories are supply nodes whose supply quantity is
- Markets are demand nodes whose supply quantity is
- No transhipment nodes
- Arc weights are unit transportation costs
- Arcs have unlimited capacities ()
If capacity is greater than demand:
- Create a “virtual market” (market 0) whose demand quantity is
- Arcs have cost
- Shipping to market 0 just means some factory capacity is unused
If different factories have different unit production costs
- is updated to
If different markets habe different unit retailing costs
- is updated to
298.3. Assignment Problems
- A manager assigns jobs to workers
-
The assignment is one-to-one (one job to one worker)
- Jobs cannot be split
- : cost for worker to complete job
How to minimize total cost?
Special case of Transportation Problem
- Jobs are factories and workers are markets
- Each factory produces one item and each market demands one item
- Cost of shipping one item from factory to maket is
What if there are fewer jobs then workers:
- Create a “virtual job” (job 0)
- Arcs have cost
- Assigning job 0 just means some workers are unused
IP Formulation
- : set of factories / jobs
- : set of markets / workers
- These matrices are totally unimodular
298.4. Transhipment Problems
If there are intermediary nodes in the transportation problem it is a transhipment problem
298.5. Maximum Flow Problems
Where:
- : flow size of the
- :
Objective: Maximize number of units sent from to given edge capacities
298.6. Shortest Path Problems
Where:
- : supply node
- : demand node
- : weather edge is chosen (binary)
- : weight (distance) between nodes and
Objective: Get from to while minimizing distance
Out of all outgoing edges from , one must be selected:
Out of all ingoing edges to , one must be selected:
For all transhipment nodes ,
Summary
Assignment problems are a special case of Transportation problems where:
- : net supply at node
Transportation problems are a special case of Transhipment problems where:
- : net supply at node
Transhipment problems are a special case of MCNF problems where:
- : No capacity on edge
Shortest Path problem is a special case of Transhipment problems where:
- : One supply node with supply of 1
- : One demand node with supply of −1 (demand)
- : All others are transhipment nodes
Maximum Flow problems are a special case of MCNF problems where:
- : All original edges have 0 cost
- : One “virtual edge” with cost −1