home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #16 / NN_1992_16.iso / spool / sci / math / numanal / 2312 < prev    next >
Encoding:
Text File  |  1992-07-27  |  2.0 KB  |  63 lines
  1. Newsgroups: sci.math.num-analysis
  2. Path: sparky!uunet!munnari.oz.au!bruce.cs.monash.edu.au!monu6!mukluk!kurtles
  3. From: kurtles@momth3.maths.monash.edu.au (Mr K.A. Brinschwitz)
  4. Subject:  REQUEST:General network solver
  5. Message-ID: <1992Jul28.075549.12213@monu6.cc.monash.edu.au>
  6. Keywords: General networks; Optimization
  7. Sender: news@monu6.cc.monash.edu.au (Usenet system)
  8. Organization: Monash University
  9. Date: Tue, 28 Jul 1992 07:55:49 GMT
  10. Lines: 51
  11.  
  12.     I am interested in obtaining either C or FORTRAN coding for
  13. a generalized network solver. The particular problem of interest is 
  14. this:
  15.     Consider a directed graph with set of nodes, N, and  a set of arcs, ARCS.
  16. Each arc, (i,j), has a scalar associated with it, Aij   , the COST of (i,j).
  17. Let Fij  denote the FLOW on arc (i,j). There are upper and lower bounds on Fij,
  18. Cij and Lij respectively.
  19.  
  20. With each arc (i,j),  there is an associated scalar Kij, the GAIN of arc (i,j).
  21.  
  22. The problem:
  23.                  _
  24.       minimize   > Aij Fij
  25.                  -
  26.          (i,j) element of ARCS
  27.  
  28.  
  29. subject to
  30.  
  31.          (Conservation of flow)
  32.           _                               _
  33.           >  Kmi  Fmi          -          >  Fim          =  0    (For All i in N)
  34.           -                               -
  35.           m                               m
  36.    (m,i) element of ARCS        (i,m) element of ARCS
  37.  
  38.        
  39.           (capacity constraints)
  40.  
  41.           Lij <=  Fij   <=  Cij        (for all (i,j) in the set ARCS)       
  42.  
  43. ------------------------------------------------------------------------------------
  44.  
  45. I am interested in obtaining a network solver that handles the above for 
  46. cases with  Kij not always unity (ie networks with gains and losses.)
  47.  
  48. I already have a paper by Bertsekas and Tseng (OPERATIONS RESEARCH, VOL36 No 1
  49. 1988),  in which an algorithm is formulated for solving a network with Gains.
  50. Does anyone know if the algorithm has been coded ? I know that they have already 
  51. coded a solver for a zero-gain network.
  52.  
  53. Any help gratefully recieved.
  54.  
  55. Kurt Brinschwitz.
  56.  
  57.  
  58.  
  59.  
  60.  
  61.  
  62.  
  63.