UDC 519.85
1 V.M. Glushkov Institute of Cybernetics, National Academy of Sciences of Ukraine, Kyiv, Ukraine
 krainaz@ukr.net
|
2 Limnological Institute of the Siberian Branch of Russian Academy of Sciences, Irkutsk, Russia
zork@isem.irk.ru
|
INTERIOR POINT ALGORITHMS: HISTORY, RESEARCH RESULTS, APPLICATIONS,
AND PROSPECTS
Abstract. A family of interior point algorithms for solving linear programming problems is considered.
The results of their theoretical substantiation are given. Subsets of algorithms that have a linear, asymptotically
independent of the parameters of the problem being solved rate of convergence, and a subset of algorithms
that lead to relatively internal points of the set of optimal solutions are identified.
The history of the creation and development of algorithms is described.
New modifications of interior point algorithms are presented, which contain as a special case the previously developed algorithms.
Keywords: linear programming, linear inequalities, interior point algorithms.
FULL TEXT
REFERENCES
- Shor N.Z. Monotone modifications of r-algorithms and their applications. Kibernetika i sistemnyj analiz. 2002. N 6. P. 74–96.
- Sergienko I.V., Stetsyuk P.I. About three scientific ideas of N.Z. Shora. Kibernetika i sistemnyj analiz. 2012. N 1. P. 4–10.
- Stetsyuk P.I., Fesyuk A.V., Khomyak O.N. Generalized ellipsoid method. Kibernetika i sistemnyj analiz. 2018. Vol. 54, N 4. P. 70–80.
- Stetsyuk P.I. r-algorithms and ellipsoids. Kibernetika i sistemnyj analiz. 1996. N 1. P. 113–134.
- Dikin I.I., Zorkaltsev V.I. Iterative solution of mathematical programming problems: algorithms of the interior point method [in Russian]. Novosibirsk: Nauka, 1980. 144 p.
- Zorkaltsev V.I., Perzhabinsky S.M., Stetsyuk P.I. Search for normal solutions to SLAEs under bilateral constraints on variables by the interior points method. Kibernetika i sistemnyj analiz. 2015. Vol. 51, N 6. P. 71–80.
- Epifanov S.P., Zorkaltsev V.I. Flow distribution problem with non-fixed selections. Kibernetika i sistemnyj analiz. 2011. N 1. P. 81–92.
