> 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 _______________________________________________ Help-glpk mailing list [email protected] http://lists.gnu.org/mailman/listinfo/help-glpk
