A Numerical Method for Solving Quadratic Integer Programming Problem

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(ncdot 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.

Keywords

nonlinear programming; integer programming; numerical method; optimization.

References

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, 2013, vol. 23, no. 3, pp. 1867-1889. DOI: 10.1137/120878495
3. 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
4. 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
5. 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
6. Duan Li, Xiaoling Sun. Nonlinear Integer Programming. N.Y., 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. Amsterdam, University of Amsterdam, 1981.
8. Axehill D. Integer Quadratic Programming for Control and Communication. PhD Thesis. Linkoping, Institutionen for systemteknik, 2008.
9. 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
10. Hemmecke R., Koppe 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
11. Borno M.A. Reduction in Solving Some Integer Least Squares Problems. Montreal, McGill University, 2011.
12. 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)