A numerical method for solving quadratic integer programming problem
Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ, Matematičeskoe modelirovanie i programmirovanie, Tome 12 (2019) no. 3, pp. 130-139
Voir la notice de l'article provenant de la source Math-Net.Ru
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\cdot\ln(n))$ operations) shown in numerical experiments, where the number of unknowns $n$ can be up to $10^8$. 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.
Keywords:
nonlinear programming, integer programming, numerical method, optimization.
@article{VYURU_2019_12_3_a10,
author = {V. M. Tat'yankin and A. V. Shitselov},
title = {A numerical method for solving quadratic integer programming problem},
journal = {Vestnik \^U\v{z}no-Uralʹskogo gosudarstvennogo universiteta. Seri\^a, Matemati\v{c}eskoe modelirovanie i programmirovanie},
pages = {130--139},
publisher = {mathdoc},
volume = {12},
number = {3},
year = {2019},
language = {en},
url = {http://geodesic.mathdoc.fr/item/VYURU_2019_12_3_a10/}
}
TY - JOUR AU - V. M. Tat'yankin AU - A. V. Shitselov TI - A numerical method for solving quadratic integer programming problem JO - Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ, Matematičeskoe modelirovanie i programmirovanie PY - 2019 SP - 130 EP - 139 VL - 12 IS - 3 PB - mathdoc UR - http://geodesic.mathdoc.fr/item/VYURU_2019_12_3_a10/ LA - en ID - VYURU_2019_12_3_a10 ER -
%0 Journal Article %A V. M. Tat'yankin %A A. V. Shitselov %T A numerical method for solving quadratic integer programming problem %J Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ, Matematičeskoe modelirovanie i programmirovanie %D 2019 %P 130-139 %V 12 %N 3 %I mathdoc %U http://geodesic.mathdoc.fr/item/VYURU_2019_12_3_a10/ %G en %F VYURU_2019_12_3_a10
V. M. Tat'yankin; A. V. Shitselov. A numerical method for solving quadratic integer programming problem. Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ, Matematičeskoe modelirovanie i programmirovanie, Tome 12 (2019) no. 3, pp. 130-139. http://geodesic.mathdoc.fr/item/VYURU_2019_12_3_a10/