[Help-glpk] Re: Slow MIP Problem...

[Andrew Makhorin]

>I have a question regarding large MIP Problems. I have a problem with three
>20 digit binary variables, which means I use 60 boolean variables to
>characterise three variables from 0 to 1048575. The problems needs a very
>long time to find the optimum, Although the three variables are actually the
>same (I know this makes no sense. It is just for testing) and I have
>equations like x1 = y1 = z1, x2 = y2 = z1, x3 = y3 = z1, ...
>
>Is there a way to make the solving process faster (for example by telling
>the solver that x1 depends on y1 and z1 before the process), because I want
>to solve much bigger problems in the future...

Most probably your problem is *hard* for the glpk b&b solver. Besides,
as it seems to me, the straightforward formulation using 20-bit integer
variables may cause numerical difficulties not only for glpk independently
on whether you reduce them to binary ones or not. For example, the glpk
b&b solver uses the integer tolerance 1e-6 (and other known solvers use
even lesser tolerance), so it is difficult to distinguish between large
integer quantities computed with finite precision. On the other hand,
reducing to binary variables involves appearing constraint coefficients
from 1 to 2^(n-1), so large n may make the problem ill-conditioned and
also cause numerical instability.

If your problem is of combinatorial kind, I belive there should be
another, more efficient description than that you are using. Otherwise
you could consider 20-bit variables as continuous and after obtaining
the optimal solution simply round them to nearest integers.


Andrew Makhorin