Advanced Algorithms UE 7

by Maarten Behn
Group 5

Exercise 7.1 (Modeling as Min-Cost Flow) (10 Points)

Consider the following problem.
A car manufacturer has $r$ factories $F_1,...,F_r$ to produce $s$ different car models $M_1,...,M_s$.
For $i\in [r]$ and $j\in [s]$, it is known whether factory $F_i$ can produce model $Mj$ and, if so, at what unit cost ${\alpha }_{i,j}$.

Furthermore, factory $F_i$ for $i\in [r]$ can produce at most ${\beta }_i$ cars per month, of which at most ${\gamma }_{i,j}$ can be of model $M_j$ , $j\in [s]$.

The cars are sold by $t$ car dealers $H_1,...,H_t$.
For $i\in [r]$ and $k\in [t]$, it costs ${\delta }_{i,k}$ to transport a vehicle from $F_i$ to $H_k$.

Additionally, dealer $H_k$, for $k\in [t]$, sells ${\theta }_{j,k}$ cars of model $M_j\in [s]$ per month.
The goal is to plan the production and transportation of cars such that the total cost is minimized.

Model the above optimization problem as a minimum-cost flow problem.
Specify the set of nodes and edges, as well as the edge capacities, costs, and balances.
Argue why your modeling solves the given production problem.

Idea

Transclude of AA-UE-7.1.excalidraw

Formal definition

$\mathcal{N}=(V,E,c,b,p)$

$V=\{a_i|i\in [r]\}$
$\cup \{b_{i,j}|i\in [r]j\in [s]\}$
$\cup \{c_{j,k}|j\in [s]k\in [t]\}$

$E=\{(a_i,b_{i,j})|i\in [r]j\in [s]\}$
$\cup \{(b_{i,j},c_{j,k})|i\in [r]j\in [s]k\in [t]\}$

$b(a_i)={\beta }_i$
$b(b_{i,j})=0$
$b(c_{j,k})=-{\theta }_{j,k}$

$c((a_i,b_{i,j}))={\gamma }_{i,j}$
$c(b_{i,j},c_{j,k}))=\infty$

$p((a_i,b_{i,j}))=0$
$p(b_{i,j},c_{j,k}))={\delta }_{i,k}$

Argument why a min const flow problem on $\mathcal{N}$ models the optimization problem

Each Factory has in $a_i$ an input flow corresponding to ${\beta }_i$.
This models the amount of cars each factory can produce.

This flow gets split up into $b_{i,1}...b_{i,s}$.
The edges have a max capacity of ${\gamma }_{i,j}$
If the factory does not produce the model the capacity would be $0$.
Therefore incoming flow into $b_{i,j}$ represents how many cars of model $j$ factory $i$ can produce.

The flow from $b_{i,j}$ gets split up into $c_{j,1}...c_{j,t}$
The incoming flow into $c_{j,k}$ represents how many cars of model $j$ dealer $k$ sells.
Therefore the $b(c_{j,k})$ is $-{\theta }_{j,k}$

The edges $p((b_{i,j},c_{j,k}))$ have a cost of ${\delta }_{i,k}$ to represent the cost of transporting a car of model $j$ from factory $i$ to dealer $k$.
Therefore the edges $(b_{i,j},c_{j,k})$ represent the distribution problem of cars to dealers.

Exercise 7.2 (Decomposition into Cycles) (10 Points)

Prove the following lemma from the lecture:
Let $f$ be a circulation in a network $N=(V,E,c,b,p)$. Then, there exist flows $f_1,...,f_k$ with $k\le m$ such that
(i) $f=f_1+...+f_k$,
(ii) $f_i$ is a feasible circulation in $\mathcal{N}$ for all $i\in [k]$, and
(iii) $f_i$ takes positive values only on edges of a cycle $C_i$ in $N$ for all $i\in [k]$.

Idea

repeatedly finding a cycle in $f$ and extracting flow along these cycle until
the $f$ is empty.

Helper definition

$E_f:=\{e\in E\mid f(e)>0\}$
$G_f:=(V,E_f)$

Observation

When $f$ is a non empty circulation there must be at least one cycle in $G_f$.

Proof

Start at $(u,v_1)\in E_f$
since $\sum _{e\in {\delta }^{-}(v_1)}=\sum _{e\in {\delta }^{+}(v_1)}\exists (v_1,v_2)\in E_f$
following all possible edges recursively must lead back to $v_1$
forming a cycle
because $G_f$ is finite and all flow in a circulation is conserved.

Algorithm

While $f$ is not empty
Create $G_f$ for $f$
Let $C$ be a cycle found in $G_f$
$\forall e\in C{f}_i(e):=min(f(e))$
$\forall e\notin C{f}_i(e):=0$
$f\leftarrow f-f_i$

Proof $f_i$​ is a feasible circulation

• satisfies conserves flow → same amount goes in a circle.
• satisfies capacity constraints → all flow is positive and less or equal to the original $f$

Proof $k\le m$

Each iteration removes at least one edge form $E_f$ (the one with the minimum flow on the cycle)
so $k\le |E|=m$