Perturbation Based Search Method for Solving Unconstrained Binary Quadratic Programming Problem

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.

Authors:

• Muthu Solayappan
• Kien Ming Ng
• Kim Leng Poh

Keywords:

• unconstrained binary quadratic programming
• perturbation
• interior point methods

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.