Perturbation Based Search Method for Solving Unconstrained Binary Quadratic Programming Problem

Authors: Muthu Solayappan, Kien Ming Ng, Kim Leng Poh

Abstract:

This paper presents a perturbation based search method to solve the unconstrained binary quadratic programming problem. The proposed algorithm was tested with some of the standard test problems and the results are reported for 10 instances of 50, 100, 250, & 500 variable problems. A comparison of the performance of the proposed algorithm with other heuristics and optimization software is made. Based on the results, it was found that the proposed algorithm is computationally inexpensive and the solutions obtained match the best known solutions for smaller sized problems. For larger instances, the algorithm is capable of finding a solution within 0.11% of the best known solution. Apart from being used as a stand-alone method, this algorithm could also be incorporated with other heuristics to find better solutions.

Keywords: unconstrained binary quadratic programming, perturbation, interior point methods

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1081850

References:

[1] C. R. Cassady, L. M. Maillart, and S. Salman, "Ranking sports teams: A customizable quadratic assignment approach," Interfaces, vol. 35, no. 6, pp. 497-510, November 2005.
[2] A. T. Phillips and J. B. Rosen, "A quadratic assignment formulation of the molecular conformation problem," Journal of Global Optimization, vol. 4, no. 2, pp. 229-241, March 1994.
[3] P. M. Pardalos and G. P. Rodgers, "A branch and bound algorithm for the maximum clique problem," Computers and Operations Research, vol. 19, no. 5, pp. 363-375, July 1992.
[4] K. G. Palubeckis, "A tight lower bound for a special case of quadratic 0-1 programming," Computing, vol. 77, no. 2, pp. 131-145, April 2006.
[5] P. M. Pardalos and G. P. Rodgers, "Computational aspects of a branch and bound algorithm for quadratic zero-one programming," Computing, vol. 45, no. 2, pp. 131-144, June 1990.
[6] H. van Maaren and J. P. Warners, "Bounds and fast approximation algorithms for binary quadratic optimization problems with application to max 2sat," Discrete Applied Mathematics, vol. 107, no. 1-3, pp. 225- 239, December 2000.
[7] C. Helmberg and F. Rendl, "Solving quadratic (0,1)-problems by semidefinite programs and cutting planes," Mathematical Programming, vol. 82, no. 3, pp. 291-315, August 1998.
[8] F. Glover, G. A. Kochenberger, and B. Alidaee, "Adaptive memory tabu search for binary quadratic programs," Management Science, vol. 44, no. 3, pp. 336-345, March 1998.
[9] M. Lewis, B. Alidaee, and G. Kochenberger, "Using xQx to model and solve the uncapacitated task allocation problem," Operations Research Letters, vol. 33, no. 2, p. 176 182, March 2005.
[10] G. A. Kochenberger, F. Glover, B. Alidaee, and C. Rego, "An unconstrained quadratic binary programming approach to the vertex coloring problem," Annals of Operations Research, vol. 139, no. 1, pp. 229-241, October 2005.
[11] K. Katayama and H. Narihisa, "Performance of simulated annealingbased heuristic for the unconstrained binary quadratic problem," European Journal of Operations Research, vol. 134, no. 1, pp. 103-119, October 2001.
[12] Z. Drezner, "A new genetic algorithm for the quadratic assignment problem," INFORMS Journal on Computing, vol. 15, no. 3, pp. 320-330, Summer 2003.
[13] A. Lodi, K. Allemand, and T. M. Liebling, "An evolutionary heuristic for quadratic 0-1 programming," European Journal of Operations Research, vol. 119, no. 3, pp. 662-670, December 1999.
[14] C. Dang and L. Xu, "Barrier function method for the nonconvex quadratic programming problem with box constraints," Journal of Global Optimization, vol. 18, no. 2, pp. 165-188, October 2000.
[15] M. S. Bazaraa and C. M. Shetty, Nonlinear Programming: Theory and Algorithms. Singapore: John Wiley & Sons, 1990, pp.252-330.
[16] J. E. Beasley, "OR-library: Distributing test problems by electronic mail," The Journal of the Operational Research Society, vol. 41, no. 11, pp. 1069-1072, November 1990.
[17] J.E.Beasley, "Heuristic algorithms for the unconstrained binary quadratic programming problem," Management School, Imperial College, London, UK, Tech. Rep., December 1998.
[18] P. Merz and B. Freisleben, "Genetic algorithms for binary quadratic programming," in GECCO-1999: Proceedings of the Genetic and Evolutionary Computation Conference, California, 1999, pp. 417-424.
[19] K. Katayama and H. Narihisa, "Performance of simulated annealingbased heuristic for the unconstrained binary quadratic programming problem," European Journal of Operational Research, vol. 134, no. 1, pp. 103-119, October 2001.