본문 바로가기
  • Home

Integer Programming-based Local Search Technique for Linear Constraint Satisfaction Optimization Problem

  • Journal of The Korea Society of Computer and Information
  • Abbr : JKSCI
  • 2010, 15(9), pp.47-55
  • Publisher : The Korean Society Of Computer And Information
  • Research Area : Engineering > Computer Science

Junha Hwang ORD ID 1 Kim, Sung-Young 1

1금오공과대학교

Accredited

ABSTRACT

Linear constraint satisfaction optimization problem is a kind of combinatorial optimization problem involving linearly expressed objective function and complex constraints. Integer programming is known as a very effective technique for such problem but require very much time and memory until finding a suboptimal solution. In this paper, we propose a method to improve the search performance by integrating local search and integer programming. Basically, simple hill-climbing search, which is the simplest form of local search, is used to solve the given problem and integer programming is applied to generate a neighbor solution. In addition, constraint programming is used to generate an initial solution. Through the experimental results using N-Queens maximization problems, we confirmed that the proposed method can produce far better solutions than any other search methods.

Citation status

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