[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Help-glpk] long-step dual ratio test in glpk 4.60
|
From: |
Andrew Makhorin |
|
Subject: |
Re: [Help-glpk] long-step dual ratio test in glpk 4.60 |
|
Date: |
Fri, 01 Apr 2016 16:38:08 +0300 |
A much more impressive effect of dual "textbook" ratio test vs dual long
step (us04 is a test lp instance from
http://www.sztaki.hu/~meszaros/public_ftp/lptestset/ ):
GLPSOL: GLPK LP/MIP Solver, v4.60
Parameter(s) specified in the command line:
us04.mps --dual --log 1.log
Reading problem data from 'us04.mps'...
Problem: us04.mps
Objective: 164
164 rows, 28016 columns, 325554 non-zeros
197828 records were read
Free objective row was removed
GLPK Simplex Optimizer, v4.60
163 rows, 28016 columns, 297538 non-zeros
Preprocessing...
163 rows, 28016 columns, 297538 non-zeros
Scaling...
A: min|aij| = 1.000e+00 max|aij| = 1.000e+00 ratio = 1.000e+00
Problem data seem to be well scaled
Constructing initial basis...
Size of triangular part is 107
# 0: obj = -2.603575500e+07 inf = 0.000e+00 (124)
# 500: obj = -2.510505500e+07 inf = 0.000e+00 (121)
# 1000: obj = -2.415973800e+07 inf = 0.000e+00 (121)
# 1500: obj = -2.290869854e+07 inf = 0.000e+00 (121)
# 2000: obj = -2.166928031e+07 inf = 0.000e+00 (121)
# 2500: obj = -2.107302139e+07 inf = 0.000e+00 (121)
# 3000: obj = -2.037209973e+07 inf = 0.000e+00 (121)
# 3500: obj = -1.911491575e+07 inf = 0.000e+00 (121)
# 4000: obj = -1.813316013e+07 inf = 0.000e+00 (116)
# 4500: obj = -1.732948957e+07 inf = 0.000e+00 (123)
# 5000: obj = -1.653905458e+07 inf = 0.000e+00 (126)
# 5500: obj = -1.580929007e+07 inf = 0.000e+00 (131)
# 6000: obj = -1.521174582e+07 inf = 0.000e+00 (122)
# 6500: obj = -1.461142784e+07 inf = 0.000e+00 (117) 1
# 7000: obj = -1.412392051e+07 inf = 0.000e+00 (117)
# 7500: obj = -1.345972953e+07 inf = 0.000e+00 (117)
# 8000: obj = -1.286223035e+07 inf = 0.000e+00 (117)
# 8500: obj = -1.242879305e+07 inf = 0.000e+00 (117)
# 9000: obj = -1.204674328e+07 inf = 0.000e+00 (117)
# 9500: obj = -1.157789201e+07 inf = 0.000e+00 (117)
# 10000: obj = -1.111477017e+07 inf = 0.000e+00 (117)
# 10500: obj = -1.070569503e+07 inf = 0.000e+00 (118)
# 11000: obj = -1.033423980e+07 inf = 0.000e+00 (118)
# 11500: obj = -1.004850164e+07 inf = 0.000e+00 (130)
# 12000: obj = -9.759715506e+06 inf = 0.000e+00 (124)
# 12500: obj = -9.511245138e+06 inf = 0.000e+00 (133)
# 13000: obj = -9.306469991e+06 inf = 0.000e+00 (130)
# 13500: obj = -9.123506862e+06 inf = 0.000e+00 (137)
# 14000: obj = -8.971916713e+06 inf = 0.000e+00 (137)
# 14500: obj = -8.795486836e+06 inf = 0.000e+00 (138)
# 15000: obj = -8.625822164e+06 inf = 0.000e+00 (138)
# 15500: obj = -8.464863209e+06 inf = 0.000e+00 (143)
# 16000: obj = -8.314036226e+06 inf = 0.000e+00 (143)
# 16500: obj = -8.104283361e+06 inf = 0.000e+00 (143)
# 17000: obj = -7.903658168e+06 inf = 0.000e+00 (143)
# 17500: obj = -7.691391088e+06 inf = 0.000e+00 (117) 1
# 18000: obj = -7.471289102e+06 inf = 0.000e+00 (117)
# 18500: obj = -7.251299685e+06 inf = 0.000e+00 (117)
# 19000: obj = -7.041476624e+06 inf = 0.000e+00 (117)
# 19500: obj = -6.816133060e+06 inf = 0.000e+00 (117)
# 20000: obj = -6.612029779e+06 inf = 0.000e+00 (117)
# 20500: obj = -6.421751911e+06 inf = 0.000e+00 (117)
# 21000: obj = -6.218943173e+06 inf = 0.000e+00 (117)
# 21500: obj = -6.015310557e+06 inf = 0.000e+00 (119)
# 22000: obj = -5.841747391e+06 inf = 0.000e+00 (120)
# 22500: obj = -5.640444478e+06 inf = 0.000e+00 (144)
# 23000: obj = -5.460614012e+06 inf = 0.000e+00 (141)
# 23500: obj = -5.316754756e+06 inf = 0.000e+00 (145)
# 24000: obj = -5.218218414e+06 inf = 0.000e+00 (144)
# 24500: obj = -5.164995476e+06 inf = 0.000e+00 (145)
# 25000: obj = -5.121545248e+06 inf = 0.000e+00 (114) 1
# 25500: obj = -5.064826380e+06 inf = 0.000e+00 (114)
# 26000: obj = -5.019705857e+06 inf = 0.000e+00 (114)
# 26500: obj = -4.873401450e+06 inf = 0.000e+00 (114)
# 27000: obj = -4.741044773e+06 inf = 0.000e+00 (114)
# 27500: obj = -4.579456204e+06 inf = 0.000e+00 (114)
# 28000: obj = -4.441922239e+06 inf = 0.000e+00 (114)
# 28500: obj = -4.346852346e+06 inf = 0.000e+00 (114)
# 29000: obj = -4.265109421e+06 inf = 0.000e+00 (114)
# 29500: obj = -4.188916175e+06 inf = 0.000e+00 (114)
# 30000: obj = -4.126386369e+06 inf = 0.000e+00 (113)
# 30500: obj = -4.076516368e+06 inf = 0.000e+00 (114)
# 31000: obj = -4.046542121e+06 inf = 0.000e+00 (114)
# 31500: obj = -3.966998373e+06 inf = 0.000e+00 (115)
# 32000: obj = -3.816651283e+06 inf = 0.000e+00 (117)
# 32500: obj = -3.644031999e+06 inf = 0.000e+00 (114) 1
# 33000: obj = -3.487010699e+06 inf = 0.000e+00 (114)
# 33500: obj = -3.339101604e+06 inf = 0.000e+00 (114)
# 34000: obj = -3.209108153e+06 inf = 0.000e+00 (114)
# 34500: obj = -3.114047893e+06 inf = 0.000e+00 (119)
# 35000: obj = -3.039669616e+06 inf = 0.000e+00 (125)
# 35500: obj = -2.908678108e+06 inf = 0.000e+00 (125)
# 36000: obj = -2.796670247e+06 inf = 0.000e+00 (133)
# 36500: obj = -2.703582699e+06 inf = 0.000e+00 (134)
# 37000: obj = -2.637234445e+06 inf = 0.000e+00 (135)
# 37500: obj = -2.548846816e+06 inf = 0.000e+00 (139)
# 38000: obj = -2.463545534e+06 inf = 0.000e+00 (142)
# 38500: obj = -2.381415127e+06 inf = 0.000e+00 (141)
# 39000: obj = -2.315608246e+06 inf = 0.000e+00 (140)
# 39500: obj = -2.269581994e+06 inf = 0.000e+00 (144)
# 40000: obj = -2.239871977e+06 inf = 0.000e+00 (133)
# 40500: obj = -2.209604958e+06 inf = 0.000e+00 (143)
# 41000: obj = -2.165105509e+06 inf = 0.000e+00 (114) 1
# 41500: obj = -2.065117751e+06 inf = 0.000e+00 (114)
# 42000: obj = -1.988336995e+06 inf = 0.000e+00 (113)
# 42500: obj = -1.915683025e+06 inf = 0.000e+00 (113)
# 43000: obj = -1.855272824e+06 inf = 0.000e+00 (113)
# 43500: obj = -1.827452739e+06 inf = 0.000e+00 (113)
# 44000: obj = -1.778495041e+06 inf = 0.000e+00 (113)
# 44500: obj = -1.722063128e+06 inf = 0.000e+00 (111)
# 45000: obj = -1.681863362e+06 inf = 0.000e+00 (119)
# 45500: obj = -1.656471114e+06 inf = 0.000e+00 (120)
# 46000: obj = -1.634488637e+06 inf = 0.000e+00 (134)
# 46500: obj = -1.590344052e+06 inf = 0.000e+00 (114) 1
# 47000: obj = -1.558818037e+06 inf = 0.000e+00 (114)
# 47500: obj = -1.543609425e+06 inf = 0.000e+00 (114)
# 48000: obj = -1.517397972e+06 inf = 0.000e+00 (113)
# 48500: obj = -1.472417150e+06 inf = 0.000e+00 (112)
# 49000: obj = -1.440310148e+06 inf = 0.000e+00 (113)
# 49500: obj = -1.426485913e+06 inf = 0.000e+00 (112)
# 50000: obj = -1.358869516e+06 inf = 0.000e+00 (129)
# 50500: obj = -1.279290469e+06 inf = 0.000e+00 (124)
# 51000: obj = -1.216084254e+06 inf = 0.000e+00 (128)
# 51500: obj = -1.166456043e+06 inf = 0.000e+00 (131)
# 52000: obj = -1.137577352e+06 inf = 0.000e+00 (132)
# 52500: obj = -1.124247452e+06 inf = 0.000e+00 (132)
# 53000: obj = -1.090594754e+06 inf = 0.000e+00 (111) 1
# 53500: obj = -1.056498198e+06 inf = 0.000e+00 (111)
# 54000: obj = -1.035740051e+06 inf = 0.000e+00 (110)
# 54500: obj = -9.935224851e+05 inf = 0.000e+00 (111)
# 55000: obj = -9.759412499e+05 inf = 0.000e+00 (111)
# 55500: obj = -9.352088913e+05 inf = 0.000e+00 (111)
# 56000: obj = -9.134047204e+05 inf = 0.000e+00 (114)
# 56500: obj = -8.966518456e+05 inf = 0.000e+00 (114)
# 57000: obj = -8.518567116e+05 inf = 0.000e+00 (113) 1
# 57500: obj = -8.218172354e+05 inf = 0.000e+00 (113)
# 58000: obj = -8.094484394e+05 inf = 0.000e+00 (113)
# 58500: obj = -7.855532946e+05 inf = 0.000e+00 (113)
# 59000: obj = -7.335774382e+05 inf = 0.000e+00 (112)
# 59500: obj = -6.964221848e+05 inf = 0.000e+00 (110)
# 60000: obj = -6.634387229e+05 inf = 0.000e+00 (110)
# 60500: obj = -6.151954989e+05 inf = 0.000e+00 (142)
# 61000: obj = -5.951245895e+05 inf = 0.000e+00 (141)
# 61500: obj = -5.745881074e+05 inf = 0.000e+00 (111) 1
# 62000: obj = -5.271600240e+05 inf = 0.000e+00 (111)
# 62500: obj = -4.967302732e+05 inf = 0.000e+00 (111)
# 63000: obj = -4.824083888e+05 inf = 0.000e+00 (110)
# 63500: obj = -4.618944228e+05 inf = 0.000e+00 (110)
# 64000: obj = -4.236553285e+05 inf = 0.000e+00 (111) 1
# 64500: obj = -3.982556592e+05 inf = 0.000e+00 (111)
# 65000: obj = -3.763865564e+05 inf = 0.000e+00 (111)
# 65500: obj = -3.504476599e+05 inf = 0.000e+00 (112)
# 66000: obj = -3.296727263e+05 inf = 0.000e+00 (112)
# 66500: obj = -3.137806456e+05 inf = 0.000e+00 (112) 1
# 67000: obj = -2.794097187e+05 inf = 0.000e+00 (112)
# 67500: obj = -2.540970105e+05 inf = 0.000e+00 (110)
# 68000: obj = -2.395460000e+05 inf = 0.000e+00 (112) 1
# 68500: obj = -2.214512631e+05 inf = 0.000e+00 (110)
# 69000: obj = -2.043903009e+05 inf = 0.000e+00 (111)
# 69500: obj = -1.871851638e+05 inf = 0.000e+00 (111)
# 70000: obj = -1.604190000e+05 inf = 0.000e+00 (112) 1
# 70500: obj = -1.454022702e+05 inf = 0.000e+00 (112)
# 71000: obj = -1.180823333e+05 inf = 0.000e+00 (109)
# 71500: obj = -9.454225412e+04 inf = 0.000e+00 (109) 1
# 72000: obj = -7.397737879e+04 inf = 0.000e+00 (107) 1
# 72500: obj = -5.517483333e+04 inf = 0.000e+00 (105)
# 73000: obj = -2.917524999e+04 inf = 0.000e+00 (103) 1
# 73500: obj = -1.633183333e+04 inf = 0.000e+00 (103) 1
# 74000: obj = 3.502666671e+02 inf = 0.000e+00 (96) 1
# 74500: obj = 1.280450000e+04 inf = 0.000e+00 (72) 3
# 74806: obj = 1.773166667e+04 inf = 1.273e-11 (0) 2
OPTIMAL LP SOLUTION FOUND
Time used: 883.1 secs
Memory used: 37.0 Mb (38779540 bytes)
GLPSOL: GLPK LP/MIP Solver, v4.60
Parameter(s) specified in the command line:
us04.mps --flip --log 2.log
Reading problem data from 'us04.mps'...
Problem: us04.mps
Objective: 164
164 rows, 28016 columns, 325554 non-zeros
197828 records were read
Free objective row was removed
GLPK Simplex Optimizer, v4.60
163 rows, 28016 columns, 297538 non-zeros
Preprocessing...
163 rows, 28016 columns, 297538 non-zeros
Scaling...
A: min|aij| = 1.000e+00 max|aij| = 1.000e+00 ratio = 1.000e+00
Problem data seem to be well scaled
Constructing initial basis...
Size of triangular part is 107
# 0: obj = -2.603575500e+07 inf = 0.000e+00 (124) 0,0
# 421: obj = 1.773166667e+04 inf = 1.705e-12 (0) 3 10,411
OPTIMAL LP SOLUTION FOUND
Time used: 2.5 secs
Memory used: 37.0 Mb (38779540 bytes)