Branch-and-Prune Search Strategies for Numerical Constraint Solving

Details Branch-and-Prune Search Strategies for Numerical Constraint Solving Branch-and-Prune Search Strategies for Numerical Constraint Solving

2005-12-11

arxiv.org/abs/cs/0512045v2

Computer Science

Artificial Intelligence

43 pages, 11 figures

Scientific paper

When solving numerical constraints such as nonlinear equations and inequalities, solvers often exploit pruning techniques, which remove redundant value combinations from the domains of variables, at pruning steps. To find the complete solution set, most of these solvers alternate the pruning steps with branching steps, which split each problem into subproblems. This forms the so-called branch-and-prune framework, well known among the approaches for solving numerical constraints. The basic branch-and-prune search strategy that uses domain bisections in place of the branching steps is called the bisection search. In general, the bisection search works well in case (i) the solutions are isolated, but it can be improved further in case (ii) there are continuums of solutions (this often occurs when inequalities are involved). In this paper, we propose a new branch-and-prune search strategy along with several variants, which not only allow yielding better branching decisions in the latter case, but also work as well as the bisection search does in the former case. These new search algorithms enable us to employ various pruning techniques in the construction of inner and outer approximations of the solution set. Our experiments show that these algorithms speed up the solving process often by one order of magnitude or more when solving problems with continuums of solutions, while keeping the same performance as the bisection search when the solutions are isolated.

Affiliated with

Also associated with

No associations

Rating

Branch-and-Prune Search Strategies for Numerical Constraint Solving does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Branch-and-Prune Search Strategies for Numerical Constraint Solving, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Branch-and-Prune Search Strategies for Numerical Constraint Solving will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-322568