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.

My question is are ---

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?

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?

A linear program is the problem of optimizing an linear objective function within some polytope $A$ over the field $\mathbf R$. There are polynomial-time algorithms for solving this problem.

In some cases, there is a linear change of variables that transforms the polytope $A$ into a polytope $B$ which can be solved by min-cost flow, and such that the original polytope $A$ is a linear projection of $B$.

The min-cost flow polytope can be defined by three classes of constraints:

1. $y_i \geq 0$
2. $y_i \leq u_i$
3. The additional linear constraints are of the form $B' y = v$, where $v$ is a fixed vector and every column of $B'$ contains 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 $B'$ correspond to vertex demands. The columns of $B'$ correspond to the source and destination vertex of each edge. The objective function can be always be realized by an appropriate edge cost.

My question is are ---

under what conditions can a polytope $A$ be transformed by a linear change of variables into a min-cost flow polytope?

Can this be done effectively?

Does this require increasing the number of constraints and/or variables by a large amount (in which case leaving it as general LP might be faster)?

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.

My question is are ---

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?