A numerical method for solving quadratic integer programming problem

• Published in: Bulletin of the South Ural State University. Series "Mathematical Modelling, Programming and Computer Software"
• Main Authors: Tat’yankin, V.M., Shitselov, A.V., Татьянкин, В.М., Шицелов, А.В.
• Format: Article in Journal/Newspaper
• Language: English
• Published: Издательский центр ЮУрГУ 2019
• Subjects: УДК 519.854.3; nonlinear programming; integer programming; numerical method; optimization; нелинейное программирование; целочисленное программирование; численный метод; оптимизация; khanty
• Online Access: http://dspace.susu.ru/xmlui/handle/0001.74/40270; https://doi.org/10.14529/mmp190311

V.M. Tat’yankin1, A.V. Shitselov1 1Yugra State University, Khanty-Mansiysk, Russian Federation E-mails: [e-mail], [e-mail] Виталий Михайлович Татьянкин, кандидат технических наук, доцент, Югорский государственный университет (г. Ханты-Мансийск, Российская Федерация), [e-mail]. Анатолий Вячеславович Шицелов, преподаватель, Югорский государственный университет (г. Ханты-Мансийск, Российская Федерация), [e-mail]. We propose a new numerical method for solving quadratic integer programming problem. The algorithm is based on a special representation of a minimizer of the corresponding objective functional. The problem can be reduced to a special box-constrained integer least squares problem. The advantage of the proposed algorithm is a good computational performance (approximately O(n • ln(n)) operations) shown in numerical experiments, where the number of unknowns n can be up to 108. The computational complexity of the algorithm is confirmed experimentally by a large number of numerical experiments. The algorithm consists of 3 steps. At the average, a solution is found at the second step in 83,6 % cases, while the third step gives solution in the remaining cases. The algorithm is realized with the use of the Python programming language. The results of numerical experiments can be found at the service GitHubGist. The elaborated software system was used to solve the problem on formation of the optimal order for education institutions in regions of the Russian Federation. Предлагается новый численный метод решения задачи целочисленного программирования квадратичного вида. Алгоритм основан на специальном представлении ми- нимизатора соответствующего целевого функционала. Проблема может быть сведена к специальной задаче с наименьшими квадратами с ограничениями. Для разработанного метода был предложен алгоритм решения задачи целочисленного программирования квадратичного вида. Преимущество представленного алгоритма заключается в невысокой вычислительной сложности, в среднем, ...