본문 바로가기
  • Home

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 : Engineering > Computer Science

Junha Hwang ORD ID 1

1금오공과대학교

Accredited

ABSTRACT

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.

Citation status

* References for papers published after 2022 are currently being built.