Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.


  • 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?

share|improve this question
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.