netgen.gms : Min Cost Flow with an Instance generated by NETGEN

Description

This problem finds a minimum cost flow in a network generated by
NETGEN and GNETGEN. An awk script converts the NETGEN format into GAMS
readable statements.

NETGEN and GNETGEN are available from NETLIB: http://www.netlib.org/lp/generators


References

  • Klingman, D, Napier, A, and Stutz, J, NETGEN: A program for generating large scale capacitated assignment, transportation, and minimum cost flow networks. Management Science 20 (1974), 814-820.
  • Clark, R H, Kennington, L, Meyer, R R, and Ramamurti, M, Generalized Networks: Parallel Algorithms and an Empirical Analysis. ORSA Journal on Computing 4, 2 (1992), 132-145.

Large Model of Type : LP


Category : GAMS Model library


Main file : netgen.gms   includes :  netgn099.inc  gnetgn99.inc

$Title  Min Cost Flow with an Instance generated by NETGEN and GNETGEN (NETGEN,SEQ=323)
$Ontext

This problem finds a minimum cost flow in a network generated by
NETGEN and GNETGEN. An awk script converts the NETGEN format into GAMS
readable statements.

NETGEN and GNETGEN are available from NETLIB: http://www.netlib.org/lp/generators


Klingman, D, Napier, A, and Stutz, J, NETGEN: A program for generating
large scale capacitated assignment, transportation, and minimum cost
flow networks. Management Science 20 (1974), 814-820.

Clark, R H, Kennington, L, Meyer, R R, and Ramamurti, M, Generalized
Networks: Parallel Algorithms and an Empirical Analysis. ORSA Journal
on Computing 4, 2 (1992), 132-145.

$Offtext


* The AWK scripts are modified versions of the ones for AMPL taken
* from the generator distributions

$onechoV > "%gams.scrdir%netgen2gms.%gams.scrext%"
/^NETGEN PROBLEM/ {print "set n nodes /1*"$4"/;\n$ondelim"; next}
/^SUPPLY/         {print "parameter supply(n) /"; next}
/^ARCS/           {print "/;\ntable adata(n,n,*)\nn,n,cost,capacity"; next}
/^DEMAND/         {print ";\nparameter demand(n) /"; next}
/^END/            {print "/;\n"; exit}
/^[^ ]/           {next}
{print}
$offecho

$onechoV > "%gams.scrdir%gnetgen2gms.%gams.scrext%"
/^ PROBLEM/       {print "set n nodes /1*"$4"/;\n$ondelim"; next}
/^SUPPLY/         {print "parameter supply(n) /"; next}
/^ARCS/           {print "/;\ntable adata(n,n,*)\nn,n,cost,capacity,multiplier"; next}
/^DEMAND/         {print ";\nparameter demand(n) /"; next}
/^END/            {print "/;\n"; exit}
/^[^ ]/           {next}
{print substr($0,7,6), substr($0,13,6), substr($0,21,10),
       substr($0,31,10), substr($0,51,10)}
$offecho

$set maxnodes 50
set n nodes /1*%maxnodes%/, nn(n), a(n,n) arcs, hdr /cost,capacity,multiplier/;

Parameter adata(n,n,hdr), supply(n), demand(n);

$if not set ngfile $set ngfile netgn099.inc
$call awk -f "%gams.scrdir%netgen2gms.%gams.scrext%" %ngfile%  > ngfile.gms
$call gams ngfile lo=%gams.lo% gdx=ngfile
$if errorlevel 1 $abort 'Problems with ngfile'

$if not set gngfile $set gngfile gnetgn99.inc
$call awk -f "%gams.scrdir%gnetgen2gms.%gams.scrext%" %gngfile%  > gngfile.gms
$call gams gngfile lo=%gams.lo% gdx=gngfile
$if errorlevel 1 $abort 'Problems with gngfile'

Variables x(n,n)  flow
          z       objective;
Positive variable x;

Equations obj     objective
          net     flow conservation;

obj..     z =e= sum(a, adata(a,'cost')*x(a));

net(nn).. supply(nn) + sum(a(n,nn), adata(a,'multiplier')*x(a)) =e= sum(a(nn,n), x(a)) + demand(nn);

model mincostflow /all/;

* Solve the NETGEN problem
execute_load 'ngfile', nn=n, supply, adata, demand;
a(n,nn)               = adata(n,nn,'capacity');
adata(a,'multiplier') = 1;
x.up(a)               = adata(a,'capacity');

solve mincostflow using lp minimizing z;

* Solve the GNETGEN problem
execute_load 'gngfile', nn=n, supply, adata, demand;
a(n,nn) = adata(n,nn,'capacity');
x.up(a) = adata(a,'capacity');

solve mincostflow using lp minimizing z;

* Clean up temporary files
execute 'rm -f gngfile.* ngfile.*';