Geodesic
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
Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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},
     year = {2019},
     volume = {12},
     number = {3},
     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
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
%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/

[1] Tat'yankin V. M., Methods and Algorithms for Control of Staffing Processes in a Region, PhD Thesis, Novosibirsk, 2017 (in Russian)

[2] Buchheim C., De Santis M., Palagi L., Piacentini M., “An Exact Algorithm for Nonconvex Quadratic Integer Minimization Using Ellipsoidal Relaxations”, SIAM Journal on Optimization, 23:3 (2013), 1867–1889 | DOI | MR | Zbl

[3] Buchheim C., Caprara A., Lodi A., “An Effective Branch-and-Bound Algorithm for Convex Quadratic Integer Programming”, Mathematical Programming, 135:1–2 (2012), 369–395 | DOI | MR | Zbl

[4] Xiao Wen Chang, Qing Han, “Solving Box-Constrained Integer Least Squares Problems”, IEEE Transactions on Wireless Communications, 7:1 (2008), 277–287 | DOI

[5] Agrell E., Eriksson T., Vardy A., Zeger K., “Closest Point Search in Lattices”, IEEE Transactions on Information Theory, 48:8 (2002), 2201–2214 | DOI | MR | Zbl

[6] Duan Li, Xiaoling Sun, Nonlinear Integer Programming, Springer Science and Business Media, N.Y., 2006 | MR | Zbl

[7] Van Emde Boas P., Another NP-Complete Partition Problem and the Complexity of Computing Short Vectors in a Lattice, University of Amsterdam, Amsterdam, 1981

[8] Axehill D., Integer Quadratic Programming for Control and Communication, PhD Thesis, Institutionen för systemteknik, Linköping, 2008

[9] Lee J., Leyffer S., Mixed Integer Nonlinear Programming, Springer Science and Business Media, N.Y.–Dordrecht–Heidelberg–London, 2012 | DOI | MR | Zbl

[10] Hemmecke R., Köppe M., Lee J., Weismantel R., “Nonlinear Integer Programming”, 50 Years of Integer Programming 1958–2008, Springer, Berlin–Heidelberg, 2010, 561–618 | DOI | Zbl

[11] Borno M. A., Reduction in Solving Some Integer Least Squares Problems, McGill University, Montreal, 2011

[12] Mudrov A. E., The Numerical Computer Solution with Use of Basic, Fortran, and Pascal, Rasko, Tomsk, 1991 (in Russian)