Hi Emma, > The attached example can be solved quickly in 4.56 but not in 4.57 and > afterwards.
Starting with version 4.56 Andrew is improving the solver routines, however I don't think this is the issue here. Using GLPK 4.60 (the latest released version), I can quickly solve your problem with pseudocost brancing, However if I disable the MIP presolver (--nointopt) I get a different solution, which is strongly indicating accuracy issues. Indeed the line: A: min|aij| = 2.451e-011 max|aij| = 1.158e+077 ratio = 4.724e+087 indicates that there are some very large values in the problem, which can cause problems like this. Is this a big M formulation like the one you showed last week? Best Regards, Chris Matrakidis PS. The output from the first run is: GLPSOL: GLPK LP/MIP Solver, v4.60 Parameter(s) specified in the command line: --pcost --glp \Users\Chris\Downloads\lp.txt Reading problem data from '\Users\Chris\Downloads\lp.txt'... 332 rows, 190 columns, 5043 non-zeros 95 integer variables, all of which are binary 5563 lines were read GLPK Integer Optimizer, v4.60 332 rows, 190 columns, 5043 non-zeros 95 integer variables, all of which are binary Preprocessing... 95 constraint coefficient(s) were reduced 154 rows, 190 columns, 3899 non-zeros 95 integer variables, all of which are binary Scaling... A: min|aij| = 1.307e-009 max|aij| = 7.569e+005 ratio = 5.792e+014 GM: min|aij| = 1.939e-004 max|aij| = 5.157e+003 ratio = 2.659e+007 EQ: min|aij| = 3.761e-008 max|aij| = 1.000e+000 ratio = 2.659e+007 2N: min|aij| = 4.643e-008 max|aij| = 1.710e+000 ratio = 3.684e+007 Constructing initial basis... Size of triangular part is 154 Solving LP relaxation... GLPK Simplex Optimizer, v4.60 154 rows, 190 columns, 3899 non-zeros 0: obj = 1.934670808e+006 inf = 1.688e+005 (93) 231: obj = 1.673470251e-009 inf = 1.269e-015 (0) 1 OPTIMAL LP SOLUTION FOUND Integer optimization begins... + 231: mip = not found yet >= -inf (1; 0) Warning: numerical instability (dual simplex, phase II) + 15741: >>>>> 3.256673153e-008 >= 1.666194294e-009 94.9% (20; 368) + 15741: mip = 3.256673153e-008 >= tree is empty 0.0% (0; 583) INTEGER OPTIMAL SOLUTION FOUND Time used: 1.4 secs Memory used: 1.2 Mb (1220521 bytes) Without MIP presolving: GLPSOL: GLPK LP/MIP Solver, v4.60 Parameter(s) specified in the command line: --pcost --glp \Users\Chris\Downloads\lp.txt --nointopt Reading problem data from '\Users\Chris\Downloads\lp.txt'... 332 rows, 190 columns, 5043 non-zeros 95 integer variables, all of which are binary 5563 lines were read Scaling... A: min|aij| = 2.451e-011 max|aij| = 1.158e+077 ratio = 4.724e+087 GM: min|aij| = 1.939e-004 max|aij| = 5.157e+003 ratio = 2.659e+007 EQ: min|aij| = 3.761e-008 max|aij| = 1.000e+000 ratio = 2.659e+007 Constructing initial basis... Size of triangular part is 328 GLPK Simplex Optimizer, v4.60 332 rows, 190 columns, 5043 non-zeros Preprocessing... 154 rows, 190 columns, 3899 non-zeros Scaling... A: min|aij| = 1.307e-009 max|aij| = 1.158e+077 ratio = 8.862e+085 GM: min|aij| = 1.939e-004 max|aij| = 5.157e+003 ratio = 2.659e+007 EQ: min|aij| = 3.761e-008 max|aij| = 1.000e+000 ratio = 2.659e+007 Constructing initial basis... Size of triangular part is 154 0: obj = 1.934670808e+006 inf = 1.884e+045 (1) 4: obj = 1.934670808e+006 inf = 1.394e-026 (0) * 76: obj = -3.027563880e+006 inf = 4.264e-027 (0) OPTIMAL LP SOLUTION FOUND GLPK Integer Optimizer, v4.60 332 rows, 190 columns, 5043 non-zeros 95 integer variables, all of which are binary Integer optimization begins... + 76: mip = not found yet >= -inf (1; 0) + 76: >>>>> -3.027563880e+006 >= -3.027563880e+006 0.0% (1; 0) + 76: mip = -3.027563880e+006 >= tree is empty 0.0% (0; 1) INTEGER OPTIMAL SOLUTION FOUND Time used: 0.1 secs Memory used: 0.6 Mb (603108 bytes) _______________________________________________ Bug-glpk mailing list Bug-glpk@gnu.org https://lists.gnu.org/mailman/listinfo/bug-glpk