A Numerical Method for Solving Quadratic Integer Programming Problem

Аннотация

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