Premium
A continuous‐time network simplex algorithm
Author(s) -
Anderson E. J.,
Philpott A. B.
Publication year - 1989
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230190403
Subject(s) - minimum cost flow problem , flow network , simplex algorithm , maximum flow problem , computer science , mathematical optimization , algorithm , out of kilter algorithm , simplex , node (physics) , linear programming , multi commodity flow problem , time complexity , flow (mathematics) , constraint (computer aided design) , upper and lower bounds , mathematics , theoretical computer science , graph , dijkstra's algorithm , shortest path problem , combinatorics , mathematical analysis , geometry , structural engineering , engineering
Given a network having costs and upper bound constraints on the flows in its arcs, the minimum‐cost network flow problem is that of finding flows which satisfy a flow‐conservation constraint at each node and minimize the total cost of the flow. If the arc capacities vary as functions of time, and storage is permitted at the nodes of the network, then the problem becomes an infinitedimensional linear program with a network structure. We describe an algorithm to solve such problems. This algorithm is a continuuous‐time version of the network simplex algorithm.