Re: [Help-glpk] counteracting infinite loops

[zephod]

Dear Nigel,

No libelling intended. Getting the permission for Black Arts and especially for sacrificing cats from the commission for ethics in science may be very time consuming. Isn't it possible I could get some more help with the white artish "please" or the mythical "pretty please"?

I'm running the solver on thousands of generated problems and have no way of checking myself if the solution is good. Is there a way to get such information from the solved, i.e., that the best guess is not more than some reasonable delta from the optimum? What would be a reasonable time limit if other problems get solved in seconds? In what order would you recommend to try the algorithms in?

Regards,

Zephod

Dnia 13 sierpnia 2016 15:10 Nigel Galloway <address@hidden> napisał(a):

Zephod, you may be libelling GLPK. What evidence do you have that it is in an infinite loop. Many problems, solvable by GLPK, are known to require a time longer than the age of the universe to complete (before quantum computers). The below is just getting started.

GLPK uses heuristics which solve these problems in a reasonable time a lot of the time. The worst case time is still usually longer than the age of the universe, and usually which are worst case is unpredictable.

You may set a time limit for GLPK's execution, and obtain its best guess so far. You may be able to prove that this guess is minimal, or close.

You can change the search algorithm GLPK is using which may find the solution faster.

You can change the formulation of the problem. Andrew has listed some problems which solve faster with restraints appearing to have nothing to do with the problem. My only comment is Mmm. These are Black Arts and probably require the sacrifice of cats or something.

--

  Nigel Galloway

address@hidden

On Thu, Aug 11, 2016, at 09:04 AM, zephod wrote:

I'm using GLPK version:

#define GLP_MAJOR_VERSION 4

#define GLP_MINOR_VERSION  60

For one of the inputs (out of many thousands that I'm running) the simplex solver goes into an infinite loop. I include part of the output below. My question is: is there any flag I could set for GLPK to abandon this computation after enough unsuccessful steps or something else that I could do to counteract infinite loops.

#355894500: obj =   1.000000000e+00 inf =   0.000e+00 (134) 7

#355895000: obj =   1.000000000e+00 inf =   0.000e+00 (8) 7

#355895500: obj =   1.000000000e+00 inf =   0.000e+00 (42) 7

#355896000: obj =   1.000000000e+00 inf =   0.000e+00 (3) 7

#355896500: obj =   1.000000000e+00 inf =   0.000e+00 (59) 7

#355897000: obj =   1.000000000e+00 inf =   0.000e+00 (10) 7

#355897500: obj =   1.000000000e+00 inf =   0.000e+00 (70) 7

#355898000: obj =   1.000000000e+00 inf =   0.000e+00 (4) 7

#355898500: obj =   1.000000000e+00 inf =   0.000e+00 (19) 7

#355899000: obj =   1.000000000e+00 inf =   0.000e+00 (5) 7

#355899500: obj =   1.000000000e+00 inf =   0.000e+00 (6) 8

#355900000: obj =   1.000000000e+00 inf =   0.000e+00 (134) 7

#355900500: obj =   1.000000000e+00 inf =   0.000e+00 (8) 7

#355901000: obj =   1.000000000e+00 inf =   0.000e+00 (42) 7

#355901500: obj =   1.000000000e+00 inf =   0.000e+00 (3) 7

#355902000: obj =   1.000000000e+00 inf =   0.000e+00 (59) 7

#355902500: obj =   1.000000000e+00 inf =   0.000e+00 (10) 7

#355903000: obj =   1.000000000e+00 inf =   0.000e+00 (69) 7

#355903500: obj =   1.000000000e+00 inf =   0.000e+00 (4) 7

#355904000: obj =   1.000000000e+00 inf =   0.000e+00 (19) 7

#355904500: obj =   1.000000000e+00 inf =   0.000e+00 (5) 7

#355905000: obj =   1.000000000e+00 inf =   0.000e+00 (6) 7

#355905500: obj =   1.000000000e+00 inf =   0.000e+00 (134) 7

#355906000: obj =   1.000000000e+00 inf =   0.000e+00 (8) 7

#355906500: obj =   1.000000000e+00 inf =   0.000e+00 (42) 7

#355907000: obj =   1.000000000e+00 inf =   0.000e+00 (3) 7

#355907500: obj =   1.000000000e+00 inf =   0.000e+00 (59) 7

#355908000: obj =   1.000000000e+00 inf =   0.000e+00 (10) 7

#355908500: obj =   1.000000000e+00 inf =   0.000e+00 (70) 7

#355909000: obj =   1.000000000e+00 inf =   0.000e+00 (4) 7

#355909500: obj =   1.000000000e+00 inf =   0.000e+00 (19) 7

#355910000: obj =   1.000000000e+00 inf =   0.000e+00 (5) 7

#355910500: obj =   1.000000000e+00 inf =   0.000e+00 (6) 7

Regards,

Zephod

_______________________________________________

Help-glpk mailing list

address@hidden

https://lists.gnu.org/mailman/listinfo/help-glpk

--
http://www.fastmail.com - A no graphics, no pop-ups email service

_______________________________________________

Help-glpk mailing list

address@hidden

https://lists.gnu.org/mailman/listinfo/help-glpk