January, 2006
This subdirectory contains the following Fortran source codes:
erelaxg.f This implements the epsilon-relaxation method for solving
separable convex cost network flow with gains. [The cost function
and its derivative are called through subroutines.]
asspg.f This implements the auction/shortest-path version of the
epsilon-relaxation method for solving
separable convex cost network flow with gains. [The cost function
and its derivative are called through subroutines.]
erelax.f This implements the epsilon-relaxation method for solving
ordinary separable convex QUADRATIC cost network flow (gains=1).
and the following Fortran subroutines
cost_ent.f This subroutine gives the function value, the derivative
value, and the derivative inverse value for a linear
cost function or an entropy cost function.
cost_inv.f This subroutine gives the function value, the derivative
value, and the derivative inverse value for a linear
cost function or an inverse cost function.
cost_pipe.f This subroutine gives the function value, the derivative
value, and the derivative inverse value for a linear
cost function or a pipe network cost function.
cost_quad.f This subroutine gives the function value, the derivative
value, and the derivative inverse value for a linear
cost function or a quadratic cost function.
dcinv.f This subroutine computes an approximate inverse of
the derivative function specified in any of the previous
four subroutines.
and the following ascii files:
NL013.DAT This is a sample input file for erelaxg and asspg that
contains a 10-node, 20-arc generalized network flow problem
Implementation and numerical experience with the codes erelaxg and asspg are described
in the paper:
Francesca Guerriero and Paul Tseng,
"Implementation and Testing of Auction Methods for Solving
Separable Convex Cost Generalized Network Flow Problems",
J. Optim. Theory Appl., vol. 115, 2002, 113-144.
These codes were last updated on March 24, 2005 to correct a small bug in setting the
termination threshold, among others.
Implementation and numerical experience with the code erelax is described in the paper:
D.P. Bertsekas, L.C. Polymenakos, and P. Tseng,
"Epsilon-Relaxation Method for Separable Convex
Cost Network Flow Problems", SIAM Journal on Optimization, Vol. 7 (1997), 853--870.
The Fortran source codes were written to run and report CPU time on
a Unix machine but they should
run on other machines with minor modifications as they conform to
the FORTRAN77 standard. I welcome questions/comments/suggestions
about the codes.
Paul Tseng (206) 543-1177, tseng@math.washington.edu
-----------------------------------------------------------------------
Instructions for compiling and running the codes on a Unix machine
(some modifications to the instructions may be necessary for non-Unix machine):
To run the epsilon-relaxation method to solve linear/quadratic cost generalized
network flow problems, do the following:
1. Compile erelaxg.f, cost_quad.f to create an executable.
For example, the unix command
f77 -O -o erelaxg erelaxg.f cost_quad.f
should create an executable named erelaxg
2. Create (in the same directory as the executable from Step 1)
ascii file NL013.DAT containing the problem data.
[The first line of NL013.DAT
should contain N (the number of nodes), NA (the number of arcs),
and NDAT (the number of data parameters); the
next NA lines should contain the starting node, ending node, linear cost
coeff, the NDAT parameters for nonlinear cost,
upper capacity (lower capacity is assumed to be zero), gain for each arc;
the last N lines should contain the supply for each node. See the
sample NL013.DAT file for reference.]
3. Run the executable.
To run the auction/shortest-path method, replace erelaxg.f by asspg.f
[For problems with gains near 1, but not equal to 1, we recommend using
asspg instead of erelaxg. On such problems, asspg can be hundreds of
times faster than erelaxg.]
To solve problems with linear/entropy cost, replace cost_quad.f by cost_ent.f
To solve problems with linear/inverse cost, replace cost_quad.f by cost_inv.f
To solve problems with linear/pipe network cost, replace cost_quad.f by cost_pipe.f
If derivative inverse of the cost function is not available, add dcinv.f
to the files being compiled.
To solve linear/quadratic cost ordinary network flow problems, either erelaxg or erelax can be used.
The code erelax is specialized to this class of problems and hence may be easier to use.
This code compiles by itself, e.g.,
f77 -O -o erelax erelax.f