Re: [Help-glpk] glpk 4.49 release information

[Andrew Makhorin]

> This is great news.  I have found many uses of minimum cost
> network-flow over the years, including revenue management models,
> small models for doing "first-come, first serve" and "last-come,
> first-serve" connections within the transportation industry, passenger
> rail crew rostering problems, and a host of other uses, and have used
> either my own version of an augmenting shortest path algorithm based
> on the work by Wang and Kennington, or a commercial license from
> Andrew Goldberg.  I am really glad that there is now a
> high-performance open-source solver that uses the relaxation method
> that others would also use and over time improve.
> 

Below here some benchmarks for a subset of Klingman's standard mincost
flow instances (glp_netgen / glp_netgen_prob):

                                   Primal simplex  OKALG   RELAX-IV
Problem  Nodes   Arcs    Optimum   Iters  Time,s   Time,s  Time,s
-------  -----  -----  ----------  --------------  ------  ------
  101     5000  25536     6191726   17560  104.4    32.5    0.1
  102     5000  25387    72337144   23633  152.3    49.5    0.2
  103     5000  25355   218947553   28101  186.4    68.4    0.3
  104     5000  25344   -19100371   16808  104.3   117.6    0.2
  105     5000  25332    31192578   17239  107.4    28.0    0.2
  106     5000  12870     4314276   11401   44.2    16.6    0.1
  107     5000  37832     7393769   20315  171.0    48.5    0.2
  108     5000  50309     8405738   22806  244.5    76.7    0.3
  109     5000  75299     9190300   27267  411.9   110.7    0.5
  110     5000  12825     8975048   11215   44.2    17.3    0.1