Name
Abstract | ||
|---|---|---|
Continuous constraint satisfaction problems are at the core of many real-world applications, including planning, scheduling, control, and diagnosis of physical systems such as car, planes, and factories. Yet in order to be effective in such resource-constrained environments, constraint-based techniques must take into account the complexity of continuous constrained problems. In this paper, we study complexity phase transition phenomena of continuous constraint satisfaction problems (CSPs). First, we analyze three continuous constraint satisfaction formulations based on (discrete) 3-SAT problems, which have a strong relation between structure and search cost. Then, we propose a generic benchmarking model for comparing continuous CSPs and algorithms, and present two example problems based on sine functions. In our experiments, these problems are solved using both local and global search methods. Besides comparing the complexities of different continuous CSPs and search algorithms, we also connect these back to results from similar studies on SAT problems. In solving continuous 3-SAT and sine-based CSPs, we find that the median search cost is characterized by simple parameters such as the constraint-to-variable ratio and constraint tightness, and that discrete search algorithms such as GSAT have continuous counter-parts with similar behavior. Regarding local versus global search techniques for constraint solving, our results show that local search methods are more efficient for weakly constrained problems, whereas global search methods work better on highly constrained problems. |
Year | DOI | Venue |
|---|---|---|
2003 | 10.1016/S0020-0255(03)00065-3 | Inf. Sci. |
Keywords | Field | DocType |
continuous csps,discrete search,experimental complexity analysis,local search method,different continuous csps,continuous constraint satisfaction problem,continuous constraint satisfaction formulation,continuous counter-parts,global search method,median search cost,global search technique,constraint satisfaction problem,constraint satisfaction,local search,phase transition,search algorithm,variable ratio,search cost | Constraint satisfaction,Discrete mathematics,Mathematical optimization,Local consistency,Constraint programming,Constraint satisfaction problem,Constraint satisfaction dual problem,Constraint logic programming,Backtracking,Mathematics,Hybrid algorithm (constraint satisfaction) | Journal |
Volume | Issue | ISSN |
153 | 1 | 0020-0255 |
Citations | PageRank | References |
5 | 0.45 | 20 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Yi Shang | 1 | 1383 | 104.53 |
| Markus P. J. Fromherz | 2 | 804 | 57.86 |