Towards Adaptive Cooperation between Global and Local Solvers for Continuous Constraint Problems
Yi Shang, Yungchun Wan, Markus P.J. Fromherz, and Lara S. Crawford
Abstract
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.
PDF file
Back to the top.