Yi Shang, Yungchun Wan, Markus P.J. Fromherz, and Lara S. Crawford
Search methods for solving continuous constraint problems can be broadly divided into two categories: global search and local search methods. Global search methods spend a great amount of effort exploring the global search space, whereas local search methods focus on converging to local optimal solutions. Although these methods alone work well on many problems, there are many others that will benefit from using cooperative local and global search strategies in a problem solving process. In this paper, we present some alternatives of combining existing local and global methods as cooperative solvers for constraint problems. To demonstrate the benefits of the combined solvers, we compare their performance with individual methods on a series of continuous constraint problems with varying ratio of constraints to variables. The test problems are modeled after control problems in robotics and are very flexible, capable of generating a variety of problems with different characteristics. Our experimental results show that local search methods are best for weakly constrained problems, whereas combining global and local methods is better for highly constrained, harder problems. As a consequence, the balance between global and local search in a combined solver should be adaptive to problem characteristics such as the ratio of constraints to variables.