Minimum-cost flow problem

Minimum-cost flow problem

In the minimum-cost flow problem, we want to find a flow that satisfies all supply and demand and has the minimum possible cost. Formally, a flow in the network $G$ is a function $f:E\to R$ assigning flows to edges, $f(v,w)$ (non-negative amount of flow on edge $v$ to $w$), which satisfies the capacity constraints and flow conservation constraints.

The input is a flow network $G=(V,E,u,c,d)$ where:

• $V$ is a set of nodes
• $E$ is a set of directed edges
• For each edge $(v,w)\in E$, $u(v,w)\ge 0$ is the capacity of edge $(v,w)$ We label each edge (x, y)
• For each node $v\in V$, (as in flow-feasibility problem) $|d(v)|$ is the (initial) supply (if $d(v)>0$) or demand (if $d(v)<0$) at $v$. 1st number on each edge, x ${\sum }_{v\in V}d(v)=0$
• For each edge $(v,w)\in E$, $c(v,w)\ge 0$ is the cost of one unit of flow on edge $(v,w)$. 2nd number on each edge, y

Link to original

The cost of a flow is ${\sum }_{(v,w)\in E}c(v,w)f(v,w)$

The capacity constraints state that for each edge $(v,w)\in E,f(u,v)\le u(v,w)$

Example of flow in this network

Technical assumption

If $(v,w)\in E$, then $(w,v)\notin E$

We can add an intermediate node as follows:

Flow conservation constraints (basics)

Net flow outgoing from node $v$: ${\sum }_{(v,x)\in E}f(v,x)-{\sum }_{(z,v)\in E}f(z,v)$

• net flow from each transitional node ($d(v)=0$) is $0$
• net flow from each “supply” node $v$ is at most $d(v)$
• net flow incoming to each “demand” node $v$ is at most $|d(v)|=-d(v)$ (the demand at $v$)

Formally, the net flow outgoing from $v$:

= &0 &&\text{if } d(v) = 0 \\ \le &d(v) &&\text{if } d(v) > 0 \\ \ge &d(v) &&\text{if } d(v) < 0 \end{cases}$$ A flow satisfies all supplies and demands if the net flow outgoing from each vertex $v$ is equal to $d(v)$. > [!example] > 

Application of minimum-cost flow problem

A car manufacturer produces several car models in several plants and ships them to several retail centres. Each retail centre requests a specific number of cars of each model.

Determine the production plan for each plant and the shipping schedule so that the total cost of production and transportation is minimised.

We model as a minimum-cost flow problem:

• nodes: plant (supply), plant/model, retailer/model, retailer (demand)
• edges
  • production edge (pi, pi/mj): capacity - maximum possible production of cars mj at plant pi cost - production cost of one car mj at plant pi
  • transportation edge (pi/mj, rk/mj): transportation of cars mj from plant pi to retailer rkl capacity and transportation cost per one car
  • demand edge (rk/mj, rk): capacity - demand for cars mj at retailer rk

A (integral) flow corresponds to a feasible production/transportation schedule. A minimum cost (integral) flow gives an optimal (minimum cost) production/transportation schedule.

Slides: 9-13 theory behind algorithm / full example of use

Slides: 14 successive shortest path algorithm

Slides: 15 correctness and running time

Multi-commodity flow problem

In a multi-commodity flow problem, we want to design simultaneous flow of all commodities which satisfies the demands of all commodities, and optimises some specified global objective.

The input is:

• a (directed) network $G=(V,E,u)$ where $u(x,y)$ is the capacity of an edge $(x,y)\in E$.
• $k$ commodities Commodity $q$ ($1\le q\le k$) is specified by $(s_q,t_q,d_q)$ where:
  • $s_q\in V$ and $t_q\in V$ are the origin (source) and the destination (target) of commodity $q$
  • $d_q(>0)$ is the (amount of) demand of this commodity

Slides 17-18 example spec

Feasibility multi-commodity-flow problem

Slide 20

Minimum-cost multi-commodity-flow problem

The congestion of a flow on an edge $(x,y)$ is defined as $\frac{f(x,y),\text{the total flow on edge }(x,y)}{u(x,y)}$

In minimum-congestion multi-commodity-flow problems, we want to design a simultaneous flow of all commodities which minimises maximum congestion: $\text{minimise}\max \{\frac{f(x,y)}{u(x,y)}:(x,y)\in E\}$

Slides 19-23