301. Multi-Commodity Network Flow

301.1. Minimum Cost Network Flow (MCNF)

1. Maximum Flow
2. Shortest Path

IP $\to$ LP Relaxation $\to$ Integer Solution

Network

• Nodes ($𝑛$)

• Edges $\left(𝑢,𝑣\right)$

• 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 $𝐺=\left(𝑉,𝐸\right)$

• For node $𝑖\in 𝑉$ there is a supply quantity ${𝑏}_{𝑖}$

  • ${𝑏}_{𝑖}>0$: $𝑖$ is a supply node
  • ${𝑏}_{𝑖}<0$: $𝑖$ is a demand node
  • ${𝑏}_{𝑖}=0$: $𝑖$ is a transhipment node
  • ${\sum }_{𝑖\in 𝑉}{𝑏}_{𝑖}=0$: Total supplies equal total demands

• For edge $\left(𝑖,𝑗\right)\in 𝐸$, the weight ${𝑐}_{𝑖𝑗}\ge 0$ 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)

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 $min\left\{{𝑐}^{𝑇}𝑥|𝐴𝑥=𝑏,𝑥\ge 0\right\}$, if

• $𝐴$ is totally unimodular and
• $𝑏\in {\mathbb{Z}}^{𝑛}$,

then an optimal bfs ${𝑥}^{\ast }$ obtained by the simplex method must satisfy ${𝑥}^{\ast }\in {\mathbb{Z}}^{𝑛}$

Proof:

Where:

• ${𝐴}_{𝐵}^{\text{adj}}$: adjugate matrix of ${𝐴}_{𝐵}$
• ${\left({𝐴}_{𝐵}^{\text{adj}}\right)}_{𝑖𝑗}$: determinant of the matrix obtained by removing row $𝑗$ and column $𝑖$ from ${𝐴}_{𝐵}$

If A is totally unimodular, $det\left({𝐴}_{𝐵}\right)$ 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

301.2. Transportation Problems

A firm owns $𝑛$ factories that supply one pruduct to $𝑚$ markets

• ${𝑠}_{𝑖}$: Capacity of factory $𝑖$, $𝑖=1,\dots ,𝑛$
• ${𝑑}_{𝑗}$: Demand of market $𝑗$, $𝑗=1,\dots ,𝑚$

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 ${\sum }_{𝑖=1}^{𝑛}{𝑠}_{𝑖}={\sum }_{𝑗=1}^{𝑛}{𝑑}_{𝑗}$

• ${𝑥}_{𝑖𝑗}$: Shipping quantity on arc $\left(𝑖,𝑗\right)$, $𝑖=1,\dots ,𝑛,𝑗=1,\dots ,𝑚$

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 (${𝑢}_{𝑖𝑗}=\infty$)

If capacity is greater than demand:

• Create a “virtual market” (market 0) whose demand quantity is ${𝑑}_0={\sum }_{𝑖=1}^{𝑛}{𝑠}_{𝑖}-{\sum }_{𝑗=1}^{𝑛}{𝑑}_{𝑗}$
• Arcs $\left(𝑖,0\right)$ have cost ${𝑐}_{𝑖0}=0$
• 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 ${𝑐}_{𝑖𝑗}+{𝑐}_{𝑗}^{𝑅}$

301.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 $\left(𝑖,0\right)$ have cost ${𝑐}_{𝑖0}=0$
• Assigning job 0 just means some workers are unused

IP Formulation

• $𝐼$: set of factories / jobs
• $𝐽$: set of markets / workers

• These matrices are totally unimodular

301.4. Transhipment Problems

If there are intermediary nodes in the transportation problem it is a transhipment problem

301.5. Maximum Flow Problems

Where:

• ${𝑥}_{𝑡𝑠}$: flow size of the
• ${𝑢}_{𝑖𝑗}$:

Objective: Maximize number of units sent from $𝑠$ to $𝑡$ given edge capacities

301.6. Shortest Path Problems

Where:

• $𝑠$: supply node
• $𝑡$: demand node
• ${𝑥}_{𝑖𝑗}$: weather edge $\left(𝑖,𝑗\right)$ 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:

• ${𝑏}_{𝑖}=1$: net supply at node $𝑖$

Transportation problems are a special case of Transhipment problems where:

• ${𝑏}_{𝑖}\ne 0$: net supply at node $𝑖$

Transhipment problems are a special case of MCNF problems where:

• ${𝑢}_{𝑖𝑗}=\infty$: No capacity on edge $\left(𝑖,𝑗\right)$

Shortest Path problem is a special case of Transhipment problems where:

• ${𝑏}_{𝑠}=1$: One supply node with supply of 1
• ${𝑏}_{𝑡}=-1$: One demand node with supply of −1 (demand)
• ${𝑏}_{𝑖}=0\forall 𝑖\in 𝑇$: All others are transhipment nodes

Maximum Flow problems are a special case of MCNF problems where:

• ${𝑐}_{𝑖𝑗}=0\forall \left(𝑖,𝑗\right)\in 𝐸$: All original edges have 0 cost
• ${𝑐}_{𝑡𝑠}=-1$: One “virtual edge” with cost −1