Performance Analysis and Mitigating the Challenges of Constraint-based Local Search

摘要

In this paper, we have analyzed the efficiency of local search(LS) with respect to constant programming and also introduced different techniques to mitigate the challenges faced during the implementation of constraint-based local search(CBLS). We have used Google OR tool for constant programming and developed the LS method from scratch in C++. To compare the performance of these two techniques, we have used the well-known $N$-queen problem. The running time of LS approach has been decreased with the help of incremental calculation. Moreover, different challenges such as cycling problem and stagnation in a local minima has been handled using tabu search and random walk respectively. Experimental results show that our LS implementation performs significantly better than the constraint programming(CP) approach of Google OR. Our developed methods are also able to overcome all the hurdles of LS approach.