# When is polytope compatible with network flow?

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?

-
Network flow polytopes do not necessarily have integral vertices -- there is no restriction that $u$ or $v$ are integral. Furthermore, is having integral vertices is a sufficient condition, even if you take into account dimensiona? Would the generic reduction from integral vertices to the network-flow polytope require an exponential increase in the number of variables or constraints? – David Harris Apr 8 '11 at 13:16
ah duh. sorry I confused rational and integral. – Suresh Venkat Apr 10 '11 at 2:51
@David: any updates to this question? I'm curious too about possible results. – Suvrit Jun 28 '11 at 23:19