A Numerical Method for Solving Quadratic Integer Programming Problem

Abstract

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 · ln(n)) operations) shown in numerical experiments, where the number of unknowns n can be up to 108 . 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.