Muthu Solayappan and Kien Ming Ng and Kim Leng Poh
Perturbation Based Search Method for Solving Unconstrained Binary Quadratic Programming Problem
30 - 36
2008
2
1
International Journal of Industrial and Manufacturing Engineering
https://publications.waset.org/pdf/13831
https://publications.waset.org/vol/13
World Academy of Science, Engineering and Technology
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 standalone method,
this algorithm could also be incorporated with other heuristics to find
better solutions.
Open Science Index 13, 2008