22
$\begingroup$

(This is a follow-up to this question and its answer.)

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

Improve this question
$\endgroup$
1
  • $\begingroup$ 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 and here for posts asking for fast algorithms for these two problems. $\endgroup$
    – Neal Young
    Commented Aug 19, 2017 at 22:58

3 Answers 3

Reset to default
13
$\begingroup$

I believe On a class of totally unimodular matrices, 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, 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.

Improve this answer
$\endgroup$
0
3
$\begingroup$

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).

Improve this answer
$\endgroup$
0
1
$\begingroup$

It has been shown that totally unimodular LP is solvable in strongly polynomial time under a "degeneracy assumption" - link here (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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.