×

zbMATH — the first resource for mathematics

A polynomial algorithm for minimum quadratic cost flow problems. (English) Zbl 0555.90039
Network flow problems with quaratic separable costs appear in a number of important applications such as approximating input-output matrices in economy, projecting and forecasting traffic matrices in telecommunication networks, or solving nondifferentiable cost flow problems by subgradient algorithms. Extending a scaling technique, used in the case of linear cost flows, to quadratic cost flows, a polynomial algorithm for this class of problems is given.
Reviewer: V.Peteanu

MSC:
90B10 Deterministic network models in operations research
90C20 Quadratic programming
68Q25 Analysis of algorithms and problem complexity
65K05 Numerical mathematical programming methods
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Allen, R.I.G.; Gossling, W.F., Estimating and projecting input-output coefficients, (1975), Input-output Publishing Company London
[2] Bacharach, M., Estimating nonnegative matrices from marginal data, International economic review, 6, 294-310, (1965) · Zbl 0136.14301
[3] Bachem, A.; Korte, B., Minimum norm problems over transportation polytopes, Linear algebra and its application, 31, 103-118, (1980) · Zbl 0435.90036
[4] Bland, R.G.; Goldfarb, D.; Todd, M.J., The ellipsoid method: A survey, Operations research, 29, 6, 1039-1091, (1981) · Zbl 0474.90056
[5] Bihain, A.; Strodiot, J.J.; Nguyen, V.H., A reduced subgradient method, (), to appear · Zbl 0624.90085
[6] Cantor, D.G.; Gerla, M., Optimal routing in a packet-switched computer network, IEEE transactions on computers, C-23, 10, 1062-1069, (1974) · Zbl 0291.90031
[7] Cottle, R.W.; Pang, J.S., On the convergence of a block successive overrelaxation method for a class of linear complementarity problems, () · Zbl 0478.90069
[8] Debiesse, J.L.; Matignon, G., Comparison of different methods for the calculation of traffic matrices, Annales des Télécommunications, 35, 91-102, (1980) · Zbl 0426.90030
[9] Dembo, R.S.; Klincewicz, A second order algorithm for network flow problems with convex separable costs, () · Zbl 0573.90083
[10] Edmonds, J.; Karp, R.M., Theoretical improvements in algorithmic efficiency for network flow problems, Journal of the ACM, 19, 2, 248-264, (1972) · Zbl 0318.90024
[11] Ferland, J.A., Minimum cost multicommodity circulation problems with convex are costs, Transportation science, 8, 4, 335-360, (1974)
[12] Ford, L.R.; Fulkerson, D.R., Flows in networks, (1962), Princeton University Press NY · Zbl 0139.13701
[13] Gondran, M.; Minoux, M., Graphes et algorithmes, (1979), Eyrolles France, English translation, Wiley, 1984 · Zbl 0497.05023
[14] Grötschel, M.; Lovász, L.; Schrijver, A., The ellipsoid method and its consequences in combinatorial optimization, Combinatorica, 1, 2, 169-197, (1981) · Zbl 0492.90056
[15] Helgason, R.; Kennington, J.; Lall, H., A polynomially bounded algorithm for a singly constrained quadratic program, Mathematical programming, 18, 338-343, (1980) · Zbl 0452.90054
[16] Hu, T.C., Minimum cost flows in convex cost networks, Naval research logistics quarterly, 13, 1, 1-9, (1966)
[17] Jaumard, B.; Minoux, M., Un algorithme de type pivots complémentaires pour LES problèmes de flots à coûts quadratiques séparables, (1982), CNET Issy, France, internal note
[18] Kennington, J.L.; Helgason, R.V., Algorithms for network programming, (1980), Wiley New York · Zbl 0502.90056
[19] Kennington, J.; Shalaby, M., An effective subgradient procedure for minimal cost multicommodity flow problems, Management science, 23, 994-1004, (1977) · Zbl 0366.90118
[20] Khachian, L.G., A polynomial algorithm in linear programming, Soviet mathematics. doklady, 20, 191-194, (1979) · Zbl 0409.90079
[21] Kozlov, M.K.; Tarasov, S.P.; Khachian, L.G., Polynomial solvability of convex quadratic programming, Soviet mathematics. doklady, 20, 1108-1111, (1979) · Zbl 0434.90071
[22] Lawler, E., Combinatorial optimization: networks and matroids, (1976), Holt, Rinehart and Winston New York · Zbl 0413.90040
[23] Leblanc, L.J.; Morluk, E.; Pierskalla, W., An efficient approach to solving the road network equilibrium traffic assignment problem, Transportation research, 9, 309-318, (1975)
[24] Lemke, C.E., A method of solution for quadratic programs, Management science, 8, 442-455, (1962) · Zbl 0995.90611
[25] Minoux, M., Un algorithme de sous-gradient pour l’extrapolation des matrices de trafic pour une norme quadratique, (1978), CNET Debiesse Matignon, cited in
[26] Minoux, M., Un algorithme polynomial pour LES problèmes de flots à coûts quadratiques et applications, (1982), CNET Issy, France, internal note of
[27] Minoux, M., ()
[28] Minoux, M., Solution explicite d’un problème de transport à coûts quadratiques et applications, (), July 1983
[29] Nguyen, S., An algorithm for the traffic assignment problem, Transportation science, 8, 203-216, (1974)
[30] Niven, I.; Zuckerman, H.S., An introduction to the theory of numbers, (1966), Wiley New York · Zbl 0186.36601
[31] Rockafellar, R.T., Convex analysis, (1970), Princeton Univeristy Press NY · Zbl 0229.90020
[32] Srinivasan, V.; Thompson, G.L., An operator theory of parametric programming for the transportation problem I and II, Naval research logistics quarterly, 19, 205-252, (1972) · Zbl 0269.90031
[33] Srinivasan, V.; Thompson, G.L., Cost operator algorithms for the transportation problem, Mathematical programming, 12, 372-391, (1977) · Zbl 0362.90058
[34] Wolfe, P., The simplex method for quadratic programming, Econometrica, 27, 3, 382-398, (1959) · Zbl 0103.37603
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.