[Lemon-user] Complexity of Network Simplex

[Alpar Juttner]

Dear Heba,


> 1-  The complexity of LEMON-Network Simplex?

>From theoretical point of view, the Network Simplex algorithm is of
exponential running time worst case.
On the other hand, it is _very_ efficient in practice, it is basically
best choice in most cases.

In this sense, it is pretty much analogous to the standard Simplex
algorithm for solving LP problems.

LEMON implementation itself is really among the best one available, both
amongst the open source and the commercial implementations.

> 2-  How scalable is it? i.e. up to how many nodes and arcs can the
> solver handle?

It depends on the type of the graph, and on the time you have, of
course.

Basically, you can expect an optimal solution within 1sec for a graphs
of a couple of ten thousands nodes and a couple of 100 thousands edges.

Also, typically you will be able to handle millions of edges within an
hour.

A much more detailed evaluation is available here: 

http://lemon.cs.elte.hu/trac/lemon/raw-attachment/wiki/Citations/Kiraly-Kovacs_min_cost_flow_ACTA_INFO_2012.pdf

This paper evaluates the different algorithms available in LEMON, and
also compares them the other solvers, such as CS2, LEDA, MCFZIB and
RelaxIV.


Regards,
Alpár






> 
> 
> Thanks a lot, 
> 
> Heba
> _______________________________________________
> Lemon-user mailing list
> Lemon-user at lemon.cs.elte.hu
> http://lemon.cs.elte.hu/mailman/listinfo/lemon-user