Hi Robbie, > I am extrapolating a little here .. and may well have > got this very wrong .. !
> First there was mention of a flow network solver earlier > this year. And just recently, some discussion on a > network syntax for the mathprog language. > Therefore ... I was just wondering ... I guess the > current GLPK problem object be compatible with the > planned network solver. But will there be support for > a higher level abstraction dealing with graphs and > edges and such? And if so, will the two problem > objects be interchangeable and/or convertible? > The reason I ask is that I am currently considering > updating/improving my GLPK solver interface class and > that provoked some thoughts as to how the GLPK API > might evolve to cope better with networks. Flow network problems are particular case of lp, and I see no need to introduce into the glpk problem object components of new types like nodes and arcs; they can be naturally modeled through equality constraints (nodes) and non-negative variables (arc flows). The lp solver could be smart enough to recognize, for example, the minimum cost flow problem to solve it with a specialized algorithm. On the other hand, it seems to me reasonable to include in glpk some graph and network algorithms (for example, Dijkstra's algorithm to find shortest paths or Tarjan's algorithm to find strongly connected components), because corresponding problems are naturally arise in many lp and mip applications. The only issue is representation of graphs and networks. I considered some variants, in particular, the data structures developed by Don Knuth in the Stanford GraphBase, which look very appropriate. On the other hand, I think there should be at least two levels: a low level, on which no particular program object is used, and the graph or network is represented traditionally by some plain arrays, and api level, on which the graph/network is represented as an opaque object like glp_prob. Andrew Makhorin _______________________________________________ Help-glpk mailing list [email protected] http://lists.gnu.org/mailman/listinfo/help-glpk
