Home > Explore Content > All Issues > Article View
An Integration of Local Search and Constraint Programming for Solving Constraint Satisfaction Optimization Problems
Journal of The Korea Society of Computer and Information
Abbr :
JKSCI
2010, 15(5), pp.39-47
Publisher : The Korean Society Of Computer And Information
Research Area : Computer Science
2010, 15(5), pp.39-47
Publisher : The Korean Society Of Computer And Information
Research Area : Computer Science
-
Constraint satisfaction optimization problem is a kind of optimization problem involving cost minimization as well as complex constraints. Local search and constraint programming respectively have been used for solving such problems. In this paper, I propose a method to integrate local search and constraint programming to improve search performance. Basically, local search is used to solve the given problem. However, it is very difficult to find a feasible neighbor satisfying all the constraints when we use only local search. Therefore, I introduced constraint programming as a tool for neighbor generation. Through the experimental results using weighted N-Queens problems, I confirmed that the proposed method can significantly improve search performance.
139 Viewed
Print this page
Download PDF