Decomposition method for a class of transport-type problems with a quadratic objective function
- Authors: Leonov V.Y.1,2, Tizik A.P.1,2, Torchinskaya E.V.1,2, Tsurkov V.I.1,2
-
Affiliations:
- Computer Science and Control Federal Research Center
- Moscow Institute of Physics and Technology
- Issue: Vol 56, No 5 (2017)
- Pages: 796-802
- Section: Systems Analysis and Operations Research
- URL: https://journals.rcsi.science/1064-2307/article/view/219970
- DOI: https://doi.org/10.1134/S1064230717050069
- ID: 219970
Cite item
Abstract
A class of transport problems with a quadratic criterion without any restrictions on the sign of unknown variables is considered. An iterative algorithm based on the consecutive modification of the coefficients of the objective function is used. The problem is reduced to successively solving pairs of problems from various groups of restrictions. These problems have one connecting variable and are solved analytically by the method of Lagrange multipliers. If the negative components appear in the course of solving them, the problem with one or several restrictions from one group and all restrictions from the other group is considered. These problems can also be easily solved for large dimensions, and in this way the dimension is reduced.
About the authors
V. Yu. Leonov
Computer Science and Control Federal Research Center; Moscow Institute of Physics and Technology
Email: tsur@ccas.ru
Russian Federation, Moscow, 119333; Dolgoprudny, Moscow oblast, 141701
A. P. Tizik
Computer Science and Control Federal Research Center; Moscow Institute of Physics and Technology
Email: tsur@ccas.ru
Russian Federation, Moscow, 119333; Dolgoprudny, Moscow oblast, 141701
E. V. Torchinskaya
Computer Science and Control Federal Research Center; Moscow Institute of Physics and Technology
Email: tsur@ccas.ru
Russian Federation, Moscow, 119333; Dolgoprudny, Moscow oblast, 141701
V. I. Tsurkov
Computer Science and Control Federal Research Center; Moscow Institute of Physics and Technology
Author for correspondence.
Email: tsur@ccas.ru
Russian Federation, Moscow, 119333; Dolgoprudny, Moscow oblast, 141701