A linear program is the problem of optimizing an linear objective function within some polytope $A$ over $\mathbf R^n$. My question is motivated by the question of when a linear programming problem can be transformed into a min-cost flow problem, which is less computationally expensive.
In some cases, there is a linear transformation $T$ such that $A = T B$, where $B$ is a polytope in a possibly larger dimensional space, and such that $B$ can be represented as a network flow.
A network-flow polytope on $y$ is defined by the constraints that $y_i \in [0, u_i]$ and in addition $L y = v$, where $u$ and $v$ are fixed vectors and $L$ is a matrix in which each column has exactly one $-1$, one $+1$, and the other entries are all zero.
The new variables $y$ correspond to edges in a directed graph. The $u_i$ is the edge capacity. The rows of $L$ correspond to vertex demands. The columns of $L$ correspond to the source and destination vertex of each edge.
Questions:
Under what conditions can we write $A = T B$ for $B$ a network-flow polytope?
Can this be done effectively?
Does this require increasing the number of constraints and/or variables by a large amount?
