Loading...
Please wait, while we are loading the content...
Similar Documents
Branch-and-prune search strategies for numerical constraint solving (2005)
| Content Provider | CiteSeerX |
|---|---|
| Author | Silaghi, Marius-Călin Faltings, Boi Sam-Haroud, Djamila Vu, Xuan-Ha |
| Abstract | 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 |
| File Format | |
| Publisher Date | 2005-01-01 |
| Publisher Institution | Swiss Federal Institute of Technology |
| Access Restriction | Open |
| Subject Keyword | Redundant Value Combination Former Case Several Variant So-called Branch-and-prune Framework Branch-and-prune Search Strategy Branching Step New Search Algorithm Latter Case New Branch-and-prune Search Strategy Numerical Constraint Basic Branch-and-prune Search Strategy Solving Process Pruning Step Complete Solution Nonlinear Equation Outer Approximation Bisection Search |
| Content Type | Text |
| Resource Type | Article |
