Re: [Help-glpk] Working with larger numbers

[Andrew Makhorin]

> we are working on a tool that utilizes glpk to solve a set of maximum
> and minimum cost flows. So far, our approach looks promising. (This
> implies a big thank-you to glpk team.)

> Currently, we have some difficulties with larger decision variables. For
> example, if  the variables of a maximisation problem (max flow) are
> limited by values above 1e9, the solution tends to be inexact.

> We still can use the solution as a basis for further processing but
> maybe we lack some lp (or glpk) basics to obtain exact values in a wider
> range.

> Does this sound like a common newbie error? Which lp basics have we
> overlooked? Are there some common techniques to handle this? (e.g.
> scaling, increase precision of the simplex solver,...)

Please note that current implementation of the glpk simplex solver
is not sufficiently robust, and large bounds may cause serious numeric
difficulties.

If large bounds are used to indicate that corresponding arcs have
unlimited capacity, this is not a good idea; it is more correct to
remove such bounds at all. If not, and if you really expect that
some arc flows may reach their upper bounds, which are large, you
might consider scaling such flows.

On the other hand, max flow and min cost flow are pure network
problems having nice numeric properties. Does your model have only
flow conservation constraints? If not, which additional constraints
it has?

(I also would like to note that the general simplex method implemented
in glpk is much slower in solving network problems than specific network
optimization algorithms.)

> P.S.: We are using the glpk API to create the problem and to run the
> simplex method. Therefore, I omitted mathprog code.

Could you write your model in mps or cplex format, gzip it, and post
it to me (up to 10 Mb is ok)? I mean the instance, for which you
obtained inexact results.

Andrew Makhorin