Re: [Help-glpk] How to tell if lpx_simplex() needs to be restarted?

[Andrew Makhorin]

Hi Woei Ling

> Please find attached the
> problem data set. Please let me know if you think having another
> set of data will help you in diagnosing the problem.

Thank you. Your instances are classic example which beats the glpk
simplex at all :+) I solved your small problem without any troubles,
however the convergence was extremely slow due to high degeneracy:
all constraints are equalities most of which have zero rhs (looking
through the constraint matrix I guess it is a pure network problem).

lpx_read_mps: reading problem data from `small.mps'...
lpx_read_mps: problem network_
lpx_read_mps: 9249 rows, 18084 columns, 206628 non-zeros
lpx_read_mps: 128822 cards were read
lpx_simplex: original LP has 9249 rows, 18084 columns, 206628 non-zeros
lpx_simplex: presolved LP has 9248 rows, 9316 columns, 197312 non-zeros
lpx_adv_basis: size of triangular part = 9088
      0:   objval =   0.000000000e+00   infeas =   1.000000000e+00 (128)
    126:   objval =   2.088068648e+01   infeas =   4.353815783e-18 (112)
*   126:   objval =   2.088068648e+01   infeas =   2.220446049e-16 (112)
*   200:   objval =   1.446037689e+01   infeas =   3.885780586e-16 (99)
*   400:   objval =   8.348297709e+00   infeas =   0.000000000e+00 (70)
*   600:   objval =   8.348297709e+00   infeas =   0.000000000e+00 (26)
*   800:   objval =   8.348297709e+00   infeas =   0.000000000e+00 (22)
*  1000:   objval =   8.348297709e+00   infeas =   0.000000000e+00 (21)
. . . . . . .
* 50200:   objval =   7.462112984e+00   infeas =   8.411967574e-13 (16)
* 50361:   objval =   7.462112984e+00   infeas =   0.000000000e+00 (16)
OPTIMAL SOLUTION FOUND
Time used:   896.0 secs
Memory used: 30.1M (31515772 bytes)

In principle, glpk simplex is able to solve your problem; however,
I would suggest to use more specialized methods like network simplex
(it is not implemented in glpk) or a version of out-of-kilter
algorithm, because they would obtain the solution much faster.

Andrew Makhorin