Interval extension of the Ford-Fulkerson algorithm for finding the maximum flow in a transport network and its software implementation at the DBMS level

The initial data in many practical problems are known by their nature only approximately or can vary within certain limits. The use of interval-valued data allows one to take into account the existing uncertainty when modeling systems using such values. The article is devoted to the development and implementation of the interval extension of the Ford-Fulkerson algorithm for solving the maximum flow problem under conditions of uncertainty of the initial data. Unlike the classical approach where the edge capacities are specified by scalar values the proposed solution uses interval data which allows for more accurate modeling of real systems with parameters known only with a certain accuracy. The algorithm implementation is presented based on the PostgreSQL relational database management system with the creation of a user-defined data type for working with interval data. The paper describes the mathematical foundations of interval arithmetic, methods for comparing interval values, and features of integrating the algorithm with a database management system. The results of a computational experiment on a test example are presented. Practical aspects of the method application in problems of transport planning, telecommunication network management, and resource allocation are discussed.

1. Cormen Th.H., Leiserson Ch.E., Rivest R.L., Stein C. Introduction to Algorithms. Cambridge: MIT Press; 2022. 1332 p.

2. Sharyi S.P. Konechnomernyi interval'nyi analiz. Novosibirsk: XYZ; 2025. 671 p. (In Russ.).

3. Allahviranloo T., Pedrycz W., Esfandiari A. Advances in Numerical Analysis Emphasizing Interval Data. Boca Raton: CRC Press; 2022. 218 p. https://doi.org/10.1201/9781003218173

4. Ahuja R.K., Magnanti Th.L., Orlin J.B. Network Flows: Theory, Algorithms, and Applications. New Jersey: Prentice Hall; 1993. 846 p.

5. Korte B., Vygen J. Combinatorial Optimization: Theory and Algorithms. Berlin, Heidelberg: Springer; 2012. 660 p. https://doi.org/10.1007/978-3-642-24488-9

6. Ding S. The α-Maximum Flow Model with Uncertain Capacities. Applied Mathematical Modelling. 2015;39(7):2056–2063. http://doi.org/10.1016/j.apm.2014.10.021

7. Liu B. Theory and Practice of Uncertain Programming. Berlin, Heidelberg: Springer; 2009. 202 p. https://doi.org/10.1007/978-3-540-89484-1

8. Hansen E., Walster G.W. Global Optimization Using Interval Analysis. New York: Marcel Dekker; 2004. 489 p.

9. Mayer G. Interval Analysis and Automatic Result Verification. Berlin, Boston: Walter de Gruyter GmbH; 2017. 532 p.

10. Sakr Sh. Storing and Querying Graph Data Using Efficient Relational Processing Techniques. In: Information Systems: Modeling, Development, and Integration: Third International United Information Systems Conference: Volume 20, 21–24 April 2009, Sydney, Australia. Berlin, Heidelberg: Springer; 2009. P. 379–392. http://doi.org/10.1007/978-3-642-01112-2_39

11. Angles R., Gutierrez C. Survey of Graph Database Models. ACM Computing Surveys. 2008;40(1). https://doi.org/10.1145/1322432.1322433

12. Pogodaev A.K., Galkin A.V., Saraev P.V., Miroshnikov A.I. Interval Data Type Comparison in MS SQL Server. Sistemy upravleniya i informatsionnye tekhnologii. 2018;(1):68–72. (In Russ.).

13. Pogodaev A.K., Galkin A., Saraev P., Miroshnikov A.I. The Development of Interval Data Type for Analytical Information Processing. In: Recent Developments and the New Direction in Soft-Computing Foundations and Applications: Selected Papers from the 7th World Conference on Soft Computing, 29–31 May 2018, Baku, Azerbaijan. Cham: Springer; 2021. P. 509–520. https://doi.org/10.1007/978-3-030-47124-8_41