Submodular functions in economics and logistics

Authors

  • Anna A. Koroleva Belarusian State University, 4 Niezaliežnasci Avenue, Minsk 220030, Belarus

Keywords:

submodular functions, discrete convexity, network transport problem

Abstract

In modern economic research, sections of special well-solved problems related to submodular functions are distinguished. Applications with submodular functions arise in various areas of economics - utility theory, game theory and logistics. The article analyses the role of submodular functions in the economy, and then introduces a wide class of transport optimisation problems, the constraints and criteria in which are modeled by submodular functions, the properties of these problems are investigated, which allows us to build effective algorithms for constructing optimal transportation in transport networks with a supermodular objective function and submodular constraints.

Author Biography

  • Anna A. Koroleva, Belarusian State University, 4 Niezaliežnasci Avenue, Minsk 220030, Belarus

    PhD (physics and mathematics), docent; dean of the faculty of economics

References

  1. Cherenin VP, Petrov AP. [Improvement of the method of drawing up a plan for the formation of trains]. Zheleznodorozhnyi transport. 1948;3:60–71. Russian.
  2. Cherenin VP. [Mechanisation calculations to plan the formation of trains]. Tekhnika zheleznykh dorog. 1954;1:79–96. Russian.
  3. Cherenin VP. Reshenie nekotorykh kombinatornykh zadach optimal’nogo planirovaniya metodom posledovatel’nykh raschetov [Solving some combinatorial problems of optimal planning by the method of successive calculations]. Novosibirsk: [s. n.]; 1962. 21 p. (Materialy k Konferentsii po opytu i perspektivam primeneniya matematicheskikh metodov i elektronnykh vychislitel’nykh mashin v planirovanii). Russian.
  4. Khachaturov VR. Nekotorye voprosy i prilozheniya metoda posledovatel’nykh raschetov k resheniyu zadach razmeshcheniya proizvodstva [Some questions and applications of the method of sequential calculations to solving problems of production placement] [dissertation]. Moscow: Tsentral’nyi ekonomiko-matematicheskii institut Akademii nauk SSSR; 1968. 164 p. Russian.
  5. Edmonds J. Submodular functions, matroids and certain polyhedra. In: Guy R, Hanani H, Sauer N, Schӧnheim J, editors. Combinatorial structures and their applications. Proceedings of the Calgary International conference; 1969 June 2–14; Calgary, Alberta, Canada. New York: Gordon and Breach; 1970. p. 69–87.
  6. Topkis DM. Minimizing a submodular functions on a lattice. Operations Research. 1978;26(2):305–321. DOI: 10.1287/opre.26.2.305.
  7. Fujishige S. Submodular systems and related topics. In: Korte B, Ritter K, editors. Mathematical Programming at Oberwolfach II. Berlin: Springer-Verlag; 1984. p. 113–131 (Mathematical programming studies; volume 22).
  8. Fujishige S. Submodular functions and optimization. 2nd edition. Amsterdam: Elsevier; 2005. 410 p. (Annals of discrete mathe­matics; volume 58).
  9. Topkis DM. Supermodularity and complementarity. Princeton: Princeton University Press; 1998. 272 p. (Frontiers of economic research).
  10. Lovasz L. Submodular functions and convexity. In: Bachem A, Grötschel M, Korte B, editors. Mathematical programming. The state of the art. Bonn, 1982. Berlin: Springer-Verlag; 1983. p. 235–257.
  11. Kovalev MM. Matroidy v diskretnoi optimizatsii [Matroids in discrete optimisation]. Minsk: Universitetskoe; 1987. 220 p. Russian.
  12. Russell C, Andrew J. Coordinating coordination failures in Keynesian models. The Quarterly Journal of Economics. 1988;103(3):441–463. DOI: 10.2307/1885539.
  13. Danilov VI. Lektsii po teorii igr [Lectures on the theory of games]. Moscow: New Economic School; 2002. 140 p. Russian.
  14. Chambers CP, Echenique F. Supermodularity and preferences. Journal of Economic Theory. 2009;144(3):1004–1014. DOI: 10.1016/j.jet.2008.06.004.
  15. Danilov VI, Koshevoi GA. [Economics with innovative goods]. Ekonomika i matematicheskie metody. 2009;45(1):44–55. Russian.
  16. Khachaturov VR. Algoritmy maksimizatsii supermodulyarnykh funktsii i ikh primenenie v zadachakh optimal’nogo raspredeleniya investitsii v regionakh [Algorithms for maximising supermodular functions and their application in problems of optimal investment distribution in regions] [dissertation]. Moscow: Tsentral’nyi ekonomiko-matematicheskii institut RAN; 2002. 95 p. Russian.
  17. Khachaturov VR. [Basic properties of cube lattices, algorithms for their construction and application possibilities in discrete optimisation]. Zhurnal vychislitel’noi matematiki i matematicheskoi fiziki. 2015;55(1):121–134. Russian. DOI: 10.7868/S004446691501010X.
  18. Montlevich VM. On the submodularity of the profit function in a problem of transport planning. Bulletin of Samara State University. Natural Science Series. 2014;10:48–54. Russian.
  19. Gasnikov AV, editor. Vvedenie v matematicheskoe modelirovanie transportnykh potokov [Introduction to mathematical modelling of transport flows]. 2nd edition. Moscow: Publishing House of the Moscow Center for Continuous Mathematical Education; 2013. 426 p. Russian.

Downloads

Published

2021-12-14

Issue

No. 2 (2021): Journal of the Belarusian State University. Economics

Section

C. Mathematical and Quantitative Methods

License

The authors who are published in this journal agree to the following:

  1. The authors retain copyright on the work and provide the journal with the right of first publication of the work on condition of license Creative Commons Attribution-NonCommercial. 4.0 International (CC BY-NC 4.0).
  2. The authors retain the right to enter into certain contractual agreements relating to the non-exclusive distribution of the published version of the work (e.g. post it on the institutional repository, publication in the book), with the reference to its original publication in this journal.
  3. The authors have the right to post their work on the Internet (e.g. on the institutional store or personal website) prior to and during the review process, conducted by the journal, as this may lead to a productive discussion and a large number of references to this work. (See The Effect of Open Access.)

How to Cite

[1]
Koroleva, A.A. 2021. Submodular functions in economics and logistics. Journal of the Belarusian State University. Economics. 2 (Dec. 2021), 18–25.