[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Bug-glpk] GLPK fails to solve
|
From: |
Andrew Makhorin |
|
Subject: |
Re: [Bug-glpk] GLPK fails to solve |
|
Date: |
Wed, 20 Aug 2014 19:22:00 +0400 |
Hi Marc,
Thank you for your bug report.
I could reproduce it (hope it is ille bug):
[...]
16000: obj = 1.379370021e+11 infeas = 2.819e+05 (53)
16500: obj = 1.389472238e+11 infeas = 2.464e+05 (52)
17000: obj = 1.454430661e+11 infeas = 1.917e+05 (33)
EXCEPTION AT 0051E8AC - ACCESS VIOLATION (C0000005)
Call traceback
func __trap, file ../c.lib/src/woe/xtrap.c, line 118
func _glp_sgf_dense_phase, file src/bflib/sgf.c, line 1143
func _glp_sgf_factorize, file src/bflib/sgf.c, line 1388
func _glp_lufint_factorize, file src/bflib/lufint.c, line 145
func _glp_fhvint_factorize, file src/bflib/fhvint.c, line 51
func _glp_bfd_factorize, file src/bfd.c, line 218
func invert_B, file src/glpspx01.c, line 454
func _glp_spx_primal, file src/glpspx01.c, line 2601
func solve_lp, file src/glpapi06.c, line 243
func preprocess_and_solve_lp, file src/glpapi06.c, line 329
func glp_simplex, file src/glpapi06.c, line 455
func glp_main, file src/glpapi21.c, line 1269
func __start, file ../c.lib/src/woe/c0.c, line 71
End of traceback
I need a time to fix it (though it'd be sufficient to disable the dense
phase).
Andrew Makhorin
On Tue, 2014-08-19 at 20:11 -0500, Meketon, Marc wrote:
> Hi Andrew,
>
>
>
> That attached MPS (which was generated by GLPSOL) fails to solve using
> the 32bit GLPK v4.52 and the primal algorithm. It solves fine in CLP
> (and in about 20 seconds).
>
>
>
> In GLPK, it causes a program crash, with an error code of -1073741819.
> See the log below
>
>
>
> I tried both the primal and dual Simplex algorithm, only the primal
> fails; the duals finds the solution in about 850 seconds. The MPS
> file was generated using GMPL/glpsol.
>
>
>
> -Marc
>
>
>
> Below is the log file when trying to solve with the primal algorithm.
> Please ignore the “time” since I had put the computer to sleep for a
> while.
>
>
>
>
>
> >C:\gusek\glpsol.exe --cover --clique --gomory --mir --freemps
> "MPP_v16.mps"
>
> GLPSOL: GLPK LP/MIP Solver, v4.52
>
> Parameter(s) specified in the command line:
>
> --cover --clique --gomory --mir --freemps MPP_v16.mps
>
> Reading problem data from `MPP_v16.mps'...
>
> Problem: MPP_v16
>
> Objective: ManpowerPlusTraining
>
> 135825 rows, 182992 columns, 748638 non-zeros
>
> 579544 records were read
>
> GLPK Simplex Optimizer, v4.52
>
> 135825 rows, 182992 columns, 748638 non-zeros
>
> Preprocessing...
>
> 127439 rows, 156909 columns, 576115 non-zeros
>
> Scaling...
>
> A: min|aij| = 2.649e-004 max|aij| = 1.300e+001 ratio = 4.907e+004
>
> GM: min|aij| = 1.276e-001 max|aij| = 7.838e+000 ratio = 6.144e+001
>
> EQ: min|aij| = 1.628e-002 max|aij| = 1.000e+000 ratio = 6.144e+001
>
> Constructing initial basis...
>
> Size of triangular part is 125953
>
> 0: obj = -1.040776100e+010 infeas = 1.576e+006 (1486)
>
> 500: obj = -1.040767560e+010 infeas = 1.575e+006 (1370)
>
> 1000: obj = -1.040394782e+010 infeas = 1.557e+006 (1305)
>
> Warning: numerical instability (primal simplex, phase I)
>
> 1057: obj = -1.040394782e+010 infeas = 1.557e+006 (1295)
>
> 1500: obj = -1.039821623e+010 infeas = 1.549e+006 (1278)
>
> 2000: obj = -1.039422852e+010 infeas = 1.529e+006 (1219)
>
> Warning: numerical instability (primal simplex, phase I)
>
> 2245: obj = -1.039422852e+010 infeas = 1.529e+006 (1174)
>
> 2500: obj = -1.039343863e+010 infeas = 1.524e+006 (1152)
>
> 3000: obj = -1.039343863e+010 infeas = 1.524e+006 (1044)
>
> Warning: numerical instability (primal simplex, phase I)
>
> 3385: obj = -1.039343863e+010 infeas = 1.524e+006 (961)
>
> Warning: numerical instability (primal simplex, phase I)
>
> 3391: obj = -1.039343863e+010 infeas = 1.524e+006 (961)
>
> Warning: numerical instability (primal simplex, phase I)
>
> 3397: obj = -1.039343863e+010 infeas = 1.524e+006 (961)
>
> Warning: numerical instability (primal simplex, phase I)
>
> 3403: obj = -1.039343863e+010 infeas = 1.524e+006 (961)
>
> Warning: numerical instability (primal simplex, phase I)
>
> 3409: obj = -1.039343863e+010 infeas = 1.524e+006 (961)
>
> 3500: obj = -1.039328300e+010 infeas = 1.523e+006 (938)
>
> 4000: obj = -1.039328300e+010 infeas = 1.523e+006 (840)
>
> Warning: numerical instability (primal simplex, phase I)
>
> 4426: obj = -1.039303373e+010 infeas = 1.522e+006 (763)
>
> Warning: numerical instability (primal simplex, phase I)
>
> 4443: obj = -1.038749049e+010 infeas = 1.515e+006 (762)
>
> Warning: numerical instability (primal simplex, phase I)
>
> 4445: obj = -1.038754329e+010 infeas = 1.515e+006 (762)
>
> 4500: obj = -1.038754177e+010 infeas = 1.515e+006 (762)
>
> Warning: numerical instability (primal simplex, phase I)
>
> 4556: obj = -1.038754150e+010 infeas = 1.515e+006 (762)
>
> Warning: numerical instability (primal simplex, phase I)
>
> 4784: obj = -1.038751958e+010 infeas = 1.515e+006 (761)
>
> Warning: numerical instability (primal simplex, phase I)
>
> 4894: obj = -1.038751036e+010 infeas = 1.515e+006 (761)
>
> Warning: numerical instability (primal simplex, phase I)
>
> 4913: obj = -1.038753866e+010 infeas = 1.515e+006 (761)
>
> 5000: obj = -1.038753559e+010 infeas = 1.515e+006 (761)
>
> Warning: numerical instability (primal simplex, phase I)
>
> 5022: obj = -1.038753333e+010 infeas = 1.515e+006 (761)
>
> Warning: numerical instability (primal simplex, phase I)
>
> 5136: obj = -1.038752446e+010 infeas = 1.515e+006 (761)
>
> Warning: numerical instability (primal simplex, phase I)
>
> 5244: obj = -1.038752065e+010 infeas = 1.515e+006 (761)
>
> Warning: numerical instability (primal simplex, phase I)
>
> 5351: obj = -1.038751189e+010 infeas = 1.515e+006 (761)
>
> Warning: numerical instability (primal simplex, phase I)
>
> 5458: obj = -1.038751380e+010 infeas = 1.515e+006 (761)
>
> 5500: obj = -1.038750568e+010 infeas = 1.515e+006 (761)
>
> Warning: numerical instability (primal simplex, phase I)
>
> 5565: obj = -1.038750343e+010 infeas = 1.515e+006 (761)
>
> Warning: numerical instability (primal simplex, phase I)
>
> 5670: obj = -1.038750293e+010 infeas = 1.515e+006 (761)
>
> Warning: numerical instability (primal simplex, phase I)
>
> 5673: obj = -1.039225936e+010 infeas = 1.535e+006 (761)
>
> Warning: numerical instability (primal simplex, phase I)
>
> 5789: obj = -1.039155576e+010 infeas = 1.533e+006 (760)
>
> Warning: numerical instability (primal simplex, phase I)
>
> 5898: obj = -1.039149415e+010 infeas = 1.533e+006 (759)
>
> 6000: obj = -1.039143833e+010 infeas = 1.533e+006 (759)
>
> Warning: numerical instability (primal simplex, phase I)
>
> 6010: obj = -1.039143851e+010 infeas = 1.533e+006 (759)
>
> Warning: numerical instability (primal simplex, phase I)
>
> 6113: obj = -1.050399968e+010 infeas = 1.871e+006 (759)
>
> Warning: numerical instability (primal simplex, phase I)
>
> 6241: obj = -1.052549744e+010 infeas = 1.937e+006 (759)
>
> Warning: numerical instability (primal simplex, phase I)
>
> 6335: obj = -1.052010953e+010 infeas = 1.920e+006 (759)
>
> 6500: obj = -1.050387462e+010 infeas = 1.870e+006 (757)
>
> Warning: numerical instability (primal simplex, phase I)
>
> 6560: obj = -1.050143625e+010 infeas = 1.863e+006 (757)
>
> Warning: numerical instability (primal simplex, phase I)
>
> 6696: obj = -1.049880092e+010 infeas = 1.854e+006 (757)
>
> Warning: numerical instability (primal simplex, phase I)
>
> 6733: obj = -1.053563294e+010 infeas = 1.965e+006 (756)
>
> Warning: numerical instability (primal simplex, phase I)
>
> 6837: obj = -1.045355753e+010 infeas = 1.717e+006 (756)
>
> Warning: numerical instability (primal simplex, phase I)
>
> 6838: obj = -1.045608406e+010 infeas = 1.725e+006 (756)
>
> Warning: numerical instability (primal simplex, phase I)
>
> 6944: obj = -1.046121888e+010 infeas = 1.740e+006 (756)
>
> Warning: numerical instability (primal simplex, phase I)
>
> 6979: obj = -1.055757619e+010 infeas = 2.035e+006 (756)
>
> Warning: numerical instability (primal simplex, phase I)
>
> 6999: obj = -1.087192219e+010 infeas = 3.022e+006 (756)
>
> 7000: obj = -1.087192219e+010 infeas = 3.022e+006 (756)
>
> Warning: numerical instability (primal simplex, phase I)
>
> 7007: obj = -1.127865205e+010 infeas = 4.308e+006 (756)
>
> Warning: numerical instability (primal simplex, phase I)
>
> 7159: obj = -1.122005321e+010 infeas = 4.122e+006 (756)
>
> Warning: numerical instability (primal simplex, phase I)
>
> 7216: obj = -1.121573354e+010 infeas = 4.107e+006 (756)
>
> Warning: numerical instability (primal simplex, phase I)
>
> 7298: obj = -1.061857763e+010 infeas = 2.154e+006 (756)
>
> Warning: numerical instability (primal simplex, phase I)
>
> 7420: obj = -1.060866484e+010 infeas = 2.122e+006 (755)
>
> 7500: obj = -1.060240259e+010 infeas = 2.103e+006 (755)
>
> Warning: numerical instability (primal simplex, phase I)
>
> 7665: obj = -1.066535028e+010 infeas = 2.274e+006 (755)
>
> Warning: numerical instability (primal simplex, phase I)
>
> 7674: obj = -1.065880459e+010 infeas = 2.256e+006 (755)
>
> Warning: numerical instability (primal simplex, phase I)
>
> 7678: obj = -1.067505524e+010 infeas = 2.302e+006 (755)
>
> Warning: numerical instability (primal simplex, phase I)
>
> 7753: obj = -1.066768636e+010 infeas = 2.285e+006 (754)
>
> Warning: numerical instability (primal simplex, phase I)
>
> 7801: obj = -1.069162479e+010 infeas = 2.364e+006 (754)
>
> Warning: numerical instability (primal simplex, phase I)
>
> 7839: obj = -1.070734536e+010 infeas = 2.393e+006 (754)
>
> 8000: obj = -1.069894976e+010 infeas = 2.377e+006 (754)
>
> 8500: obj = -1.062687414e+010 infeas = 2.172e+006 (754)
>
> 9000: obj = -1.061556476e+010 infeas = 2.140e+006 (754)
>
> Warning: numerical instability (primal simplex, phase I)
>
> 9027: obj = -1.061545046e+010 infeas = 2.140e+006 (754)
>
> Warning: numerical instability (primal simplex, phase I)
>
> 9197: obj = -1.060966730e+010 infeas = 2.125e+006 (754)
>
> Warning: numerical instability (primal simplex, phase I)
>
> 9218: obj = -1.069913146e+010 infeas = 2.361e+006 (754)
>
> Warning: numerical instability (primal simplex, phase I)
>
> 9333: obj = -1.068488550e+010 infeas = 2.323e+006 (754)
>
> 9500: obj = -1.066646965e+010 infeas = 2.274e+006 (754)
>
> Warning: numerical instability (primal simplex, phase I)
>
> 9577: obj = -1.064105636e+010 infeas = 2.205e+006 (753)
>
> Warning: numerical instability (primal simplex, phase I)
>
> 9613: obj = -1.061437479e+010 infeas = 2.171e+006 (753)
>
> Warning: numerical instability (primal simplex, phase I)
>
> 9614: obj = -1.063311758e+010 infeas = 2.223e+006 (753)
>
> Warning: numerical instability (primal simplex, phase I)
>
> 9651: obj = -1.062505146e+010 infeas = 2.204e+006 (753)
>
> Warning: numerical instability (primal simplex, phase I)
>
> 9652: obj = -1.062965468e+010 infeas = 2.216e+006 (753)
>
> Warning: numerical instability (primal simplex, phase I)
>
> 9762: obj = -1.061732117e+010 infeas = 2.182e+006 (752)
>
> Warning: numerical instability (primal simplex, phase I)
>
> 9787: obj = -1.061753233e+010 infeas = 2.182e+006 (751)
>
> Warning: numerical instability (primal simplex, phase I)
>
> 9837: obj = -1.061573798e+010 infeas = 2.177e+006 (751)
>
> Warning: numerical instability (primal simplex, phase I)
>
> 9838: obj = -1.072720392e+010 infeas = 2.495e+006 (751)
>
> Warning: numerical instability (primal simplex, phase I)
>
> 9843: obj = -1.072464743e+010 infeas = 2.488e+006 (751)
>
> Warning: numerical instability (primal simplex, phase I)
>
> 9844: obj = -1.075156053e+010 infeas = 2.564e+006 (751)
>
> Warning: numerical instability (primal simplex, phase I)
>
> 9958: obj = -1.071365989e+010 infeas = 2.457e+006 (749)
>
> 10000: obj = -1.070620421e+010 infeas = 2.436e+006 (749)
>
> Warning: numerical instability (primal simplex, phase I)
>
> 10022: obj = -1.070414015e+010 infeas = 2.431e+006 (749)
>
> Warning: numerical instability (primal simplex, phase I)
>
> 10031: obj = -1.070219131e+010 infeas = 2.425e+006 (749)
>
> Warning: numerical instability (primal simplex, phase I)
>
> 10091: obj = -1.070191522e+010 infeas = 2.424e+006 (749)
>
> Warning: numerical instability (primal simplex, phase I)
>
> 10097: obj = -1.099663052e+010 infeas = 3.249e+006 (749)
>
> Warning: numerical instability (primal simplex, phase I)
>
> 10208: obj = -1.100513385e+010 infeas = 3.273e+006 (749)
>
> Warning: numerical instability (primal simplex, phase I)
>
> 10226: obj = -1.185740360e+010 infeas = 5.652e+006 (749)
>
> 10500: obj = -1.164369905e+010 infeas = 5.052e+006 (745)
>
> Warning: numerical instability (primal simplex, phase I)
>
> 10559: obj = -1.162793753e+010 infeas = 5.008e+006 (745)
>
> Warning: numerical instability (primal simplex, phase I)
>
> 10754: obj = -1.152727897e+010 infeas = 4.727e+006 (744)
>
> 11000: obj = -1.146322329e+010 infeas = 4.548e+006 (744)
>
> 11500: obj = -1.139012781e+010 infeas = 4.338e+006 (741)
>
> 12000: obj = -1.129672756e+010 infeas = 4.062e+006 (740)
>
> Warning: numerical instability (primal simplex, phase I)
>
> 12446: obj = -1.129584286e+010 infeas = 4.059e+006 (740)
>
> 12500: obj = -1.129575107e+010 infeas = 4.058e+006 (740)
>
> 13000: obj = -1.129520086e+010 infeas = 4.055e+006 (740)
>
> 13500: obj = -1.129129908e+010 infeas = 4.048e+006 (737)
>
> 14000: obj = -1.121217928e+010 infeas = 3.904e+006 (736)
>
> 14500: obj = -1.090645376e+010 infeas = 3.347e+006 (732)
>
> 15000: obj = -1.080187966e+010 infeas = 3.157e+006 (731)
>
> 15500: obj = -1.073222825e+010 infeas = 3.031e+006 (730)
>
> 16000: obj = -1.069081112e+010 infeas = 2.956e+006 (727)
>
> 16500: obj = -1.063029024e+010 infeas = 2.847e+006 (727)
>
> 17000: obj = -1.055671721e+010 infeas = 2.714e+006 (726)
>
> 17500: obj = -1.049744046e+010 infeas = 2.607e+006 (725)
>
> 18000: obj = -1.045425416e+010 infeas = 2.529e+006 (723)
>
> 18500: obj = -1.039807250e+010 infeas = 2.428e+006 (719)
>
> 19000: obj = -1.035229611e+010 infeas = 2.345e+006 (717)
>
> Warning: numerical instability (primal simplex, phase I)
>
> 19005: obj = -1.035230753e+010 infeas = 2.345e+006 (717)
>
> 19500: obj = -1.033032190e+010 infeas = 2.306e+006 (716)
>
> 20000: obj = -1.029801845e+010 infeas = 2.248e+006 (714)
>
> 20500: obj = -1.025090264e+010 infeas = 2.165e+006 (712)
>
> 21000: obj = -1.022040504e+010 infeas = 2.110e+006 (711)
>
> 21500: obj = -1.019952733e+010 infeas = 2.074e+006 (708)
>
> Warning: numerical instability (primal simplex, phase I)
>
> 21610: obj = -1.019958709e+010 infeas = 2.074e+006 (707)
>
> 22000: obj = -1.018794454e+010 infeas = 2.053e+006 (707)
>
> 22500: obj = -1.016595191e+010 infeas = 2.015e+006 (706)
>
> 23000: obj = -1.015128937e+010 infeas = 1.989e+006 (704)
>
> 23500: obj = -1.012364219e+010 infeas = 1.941e+006 (704)
>
> 24000: obj = -1.009611772e+010 infeas = 1.894e+006 (703)
>
> 24500: obj = -1.007657689e+010 infeas = 1.860e+006 (700)
>
> 25000: obj = -1.004908465e+010 infeas = 1.813e+006 (696)
>
> 25500: obj = -1.002570421e+010 infeas = 1.772e+006 (693)
>
> 26000: obj = -1.000935739e+010 infeas = 1.744e+006 (690)
>
> 26500: obj = -9.990587841e+009 infeas = 1.711e+006 (689)
>
> 27000: obj = -9.975522255e+009 infeas = 1.683e+006 (685)
>
> 27500: obj = -9.956631516e+009 infeas = 1.652e+006 (682)
>
> 28000: obj = -9.937312424e+009 infeas = 1.619e+006 (681)
>
> 28500: obj = -9.919192042e+009 infeas = 1.589e+006 (679)
>
> 29000: obj = -9.899046235e+009 infeas = 1.555e+006 (669)
>
> 29500: obj = -9.893088942e+009 infeas = 1.546e+006 (667)
>
> 30000: obj = -9.886771329e+009 infeas = 1.539e+006 (662)
>
> 30500: obj = -9.882893737e+009 infeas = 1.535e+006 (659)
>
> 31000: obj = -9.871080606e+009 infeas = 1.526e+006 (650)
>
> 31500: obj = -9.864702309e+009 infeas = 1.522e+006 (646)
>
> Warning: numerical instability (primal simplex, phase I)
>
> 31699: obj = -9.864694693e+009 infeas = 1.522e+006 (608)
>
> 32000: obj = -9.864203527e+009 infeas = 1.521e+006 (606)
>
> 32500: obj = -9.859989131e+009 infeas = 1.517e+006 (597)
>
> 33000: obj = -9.857971034e+009 infeas = 1.516e+006 (592)
>
> 33500: obj = -9.859608905e+009 infeas = 1.516e+006 (585)
>
> 34000: obj = -9.862816648e+009 infeas = 1.515e+006 (582)
>
> 34500: obj = -9.862699481e+009 infeas = 1.515e+006 (578)
>
> 35000: obj = -9.755191594e+009 infeas = 1.493e+006 (523)
>
> 35500: obj = -7.166585911e+009 infeas = 1.399e+006 (483)
>
> 36000: obj = -3.105481856e+009 infeas = 1.340e+006 (430)
>
> 36500: obj = 9.758402747e+009 infeas = 1.269e+006 (395)
>
> 37000: obj = 3.227812851e+010 infeas = 1.230e+006 (336)
>
> 37500: obj = 9.606387008e+010 infeas = 1.162e+006 (272)
>
> 38000: obj = 9.331517519e+010 infeas = 1.110e+006 (202)
>
> 38500: obj = 9.569619542e+010 infeas = 1.008e+006 (192)
>
> 39000: obj = 8.693322788e+010 infeas = 9.238e+005 (163)
>
> 39500: obj = 8.398161026e+010 infeas = 8.691e+005 (154)
>
> 40000: obj = 8.786748759e+010 infeas = 8.059e+005 (136)
>
> 40500: obj = 9.066086608e+010 infeas = 7.567e+005 (123)
>
> 41000: obj = 9.230583414e+010 infeas = 7.072e+005 (111)
>
> 41500: obj = 9.613267613e+010 infeas = 6.517e+005 (106)
>
> 42000: obj = 1.080752540e+011 infeas = 5.902e+005 (90)
>
> 42500: obj = 1.155325567e+011 infeas = 5.421e+005 (85)
>
> 43000: obj = 1.225569894e+011 infeas = 4.894e+005 (77)
>
> 43500: obj = 1.432175954e+011 infeas = 4.397e+005 (72)
>
> 44000: obj = 1.648361247e+011 infeas = 3.695e+005 (64)
>
> 44500: obj = 1.726011476e+011 infeas = 3.272e+005 (59)
>
> 45000: obj = 1.772670475e+011 infeas = 2.605e+005 (50)
>
> 45500: obj = 1.797377671e+011 infeas = 2.270e+005 (46)
>
> 46000: obj = 1.813868645e+011 infeas = 1.828e+005 (37)
>
> >Exit code: -1073741819 Time: 9271.811
>
>
>
>
> ______________________________________________________________________
> This e-mail and any attachments may be confidential or legally
> privileged. If you received this message in error or are not the
> intended recipient, you should destroy the e-mail message and any
> attachments or copies, and you are prohibited from retaining,
> distributing, disclosing or using any information contained herein.
> Please inform us of the erroneous delivery by return e-mail. Thank you
> for your cooperation.
- Re: [Bug-glpk] GLPK fails to solve,
Andrew Makhorin <=