01.2 - The min-cost flow problem - from slides - MM

Problem definition

A network like the one below is given:

The same network, can also be described through 6 linear equations:

{\begin{cases} Nodo 1: x_{1} - x_{8} = 10 \\ Nodo 2: - x_{1} + x_{2} + x_{4} + x_{5} + x_{7} = - 12 \\ Nodo 3: - x_{2} + x_{3} = 0 \\ Nodo 4: - x_{3} - x_{4} - x_{5} + x_{9} - x_{10} = - 13 \\ Nodo 5: - x_{5} + x_{6} = 0 \\ Nodo 6: - x_{7} + x_{8} - x_{9} + x_{10} = 15 \end{cases}

or in matrix form:

[\begin{matrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 & - 1 & 0 & 0 \\ - 1 & 1 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 0 \\ 0 & - 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & - 1 & - 1 & - 1 & 0 & 0 & 0 & 1 & - 1 \\ 0 & 0 & 0 & 0 & - 1 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & - 1 & 1 & - 1 & 1 \end{matrix}] [\begin{matrix} x_{1} \\ x_{2} \\ x_{3} \\ x_{4} \\ x_{5} \\ x_{6} \\ x_{7} \\ x_{8} \\ x_{9} \\ x_{10} \end{matrix}] = [\begin{matrix} 10 \\ - 12 \\ 0 \\ - 13 \\ 0 \\ 15 \end{matrix}]

observation

Notice how the 6 equations are not linearly indipendent. One equation can be removed as it originates from the others. We same the system is overdetermined.

The flow vector, $x$ , is unknown.

Given we have more unknown variables than equations, the solution won't be unique.

min-cost problem

The min-cost problem consists in finding the solution, or solutions, that minimize the cost of moving units across a network.

Let:

$D =$ Node-link incidence matrix
$x =$ flow vector (decision variables)
$b =$ injections/extractions vector
$l, u =$ lower and upper bounds vectors
$c =$ Is the vector cost: it assigns a cost value to every link

Our system can be written as:
$D x = b$
We want $x$ , so that we minimize the quantity
$c^{T} x$
keeping in mind, as a restrain, that:
$l \leq x \leq u$

Usually, $l = 0$ . If this is not the case, it is easy to reformulate the problem defining a new flow vector $y$

y = x - l

Typically, $c \geq 0$ . If this is the case, the solution set, $F^{*}$ , is upper bounded.

[?] Why is the solution upper bounded when the cost is greater than 0?

Basic feasible solution

Each problem defined as in #Problem definition, has many possible solutions. We are interested in some specific ones, called basic feasible solutions.

Let there be a graphgraph $G = (N, A)$ . Let $x_{i j}$ with $(i, j) \in A$ be a feasible flow of given graph.

The solution, $x_{i j}$ is a basic feasible solution if it falls under the following conditions:
0. It's feasible

We can build a set, $I_{B}$ , so that $| I_{B} | = | N | - 1$ containing links where the flows in the graph are equal to:
- $x_{i, j} = 0 \lor x_{i, j} = u_{i, j} \lor 0 < x_{i, j} < u_{i, j}$
$I_{B}$ constitutes a spanning tree
We put every other null or upper bound flow in other sets, $I_{N}$ or $I_{N +} \lor I_{N -}$

where:

$I_{N -} =$ Set of links with null flows: $(i, j) \in I_{N -}$ , then $x_{i, j} = 0$
$I_{N +} =$ Set of links with upper bound flows: $(i, j) \in I_{N +}$ , then $x_{i, j} = u_{i, j}$
or, alternativly, if there is NOT an upper bound, we only have $I_{N}$ :
$I_{N} =$ Set of links with null flows: $(i, j) \in I_{N}$ , then $x_{i, j} = 0$

$I_{N}$ , $I_{N +}$ and $I_{N -}$ don't have to contain all the links.

Given this graph:

We can define $I_{B}$ as

I_{B} = (1, 2), (2, 3), (2, 5), (3, 4), (6, 1)

Notice that:

| I_{B} | = 6 - 1 = 5

and that the links in $I_{B}$ form a spanning tree.

There is no upper bound so we only need $I_{N}$ and it will contain all the other links with flow equal to 0.

Once we select a spanning tree, we can make an incidence matrix of just the spanning tree. In this case, we'll get:

[\begin{matrix} 1 & 0 & 0 & 0 & - 1 \\ - 1 & 1 & 0 & 1 & 0 \\ 0 & - 1 & 1 & 0 & 0 \\ 0 & 0 & - 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 \end{matrix}]

Notice that the system above is not linearly independent. So, we can remove the last row and we get:

B = [\begin{matrix} 1 & 0 & 0 & 0 & - 1 \\ - 1 & 1 & 0 & 1 & 0 \\ 0 & - 1 & 1 & 0 & 0 \\ 0 & 0 & - 1 & 0 & 0 \end{matrix}]

❗❗❗❗❗❗❗❗❗❗❗❗
❗❗❗ COMPLETARE ❗❗❗
❗❗❗❗❗❗❗❗❗❗❗❗

From slide 17 to end of pdf.