×

Optimal control of network flows with convex cost and state constraints. (English) Zbl 1069.49507

Summary: Consider a network in which a commodity flows at a variable rate across the arcs in order to meet supply/demand at the nodes. The aim is to optimally control the rate of flow such that a convex objective functional is minimized. This is an optimal control problem with a large number of states, and with an even larger number of controls. It is also complicated by storage bounds at the nodes leading to two state constraints for each node. We show, under some mild assumptions on the problem’s parameters, that an exact solution to this state-constrained optimal control problem can be found efficiently without a complete discretization of the time variable, and develop a solution algorithm, based on the active-set-on-a-graph (ASG) algorithm for static convex flow problems. A brief description of a possible application as well as some numerical results are provided to illustrate the usefulness of the algorithm.

MSC:

49N90 Applications of optimal control and differential games
49M30 Other numerical methods in calculus of variations (MSC2010)
90C90 Applications of mathematical programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Anderson, Networks 19 pp 395– (1989) · Zbl 0672.90048 · doi:10.1002/net.3230190403
[2] A Unified Computational Approach to Optimal Control Problems. Longman Scientific and Technical: Harlow, Essex, 1991.
[3] Perold, SIAM Journal on Control and Optimization 19 pp 52– (1981) · Zbl 0488.49019 · doi:10.1137/0319005
[4] Separated continuous linear programs: theory and algorithms. Ph.D. Dissertation, Judge Institute of Management Studies, University of Cambridge, 1992.
[5] Zalmai, Journal of Mathematical Analysis and Applications 109 pp 426– (1985) · Zbl 0589.90069 · doi:10.1016/0022-247X(85)90160-X
[6] Boland, Applied Mathematics Letters 4 pp 61– (1991) · Zbl 0746.90017 · doi:10.1016/0893-9659(91)90056-2
[7] Boland, Journal of the Operational Research Society 42 pp 979– (1992) · Zbl 0768.90073 · doi:10.1057/jors.1992.149
[8] Boland, Applied Mathematics Letters 7 pp 23– (1994) · Zbl 0820.90039 · doi:10.1016/0893-9659(94)90066-3
[9] Jennings, Advances in Engineering Softwares 13 pp 190– (1991)
[10] Collins, Management Science 24 pp 747– (1978) · Zbl 0375.90069 · doi:10.1287/mnsc.24.7.747
[11] Applied Optimal Control: Optimization, Estimation, and Control (Revised edition). Wiley: New York, 1975.
[12] Theory of Extremal Problems. Elsevier North-Holland: New York, 1979.
[13] Flows in Networks. Princeton University Press: Princeton, 1962.
[14] Ernst, Journal of the Australian Mathematical Society, Series B 37 pp 530– (1996) · Zbl 0852.90071 · doi:10.1017/S0334270000010857
[15] Network Flows and Monotropic Optimization. Wiley-Interscience: New York, 1984. · Zbl 0596.90055
[16] Solution of linear systems of equations: iterative methods. Sparse Matrix Techniques, Lecture Notes in Mathematics, Springer: New York, 1977; 1-51.
[17] Klincewicz, Networks 13 pp 427– (1983) · Zbl 0518.90016 · doi:10.1002/net.3230130310
[18] Goldfarb, Mathematical Programming 27 pp 1– (1983) · Zbl 0537.90081 · doi:10.1007/BF02591962
[19] Active set methods for convex network and monotropic programs, unpublished Ph.D. thesis, Department of Mathematics, The University of Western Australia, 1995.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.