<p>You might be able to derive better bounds from the general LP algorithm in the paper "Linear Programming in $O([n^3/\ln n]L)$ Operations" (<a href="http://dx.doi.org/10.1137/S1052623497323194" rel="nofollow">here</a>).</p>

CC BY-SA 2.5
2011-01-24T12:50:53.587Z
2011-01-24T12:50:53.587Z
Falk Hüffner
<p>It has been shown that totally unimodular LP is solvable in strongly polynomial time under a "degeneracy assumption" - <a href="http://www.tandfonline.com/doi/full/10.1080/10556788.2016.1208748" rel="nofollow noreferrer"> link here </a>(thus if the ILP has a Totally Unimodular (TU) formulation with the same assumptions then this algorithm would solve 
a TU ILP, in strong polynomial time. This is a development from Tardos's methods, and implies tighter bounds to an TU (Totally Unimodular) ILP formulation. </p>

CC BY-SA 3.0
2017-03-08T06:55:17.970Z
2017-03-08T06:55:17.970Z
user3483902
<p>I believe <a href="http://www.jstor.org/stable/pdfplus/3689380.pdf?acceptTC=true">On a class of totally unimodular matrices</a>, by Yannakakis, gives an answer to your question for a special case of TU ILP (whenever there are no odd cycles in a bipartite graph obtained by seeing the coefficient matrix as an adjacency matrix). </p>

<p>In that paper there is a reference to <a href="http://www.springerlink.com/content/j0m40587pj827586/fulltext.pdf">Polynomial algorithms for a class of linear programs</a>, which seems to handle all totally unimodular matrices, but I am not sure about how much more efficient it is compared to generic algorithms for LPs.</p>

CC BY-SA 2.5
2011-01-21T23:05:49.923Z
2011-01-21T23:05:49.923Z
Abel Molina
<p>(This is a follow-up to <a href="https://cstheory.stackexchange.com/q/4409/148">this question </a> and its <a href="https://cstheory.stackexchange.com/questions/4409/which-integer-linear-programs-are-easy/4411#4411">answer</a>.)</p>
<p>I have the following totally unimodular (TU) integer linear program (ILP). Here  <span class="math-container">$\ell,m,n_{1},n_{2},\ldots,n_{\ell},c_{1},c_{2},\ldots,c_{m},w$</span> are all positive integers given as part of the input. A specified subset of the variables <span class="math-container">$x_{ij}$</span> is set to zero, and the rest can take positive integral values:</p>
<blockquote>
<p>Minimize</p>
<p><span class="math-container">$\sum_{j=1}^{m}c_{j}\sum_{i=1}^{\ell}x_{ij}$</span></p>
<p>Subject to:</p>
<p><span class="math-container">$\sum_{j=1}^{m}x_{ij}=n_{i}\,\,\forall i$</span></p>
<p><span class="math-container">$\sum_{i=1}^{\ell}x_{ij}\ge w\,\,\forall j$</span></p>
</blockquote>
<p>The coefficient matrix of the standard form is a <span class="math-container">$(2\ell+m)\times \ell m$</span> matrix with entries from <span class="math-container">${-1,0,1}$</span>.</p>
<p>My question is:</p>
<blockquote>
<p>What are the best upper bounds known for the running time of polynomial-time algorithms that solve such an ILP? Could you point me to some references on this?</p>
</blockquote>
<p>I did some searching, but at most places they stop with saying that a TU ILP can be solved in polynomial time using polynomial-time algorithms for LP. One thing that looked promising is a 1986 paper by Tardos [1] where she proves that such problems can be solved in time polynomial in the size of the coefficient matrix. As far as I could figure out from the paper, however, the running time of that algorithm depends in turn on the running time of a polynomial-time algorithm for solving LP.</p>
<blockquote>
<p>Do we know of algorithms that solve this special case (of TU ILP) significantly faster than the general algorithms that solve the LP problem?</p>
</blockquote>
<p>If not,</p>
<blockquote>
<p>Which algorithm for LP would solve such an ILP the fastest (in an asymptotic sense)?</p>
</blockquote>
<p>[1] A strongly polynomial algorithm to solve combinatorial linear programs, Eva Tardos, Operations Research 34(2), 1986</p>

CC BY-SA 3.0
2017-08-19T22:58:34.157Z
As pointed out by the answer you cite to your previous post, your problem is a special case of the transportation problem, which is in turn a special case of minimum-cost flow.  See [here](https://cstheory.stackexchange.com/questions/5918/what-is-the-currently-best-known-algorithm-for-the-transportation-problem) and [here](https://cstheory.stackexchange.com/questions/30525/fastest-polynomial-time-algorithm-for-solving-minimum-cost-maximum-flow-problems) for posts asking for fast algorithms for these two problems.
Neal Young
<ds.algorithms><reference-request><linear-programming><integer-programming><polynomial-time>
How fast can we solve a totally unimodular integer linear program?
gphilip
# How fast can we solve a totally unimodular integer linear program?

(Asked by: username_0 on 2011-01-21)

(This is a follow-up to [this question](https://cstheory.stackexchange.com/q/4409/148)  and its [answer](https://cstheory.stackexchange.com/questions/4409/which-integer-linear-programs-are-easy/4411#4411).)

I have the following totally unimodular (TU) integer linear program (ILP). Here $\ell,m,n\_{1},n\_{2},\ldots,n\_{\ell},c\_{1},c\_{2},\ldots,c\_{m},w$ are all positive integers given as part of the input. A specified subset of the variables $x\_{ij}$ is set to zero, and the rest can take positive integral values:

> Minimize
>
> $\sum\_{j=1}^{m}c\_{j}\sum\_{i=1}^{\ell}x\_{ij}$
>
> Subject to:
>
> $\sum\_{j=1}^{m}x\_{ij}=n\_{i}\,\,\forall i$
>
> $\sum\_{i=1}^{\ell}x\_{ij}\ge w\,\,\forall j$

The coefficient matrix of the standard form is a $(2\ell+m)\times \ell m$ matrix with entries from ${-1,0,1}$.

My question is:

> What are the best upper bounds known for the running time of polynomial-time algorithms that solve such an ILP? Could you point me to some references on this?

I did some searching, but at most places they stop with saying that a TU ILP can be solved in polynomial time using polynomial-time algorithms for LP. One thing that looked promising is a 1986 paper by Tardos [1] where she proves that such problems can be solved in time polynomial in the size of the coefficient matrix. As far as I could figure out from the paper, however, the running time of that algorithm depends in turn on the running time of a polynomial-time algorithm for solving LP.

> Do we know of algorithms that solve this special case (of TU ILP) significantly faster than the general algorithms that solve the LP problem?

If not,

> Which algorithm for LP would solve such an ILP the fastest (in an asymptotic sense)?

[1] A strongly polynomial algorithm to solve combinatorial linear programs, Eva Tardos, Operations Research 34(2), 1986

**Tags:** ds.algorithms, reference-request, linear-programming, integer-programming, polynomial-time
> **Comments:**
> **username_1**: As pointed out by the answer you cite to your previous post, your problem is a special case of the transportation problem, which is in turn a special case of minimum-cost flow.  See [here](https://cstheory.stackexchange.com/questions/5918/what-is-the-currently-best-known-algorithm-for-the-transportation-problem) and [here](https://cstheory.stackexchange.com/questions/30525/fastest-polynomial-time-algorithm-for-solving-minimum-cost-maximum-flow-problems) for posts asking for fast algorithms for these two problems.  

---

## 3 answers

### Answer by username_4 on 2011-01-21. Score: 13 | Accepted answer

I believe [On a class of totally unimodular matrices](http://www.jstor.org/stable/pdfplus/3689380.pdf?acceptTC=true), by Yannakakis, gives an answer to your question for a special case of TU ILP (whenever there are no odd cycles in a bipartite graph obtained by seeing the coefficient matrix as an adjacency matrix).

In that paper there is a reference to [Polynomial algorithms for a class of linear programs](http://www.springerlink.com/content/j0m40587pj827586/fulltext.pdf), which seems to handle all totally unimodular matrices, but I am not sure about how much more efficient it is compared to generic algorithms for LPs.


---

### Answer by username_2 on 2011-01-24. Score: 3

You might be able to derive better bounds from the general LP algorithm in the paper "Linear Programming in $O([n^3/\ln n]L)$ Operations" ([here](http://dx.doi.org/10.1137/S1052623497323194)).


---

### Answer by username_3 on 2017-03-08. Score: 1

It has been shown that totally unimodular LP is solvable in strongly polynomial time under a "degeneracy assumption" -  [link here](http://www.tandfonline.com/doi/full/10.1080/10556788.2016.1208748) (thus if the ILP has a Totally Unimodular (TU) formulation with the same assumptions then this algorithm would solve
a TU ILP, in strong polynomial time. This is a development from Tardos's methods, and implies tighter bounds to an TU (Totally Unimodular) ILP formulation.


---

