Re: [Help-glpk] tiny MIP money division problem almost impractical to solve

[Andrew Makhorin]

> I have the following problem which is an example of division of money 
> between three people.
> I wanted the results to be more pleasing to the eye, so I tried to force 
> the amounts to be multiple of 50 instead of going down to 1.
> 
> I tried solving it with GLPK, and for some reason glpsol doesn't 
> converge, while for example CPLEX takes maybe 100ms to solve the same 
> problem translated by GLPK. Am I doing something wrong?
> 

Glpk cannot solve your mip using standard settings because of very large
integers involved, i.e. in optimal solution some integers variables take
on very large values; this, in particular, means that you may drop
integrality conditions and solve your instance as pure lp.

Changing the default branching heuristic to --first I managed to solve
your mip to optimality:

GLPSOL: GLPK LP/MIP Solver, v4.46
Parameter(s) specified in the command line:
 -m money.mod --first --log log.txt
Reading model section from money.mod...
41 lines were read
Generating z...
Generating R1...
Generating R2...
Generating R3...
Generating R4...
Generating R5...
Generating R6...
Generating R7... 
Generating R8...
Generating R9...
Generating R10...
Generating R11...
Generating R12...
Generating R13...
Model has been successfully generated
GLPK Integer Optimizer, v4.46
14 rows, 14 columns, 42 non-zeros
4 integer variables, none of which are binary
Preprocessing...
13 rows, 14 columns, 38 non-zeros
4 integer variables, none of which are binary
Scaling...
 A: min|aij| =  1.550e-01  max|aij| =  5.000e+01  ratio =  3.226e+02
GM: min|aij| =  5.276e-01  max|aij| =  1.895e+00  ratio =  3.592e+00
EQ: min|aij| =  2.784e-01  max|aij| =  1.000e+00  ratio =  3.592e+00
2N: min|aij| =  1.550e-01  max|aij| =  1.000e+00  ratio =  6.452e+00
Constructing initial basis...
Size of triangular part = 11
Solving LP relaxation...
GLPK Simplex Optimizer, v4.46
13 rows, 14 columns, 38 non-zeros
      0: obj =   9.096975000e+05  infeas =  3.047e+04 (2)
*     1: obj =   1.001107500e+06  infeas =  7.276e-12 (1)
OPTIMAL SOLUTION FOUND
Integer optimization begins...
+     1: mip =     not found yet >=              -inf        (1; 0)
+     8: >>>>>   1.005450000e+06 >=   1.001197500e+06   0.4% (3; 0)
+   184: mip =   1.005450000e+06 >=     tree is empty   0.0% (0; 67)
INTEGER OPTIMAL SOLUTION FOUND
Time used:   0.1 secs
Memory used: 0.1 Mb (142208 bytes)