Re: [Help-glpk] [Bug-glpk] [bug] glpk cycling

[Andrew Makhorin]

Please replace file glpk-4.63/src/simplex/spydual.c with a new one
(see attachment) and then build the package as usual.

Now your instance is solved successfully:

address@hidden:~/Desktop/glpk$ make
g++  -Wall -Wextra -pedantic -O3 -g -march=native -std=c++11  -c glpk.cc
-o glpk.o
g++  glpk.o -lglpk -lm -o glpk
address@hidden:~/Desktop/glpk$ ./glpk
GLPK Simplex Optimizer, v4.64
10 rows, 9 columns, 54 non-zeros
#     0: obj =   0.000000000e+00 inf =   0.000e+00 (5)
#     9: obj =   0.000000000e+00 inf =   0.000e+00 (0)
OPTIMAL LP SOLUTION FOUND
GLPK Simplex Optimizer, v4.64
14 rows, 9 columns, 80 non-zeros
#     9: obj =   0.000000000e+00 inf =   0.000e+00 (4)
#    14: obj =   0.000000000e+00 inf =   0.000e+00 (0)
OPTIMAL LP SOLUTION FOUND
GLPK Simplex Optimizer, v4.64
15 rows, 9 columns, 83 non-zeros
#    14: obj =   0.000000000e+00 inf =   0.000e+00 (1)
#    18: obj =   0.000000000e+00 inf =   0.000e+00 (0)
OPTIMAL LP SOLUTION FOUND
GLPK Simplex Optimizer, v4.64
17 rows, 9 columns, 93 non-zeros
#    18: obj =   0.000000000e+00 inf =   0.000e+00 (2)
Perturbing LP to avoid stalling [217]...
Removing LP perturbation [223]...
#   223: obj =   0.000000000e+00 inf =   0.000e+00 (0) 2
OPTIMAL LP SOLUTION FOUND
address@hidden:~/Desktop/glpk$

I changed the internal routine play_coef to perform more aggressive
perturbation to prevent dual degeneracy even if the current dual basic
solution is strongly feasible (as in your case, where the objective is
zero, so all reduced costs are always zero). BTW, in your case the
primal simplex would be preferable; why do you choose dual?


Best regards,

Andrew Makhorin

spydual.c.gz
Description: GNU Zip compressed data