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

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.

Keywords: linear programming, minimum cost flow problem, network optimization
$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% /
   a(n,n) 'arcs'
   nn(n)
   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
$ifE errorLevel<>0 $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
$ifE errorLevel<>0 $abort 'Problems with gngfile'

Variable
   x(n,n) 'flow'
   z      'objective';

Positive Variable x;

Equation
   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.*';