A Numerical Method for Solving Quadratic Integer Programming Problem

V. M. Tat'yankin; A. V. Shitselov

doi:10.14529/mmp190311

Авторы

V. M. Tat'yankin Югорский государственный университет
A. V. Shitselov Югорский государственный университет

DOI:

https://doi.org/10.14529/mmp190311

Ключевые слова:

нелинейное программирование, целочисленное программирование, численный метод, оптимизация.

Аннотация

Предлагается новый численный метод решения задачи целочисленного программирования квадратичного вида. Алгоритм основан на специальном представлении минимизатора соответствующего целевого функционала. Проблема может быть сведена к специальной задаче с наименьшими квадратами с ограничениями. Для разработанного метода был предложен алгоритм решения задачи целочисленного программирования квадратичного вида. Преимущество представленного алгоритма заключается в невысокой вычислительной сложности, в среднем, которая оценивается в O(nln(n)). Данная вычислительная сложность подтверждена экспериментально. Эксперимент заключался в решении задачи при количестве неизвестных 10, 10^2, ..., 10^8. Каждое вычисление производилось 500 раз. Разработанный алгоритм состоит из 3 шагов. В среднем, в 83,6.
Численный эксперимент реализован на языке 'Python' и размещeн на сервисе GitHubGist. Прикладное значение разработанного алгоритма заключается в его использовании для решения задачи 'Формирование оптимального регионального заказа на подготовку профессиональных кадров по учреждениям высшего и среднего образования в Российской Федерации'.

Биографии авторов

V. M. Tat'yankin, Югорский государственный университет

Кандидат технических наук, доцент,

A. V. Shitselov, Югорский государственный университет

Преподаватель

Библиографические ссылки

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

Buchheim C., De Santis M., Palagi L., Piacentini M. An Exact Algorithm for Nonconvex Quadratic Integer Minimization Using Ellipsoidal Relaxations. SIAM Journal on Optimization, 2013, vol. 23, no. 3, pp. 1867–1889. DOI: 10.1137/120878495

Buchheim C., Caprara A., Lodi A. An Effective Branch-and-Bound Algorithm for Convex Quadratic Integer Programming. Mathematical Programming, 2012, vol. 135, no. 1–2, pp. 369–395. DOI: 10.1007/s10107-011-0475-x

Xiao Wen Chang, Qing Han. Solving Box-Constrained Integer Least Squares Problems. IEEE Transactions on Wireless Communications, 2008, vol. 7, no. 1, pp. 277–287. DOI: 10.1109/TWC.2008.060497

Agrell E., Eriksson T., Vardy A., Zeger K. Closest Point Search in Lattices. IEEE Transactions on Information Theory, 2002, vol. 48, no. 8, pp. 2201–2214. DOI: 10.1109/TIT.2002.800499

Duan Li, Xiaoling Sun. Nonlinear Integer Programming. N.Y., Springer Science and Business Media, 2006.

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

Axehill D. Integer Quadratic Programming for Control and Communication. PhD Thesis. Linkoping, Institutionen f¨or systemteknik, 2008.

Lee J., Leyffer S. Mixed Integer Nonlinear Programming. N.Y., Dordrecht, Heidelberg, London, Springer Science and Business Media, 2012. DOI: 10.1007/978-1-4614-1927-3

Hemmecke R., K¨oppe M., Lee J., Weismantel R. Nonlinear Integer Programming. 50 Years of Integer Programming 1958–2008. Berlin, Heidelberg, Springer, 2010, pp. 561–618. DOI: 10.1007/978-3-540-68279-0_15

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

Mudrov A.E. Chislennye metody dlya PEVM na yazykah Beysik, Fortran i Paskal’ [The Numerical Computer Solution with Use of Basic, Fortran, and Pascal]. Tomsk, Rasko, 1991. (in Russian)