Looks like large constraint coefficients cause the effect described in the paper:
A. Neumaier and O. Shcherbina, Safe bounds in linear and mixed-integer programming, Math. Programming A 99 (2004), 283-296. http://www.mat.univie.ac.at/~neum/ms/mip.pdf when tightening the feasible region "improves" the optimum. In particular, if MIR or Gomory mixed integer cuts are enabled, glpsol finds the correct solution: $ glpsol --cpxlp glpkin.txt --mir GLPSOL: GLPK LP/MIP Solver 4.40 Reading problem data from `glpkin.txt'... 12 rows, 48 columns, 216 non-zeros 48 integer variables, all of which are binary 178 lines were read ipp_basic_tech: 0 row(s) and 0 column(s) removed ipp_reduce_bnds: 1 pass(es) made, 0 bound(s) reduced ipp_basic_tech: 0 row(s) and 0 column(s) removed ipp_reduce_coef: 1 pass(es) made, 0 coefficient(s) reduced glp_intopt: presolved MIP has 12 rows, 48 columns, 216 non-zeros glp_intopt: 48 integer columns, all of which are binary Scaling... A: min|aij| = 1.000e+00 max|aij| = 5.040e+07 ratio = 5.040e+07 GM: min|aij| = 6.708e-01 max|aij| = 1.491e+00 ratio = 2.222e+00 EQ: min|aij| = 4.650e-01 max|aij| = 1.000e+00 ratio = 2.151e+00 2N: min|aij| = 2.500e-01 max|aij| = 1.439e+00 ratio = 5.758e+00 Constructing initial basis... Size of triangular part = 12 Solving LP relaxation... * 0: obj = 5.975086563e+04 infeas = 0.000e+00 (0) * 23: obj = 4.295331243e+04 infeas = 0.000e+00 (0) OPTIMAL SOLUTION FOUND Integer optimization begins... MIR cuts enabled + 23: mip = not found yet >= -inf (1; 0) + 63: >>>>> 4.296612894e+04 >= 4.295331243e+04 < 0.1% (7; 0) + 64: >>>>> 4.295674010e+04 >= 4.295331243e+04 < 0.1% (5; 3) + 65: >>>>> 4.295528707e+04 >= 4.295331243e+04 < 0.1% (4; 5) + 80: >>>>> 4.295372226e+04 >= 4.295346307e+04 < 0.1% (2; 8) + 84: mip = 4.295372226e+04 >= tree is empty 0.0% (0; 13) INTEGER OPTIMAL SOLUTION FOUND Time used: 0.0 secs Memory used: 0.2 Mb (162716 bytes) _______________________________________________ Bug-glpk mailing list Bug-glpk@gnu.org http://lists.gnu.org/mailman/listinfo/bug-glpk