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

[Andrew Makhorin]

-------- Forwarded Message --------
From: Matteo Fortini <address@hidden>
To: address@hidden
Subject: tiny MIP money division problem almost impractical to solve
Date: Sat, 30 Jul 2011 14:31:12 +0200

Hi all,
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?

TIA,
Matteo

var valA >= 179000;
var valB >= 229000;
var valC >= 100000;
var valD >= 325500;

var valBobIni >= 0;
var valAliceIni >= 0;
var valCharlieIni >= 0;

var valBobFin >= 0;
var valAliceFin >= 0;
var valCharlieFin >= 0;

param step := 50 integer;

var numstepA >= 0 integer ;
var numstepB >= 0 integer ;
var numstepC >= 0 integer ;
var numstepD >= 0 integer ;

minimize z: valA + valB + valC + valD;

s.t. R1: valBobIni = valBobFin;
s.t. R2: valAliceIni = valAliceFin;
s.t. R3: valCharlieIni = valCharlieFin;

s.t. R4: valBobIni = valA/3 + valB/3 + valC/3 + valD/6;
s.t. R5: valAliceIni = valA/3 + valB/3 + valC/3 + valD/6;
s.t. R6: valCharlieIni = valA/3 + valB/3 + valC/3 + (4*valD)/6;

s.t. R7: valBobFin = valA + 0.215 * valD;
s.t. R8: valAliceFin = valB + 0.155 * valD;
s.t. R9: valCharlieFin = valC + 0.63 * valD;

s.t. R10: valA = step * numstepA;
s.t. R11: valB = step * numstepB;
s.t. R12: valC = step * numstepC;
s.t. R13: valD = step * numstepD;


end;