Re: [Help-glpk] graph objects and proposed network solver

[Andrew Makhorin]

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