Abstract
The feasibility problem of multicommodity flow is reduced to finding out if a multidimensional vector determined by the network parameters belongs to a convex polyhedral cone determined by the set of paths in the network. It is shown that this representation of the feasibility problem makes it possible to formulate the feasibility criterion described in [1] in a different form. It is proved that this criterion is sufficient. The concepts of reference vectors and networks are defined, and they are used to describe a method for solving the feasibility problem for an arbitrary network represented by a complete graph.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
A. B. Papernov, “Realizability of multicommodity flows,” in Discrete Optimization Studies (Nauka, Moscow, 1976), pp. 230–261 [in Russian].
L. R. Ford and D. R. Fulkerson, Flows in Networks (Princeton Univ. Press, Princeton, 1962; Mir, Moscow, 1966).
T. C. Hu, Integer Programming and Network Flows (Addison–Wesley, Reading, Mass., 1970; Mir, Moscow, 1974).
M. V. Lomonosov, “On system of flows in a network,” Probl. Inf. Transm. 14 (4), 280–290 (1978).
B. N. Pshenichyi, Convex Analysis and Extremum Value Problems (Nauka, Moscow, 1980) [in Russian].
M. R. Davidson, Yu. E. Malashenko, N. M. Novikova, M. M. Smirnov, and G. V. Strogaya, Mathematical Statements of Problems of Recovery and Survivability for Multicommodity Networks (Vychisl. Tsentr, Ross. Akad. Nauk, Moscow, 1993) [in Russian].
M. R. Davidson, “Stability of the lexicographic maximin problem of distributing flows in multicommodity networks,” Zh. Vychisl. Mat. Mat. Fiz. 35, 334–351 (1995).
Yu. E. Malashenko and N. M. Novikova, “Superconcurrent distribution of flows in multicommodity networks,” Discretn. Anal. Issled. Oper. 4 (2), 34–54 (1997).
A. Schrijver, Theory of Linear and Integer Programming (Wiley, Chichester, 1986; Mir, Moscow, 1991).
Ya. R. Grinberg, “Step graphs and their application to the organization of commodity flows in networks,” J. Comput. Syst. Sci. Int. 55, 222–231 (2016).
Author information
Authors and Affiliations
Corresponding author
Additional information
Original Russian Text © Ya.R. Grinberg, 2018, published in Zhurnal Vychislitel’noi Matematiki i Matematicheskoi Fiziki, 2018, Vol. 58, No. 5, pp. 834–842.
Rights and permissions
About this article
Cite this article
Grinberg, Y.R. Methods of the Convex Cone Theory in the Feasibility Problem of Multicommodity Flow. Comput. Math. and Math. Phys. 58, 803–812 (2018). https://doi.org/10.1134/S096554251805010X
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1134/S096554251805010X