[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [Help-glpk] Network problems: remap columns to arcs

From: Andrew Makhorin
Subject: Re: [Help-glpk] Network problems: remap columns to arcs
Date: Wed, 5 Aug 2009 02:06:40 +0400

> GLPK 4.39 provides the possibility to model networks and solve maximum
> network flow problems.

> Function glp_maxflow_lp() is provided to convert the network flow problem to
> a LP which can
> be solved using the simplex algorithm.

> After the problem is solved it is necessary to map the column values back to
> the arcs of the
> network to be able to output the result.

> How can the columns be reliably mapped back to arcs? Using the column labels
> created with
> sprintf(name, "x[%d,%d]", a->tail->i, a->head->i);
> seems quite awkward.

> I propose glp_maxflow_lp should return a mapping table.

All glpk network api routines use a natural ordering of arcs, which
can be explained as follows:

glp_arc *a;
int i, j;

j = 0;
for (i = 1; i <= G->nv; i++)
{  for (a = G->v[i]->out; a != NULL; a = a->t_next)
   {  j++;
      /* arc a corresponds to column j */

reply via email to

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