
Accession Number : AD0715620
Title : An Algorithm to Find Minimum Cost Flow in a Network.
Descriptive Note : Research rept.,
Corporate Author : CALIFORNIA UNIV BERKELEY OPERATIONS RESEARCH CENTER
Personal Author(s) : Fillet,A. ; Giraud,P. ; Sakarovitch,M.
Report Date : NOV 1970
Pagination or Media Count : 19
Abstract : The paper describes an algorithm to find a flow of minimum cost in a network and a computer program which performs this algorithm. The principle of the algorithm is the following: At each iteration distances, which depend on the current flow, are defined on each arc and then a circuit of negative length is looked for. If such a circuit exists, more flow is pushed into it and a 'better' flow is found; if no such circuit exists, current flow is optimal. What might make this algorithm efficient is the fact that the information which has been gathered at some iteration to find a negative circuit will be used to find a negative circuit at next iteration so that each iteration requires a relatively small amount of work. (Author)
Descriptors : (*OPERATIONS RESEARCH, FLOW CHARTING), CONVEX SETS, ITERATIONS, OPTIMIZATION, COMPUTER PROGRAMMING, GRAPHICS
Subject Categories : Operations Research
Distribution Statement : APPROVED FOR PUBLIC RELEASE