[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Help-glpk] very small "infeas=" values in glpsol
From: |
Andrew Makhorin |
Subject: |
Re: [Help-glpk] very small "infeas=" values in glpsol |
Date: |
Sat, 10 Oct 2009 11:29:02 +0400 |
> I'm solving a semiconductor routing problem, and running glpsol, I'm
> running into very long solution times, accompanied by very small
> infeasibility numbers.
> Some questions:
> *) What do the infeasibility numbers mean? Does it matter that they're
> very small?
Once a next node subproblem is selected, the mip solver uses the dual
simplex to find optimal solution to its lp relaxation. If the solution
takes more than 5 seconds, the underlying simplex solver starts terminal
output to prevent a "dead screen", so you see something like this:
. . .
+129044: mip = not found yet <= 2.400000000e+002 (14; 9)
|130400: obj = 2.400000000e+002 infeas = 0.000e+000 (664)
|130600: obj = 2.400000000e+002 infeas = 0.000e+000 (663)
|130800: obj = 2.400000000e+002 infeas = 1.988e-014 (662)
|131000: obj = 2.400000000e+002 infeas = 0.000e+000 (662)
. . .
'infeas' is the sum of scaled dual infeasibilities usually reported
by the glpk simplex solvers. Normally it must be close to zero, because
on re-optimization the current basic solution is always dual feasible
within a working precision.
> *) Is there a way/runtime-option I can use to speed up the solution
> times?
Your instance seems to be highly degenerate and therefore hard for
the glpk mip solver. You could try either reformulating it or using
cutting plane options.
- Re: [Help-glpk] very small "infeas=" values in glpsol,
Andrew Makhorin <=