Development of Operations Research in the Soviet Union
Sciences in the Soviet system had their struggles, but benefited from strong government support for physics and mathematics, advanced mathematical education in high schools and cheap textbooks. However, lack of visits abroad, high levels of secrecy for publications and a hierarchical structure of bureaucracy hindered scientists. The period 1955–1970 was the least oppressive: it was a “golden age” of Soviet mathematics which was reflected in the strong mathematical breakthroughs conducted by Soviet mathematicians.
In contrast to the vast collection of research communities in the USA, where research was spread over many universities and some government and industrial research institutes, research in the USSR on topics such as mathematical programming was concentrated in a few scientific centers in Moscow, Kiev, Novosibirsk, and Leningrad (now, St. Petersburg). Notable institutes included:
Moscow: Moscow State University (Girsanov, Tikhomirov, Polyak, Vasiliev),
Yudin's Laboratory (Yudin, Golstein, later Ioffe, Nemirovski),
Central Economical - Mathematical Institute (Golstein, later Skokov, Tretyakov, Nesterov),
Computer Center of the Academy of Sciences (Moiseev, Evtushenko, later Khachiyan,
Antipin), and other institutes led by Dubovitskii, Miljutin.
Kiev: Glushkov Institute of Cybernetics (Ermoliev, Pshenichnyi, Shor, Mikhalevich, Nurminskii), and
other institutes led by Zukhovitskii, R.Polyak, and Primak.
Novosibirsk: Institute of Mathematics (Kantorovich, Rubinstein, Dikin, Bulavskii, Rubinov, Kaplan).
Leningrad: Leningrad State University (Demyanov, Romanovskii, Vershik).
Kharkov: (Ljubich, Majstrovskii).
Sverdlovsk: (Eremin).
Irkutsk: (Bulatov, later Dikin).
Minsk: (Gabasov, Kirillova, later Mordukhovich).
Voronezh: (Krasnoselskii, Levin).
Before the 20th century, the most famous names are those of Euler, Chebyshev, Markov, and Lyapunov, all of whom spent most of their adult life in St. Petersburg. Euler popularized many notational conventions used thereafter, such as e, π, i, Σ, and f(x). In 1930, A.N. Tolstoi, of the Commissariat of Transportation in Moscow, studied transportation problems and identified some necessary conditions for optimality. For a problem based on the Soviet rail system with 155 edges, Tolstoi found an optimal solution. At the beginning of the 20th century, Leonid Kantorovich was in the forefront of mathematical optimization. Kantorovich’s main contributions in optimization include the following discoveries: linear programming (1939), general conditions of optimality (1940), and several functional analysis techniques (1939–1948). In 1939, Kantorovich published the book Mathematical Methods for Production Organization and Planning which first introduced linear programming; however, this received little attention even in the Soviet Union. In 1948, Kantorovich published a survey which showed convergence of the steepest descent method, and the Newton method. Kantorovich won numerous awards in his lifetime, the most notable of which were the Stalin Prize (1949), Lenin Prize (1965) and the Nobel Prize (1975).
In 1955, Rubinstein, a former student of Kantorovich, published the first rigorous mathematical formulation of linear programming problems and their analysis in Russian. The results of Western scientists (G. Dantzig, H. Kuhn, A. Tucker, D. Gale, and others) on linear programming became known in the Soviet Union during this period. Hence, translations of the original works into Russian were conducted as well; the first one appeared in 1959 of the work of Kuhn and Tucker. The first publication on matrix games were by Vorobjev and Ventzel in 1959, while the first Russian textbook on linear programming was written by Yudin and Golstein in 1961.
In 1956, Pontryagin, provided a new formulation of the optimal control problem and obtained a new necessary condition for optimality, the so-called maximum principle. In the 1960s, the main directions were as follows: towards the general theory of extremum problems with contributions from Goldstein, Pshenichnyj and Kantorovich; and, non-smooth optimization with contributions from Shor, Ermoliev, and Polyak. Shor proposed the subgradient method in 1964, which is still widely used. Ermoliev also provided contributions towards stochastic optimization; however, there was not much activity in the direction of stochastic programming as known in the western world except for a textbook by Yudin in 1979.
From the beginning of the 1960s, a significant amount of research activity in optimization was related to the Mathematical Department of the Moscow State University (A. Ioffe, V. Tikhomirov, I. Girsanov). It was concentrated on studying nontrivial infinite dimensional optimization problems and convenient frameworks for deriving optimality conditions. At the same time, a new impulse for development of the optimization methods and the models of operations research was started by A. Tikhonov in 1970 by creating a new department of Computational Mathematics and Cybernetics in the Moscow State University. A new chair of Operations Research was headed there by Y. Germeyer, a well-known specialist in reliability and game theory. The scope of the research in this group was extended to repeated minimax problems (V. Fedorov), mathematical economics (S. Ashmanov), and Optimization (V. Karmanov and F. Vasilyev). The later research direction was quite pioneering because of the presence of the first global efficiency bounds for convex optimization, even at the level of graduate courses.
Between 1976 and 1979, Nemirovski and Yudin introduced the new notion of complexity of optimization problems, with later contributions by Nesterov and Khachiyan. In 1979, Khachiyan proved the polynomial complexity of solving a linear program, ending the open question of whether linear programs are NP-hard or not. Nesterov and Nemirovski later developed semidefinite programming as well. Further, B. Polyak’s main findings in optimization theory, motivated by the engineering applications and problems of control theory, were presented in his now famous book, Introduction to Optimization, in 1983. During this time, another O.R. research effort was growing in Leningrad. The main topics there were game theory (N. Vorobyev) and the theory of minimax (V. Demyanov). The latter direction remained active into the 21st century, concentrating mainly on studying the differences of non-differentiable convex functions (DC programming).
The Soviet military relied heavily on operations research. The journal Military Thought was the restricted journal of the Soviet General Staff. In the early 1970s, mathematical models were widely accepted and also encouraged. The main drivers of interest were planning and budgeting. Here fields such as stochastic optimization, dynamic programming, integer programming, queuing theory, probability and statistics were all used.
Probability and statistics are heavily indebted to Soviet mathematicians as well. The earliest names are again those of Markov, Chebyshev, and Bernstein. Later, Luzin and his chain of students developed seminal contributions. Perhaps, the most famous Soviet probabilist was A. Kolmogorov, another student of Luzin. Kolmogorov received a variety of prestigious prizes in his lifetime: the title Hero of Socialist Work in 1963, seven Orders of Lenin, the Order of the October Revolution, and the Order of the Red Banner of Labor, the Lenin Prize in 1965 for his work on classical mechanics (with V.I. Arnold), the State prize in 1941 for work on the theory of probability (with A. Khinchin), the Chebyshev prize (with B. Gnedenko) in 1951 and the Lobachevskii prize in 1986
A. Khinchin, a student of Luzin, promoted queueing theory for the first time in the Soviet Union. In the early 1930s, Khinchin introduced and studied probabilistic models for maintenance of machines in a textile factory serviced by a group of repairmen. He published a book on queuing in 1963 based on Scandinavian materials on tele-traffic; later, queueing theory was expanded by V. Ivnitskii. The Russian term for “queueing theory” was initially “mass service theory”. In the 1970s, analysis of air defenses was also studied using queueing theory. Khinchin was awarded the Stalin Prize in 1941. For many decades, B.V. Gnedenko played informally the role of the leader of the Soviet school in queueing theory, and there were many strong research groups across the USSR, both in theoretical and applied queueing theory, and, in particular, those led by A.A. Borovkov (Novosibirsk), G.P. Basharin (Moscow), I.N. Kovalenko and V.S. Korolyuk (Kiev).
This article is largely compiled from a survey article by Boris Polyak: “History of mathematical programming in the USSR: analyzing the phenomenon”, Mathematical Programming, 91, (2002): 401-416. The material on Tolstoi is based on an article by Alexander Schrijver: “On the history of the transportation and maximum flow problems”, Mathematical Programming, Ser. B 91, (2002) : 437–445.
Compiled by: Bismark Singh
Acknowledgements to: Sergey Foss, Yurii Nesterov, Oleg Prokopyev, Sergey Sevastyanov
Edited by: Mark Eisner, Linus Schrage