2
$\begingroup$

I have a large-ish instance of a transportation problem that is very asymmetric, say of dimensions $100\times10000$. I am currently solving it with a stock LP solver, but obviously something like the network simplex method would be preferable. In addition to network simplex, are there any other well-known algorithms that are particularly well-suited to a problem of this type?

Improve this question
$\endgroup$
1
  • $\begingroup$ One thing easy to try, if you didn't already, is to apply the LP solver to the dual LP. It might run very much faster. Or it might not; it is hard to predict. $\endgroup$
    – Brendan McKay
    Commented May 25, 2017 at 2:48

1 Answer 1

Reset to default
1
$\begingroup$

Although there are a million variables $x_{ij}$ where $i=1\ldots100$ and $j=1\ldots10000$, depending on the problem parameters it is likely that only a small number of them will be basic in an optimal solution. In this situation the method of "delayed column generation" may be useful. Start with a relatively small number of $x_{ij}$, enough to make the problem feasible, and solve the LP for those. Then using the shadow prices, search for some $x_{ij}$ that would most profitably enter the basis (i.e. where the cost of transporting a unit from $i$ to $j$ is less than the difference between the shadow prices at $i$ and $j$). Include those $x_{ij}$ and solve again. (Software such as Cplex may let you solve the modified problem starting with the optimal solution for the last problem, which is convenient). If the number of variables gets too large to be convenient, you might remove those that haven't been in the basis for the last 1000 iterations or so. Stop when no new $x_{ij}$ will enter the basis.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .