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