[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.

reply via email to

[Prev in Thread] Current Thread [Next in Thread]