0
$\begingroup$

I am currently using Network Simplex to find the min-cost flow to send $x$ units of goods from source $s$ to sink $t$ given a capacitated graph.

I would now like to solve the problem for all $x \in [1, 2, 3, \ldots, N]$. I could run network simplex $N$ times (once for each $x$) but that is proving to be slow for large $N$ (e.g. $N=200)$.

Does anyone know of some optimized way to do this?

$\endgroup$
1
  • $\begingroup$ These methods are very fast, so 200 * almost nothing is still fast. Some algorithms allow a warm-start (using an advanced basis). In addition you can solve things in parallel. $\endgroup$ Jul 17 '16 at 19:37
0
$\begingroup$

Try Ant methods / critical path analysis on the problem.

Ant Method

Critical Path method

I am not able to advise on efficiency of these algorithms compared to Network Simplex

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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