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