A Numerical Method for Solving Quadratic Integer Programming Problem

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

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

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

Литература

1. Татьянкин, В.М. Методы и алгоритмы для управления процессами кадрового обеспечения региона: дис. ... канд. техн. наук / В.М. Татьянкин. - Новосибирск, 2017.
2. Buchheim, C. An Exact Algorithm for Nonconvex Quadratic Integer Minimization Using Ellipsoidal Relaxations / C. Buchheim, M. De Santis, L. Palagi, M. Piacentini // SIAM Journal on Optimization. - 2013. - V. 23, № 3. - P. 1867-1889.
3. Buchheim, C. An Effective Branch-and-Bound Algorithm for Convex Quadratic Integer Programming / C. Buchheim, A. Caprara, A. Lodi // Mathematical Programming. - 2012. - V. 135, № 1-2. - P. 369-395.
4. Xiao Wen Chang. Solving Box-Constrained Integer Least Squares Problems / Xiao Wen Chang, Qing Han // IEEE Transactions on Wireless Communications. - 2008. - V. 7, № 1. - P. 277-287.
5. Agrell, E. Closest Point Search in Lattices / E. Agrell, T. Eriksson, A. Vardy, K. Zeger // IEEE Transactions on Information Theory. - 2002. - V. 48, № 8. - P. 2201-2214.
6. Duan Li. Nonlinear Integer Programming / Duan Li, Xiaoling Sun. - New York: Springer Science and Business Media, 2006.
7. Van Emde Boas, P. Another NP-Complete Partition Problem and the Complexity of Computing Short Vectors in a Lattice / P. van Emde Boas. - Amsterdam: University of Amsterdam. - 1981.
8. Axehill, D. Integer Quadratic Programming for Control and Communication. PhD Thesis / D. Axehill. - Linkoping: Institutionen for systemteknik, 2008.
9. Lee, J. Mixed Integer Nonlinear Programming / J. Lee, S. Leyffer. - New York; Dordrecht; Heidelberg; London: Springer Science and Business Media, 2012.
10. Hemmecke, R. Nonlinear Integer Programming. Optimization and Control / R. Hemmecke, M. Koppe, J. Lee, R. Weismantel // 50 Years of Integer Programming 1958-2008. - Berlin; Heidelberg: Springer, 2010. - P. 561-618.
11. Borno, M.A. Reduction in Solving Some Integer Least Squares Problems / M.A. Borno. - Montreal: McGill University. - 2011.
12. Мудров, А.Е. Численные методы для ПЭВМ на языках Бейсик, Фортран и Паскаль / А.Е. Мудров. - Томск: Раско, 1991.