Let $A \in \{0, 1\}^{m \times n}$ be a matrix with consecutive ones in either the rows or columns. Then apparently solving an linear programming problem of the form
Minimize $c^Tx$ subject to $Ax = b$.
can be solved with a minimimum flow algorithm.
An example given in an exercise:
$A = \begin{pmatrix}
0 & 1 & 0 & 1 & 1 \\
1 & 1 & 0 & 1 & 1 \\
1 & 1 & 1 & 0 & 1 \\
1 & 1 & 1 & 0 & 0 \\
\end{pmatrix}$
$b = (5, 12, 10, 6)^T$.
I am confused as to how to turn this into a minimum flow problem. I know that given a minimum flow problem, we can turn it into a linear programming problem by letting $x$ be the vector of edges and $c$ the cost vector, then we want to minimize $c^T x$. We have some equality restraints for the net flow for each vertex, and some inequalities for the capacity constraints.
However, $Ax = b$ only has equalities, and I would expect some $-1$'s in $A$ to denote the edges going out of a vertex (assuming $x_2 + x_4 + x_5 = 5$ has interpretation: there is a node with flow supply $5$, and edges $x_2, x_4, x_5$ leave it, and no other edges enter it). Also, it doesn't quite add up because $x_2$ would need to leave two different vertices.
I also don't understand the significance of $A$ having consecutive 1's in rows or columns.
Can anyone help me make sense on how to interpret this as a minimum flow problem?
Best Answer
Replace each row $i$ with row $i$ minus row $i+1$, and you will obtain at most $1$ and at most $-1$ in each column. Now introduce a source and sink, which will each have another row in the constraint matrix. These additional two rows will contain either $1$ or $-1$ as needed to make each column sum to $0$.