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

[Andrew Makhorin]

-------- Forwarded Message --------
From: Matteo Fortini <address@hidden>
To: address@hidden
Subject: Re: [Help-glpk] tiny MIP money division problem almost
impractical to solve
Date: Sat, 30 Jul 2011 16:22:51 +0200

Thank you Andrew, both for your answer and for GLPK.

Actually it seems that the only branching heuristic which has problems 
is the default one: I tried all the other branching methods and they are 
all very fast. The --drtom heuristic instead is not able to solve it 
even after hours. Maybe it would be good to update GPLK FAQs to include 
the advice of trying more than one method and see which fits (of course 
I could have thought of that myself, but I only played with backtracking 
options, which were useless)

Thank you again,
Matteo

On 30/07/2011 15:35, Andrew Makhorin wrote:
>> 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)
>
>
>
> _______________________________________________
> Help-glpk mailing list
> address@hidden
> https://lists.gnu.org/mailman/listinfo/help-glpk
>