Complexity of Continuous, 3-SAT-like Constraint Satisfaction Problems

Yi Shang, Markus Fromherz, Tad Hogg, and Warren Jackson

Abstract

Continuous constrained optimization is at the core of many real-world applications such as planning, scheduling, control, and diagnosis of physical systems (car, planes, factories). Effective constraint-based techniques must handle the complexity of real-world continuous constraint problems by dynamically adapting solvers to the structure of the problem. Toward this end, we analyze continuous constraint satisfaction problem formulations based on (discrete) 3-SAT problems, which have a strong relation between structure and search cost. We compare the search complexities of three different problem formulations and three randomized search algorithms. This allows us not only to compare different problems and solution approaches, but also to connect back to results from similar studies on SAT problems. In particular, we find that median search cost is characterized by simple parameters such as the constraint-to-variable ratio, and that discrete search algorithms such as GSAT and WSAT have continuous counter-parts with similar behavior.

PDF file

Back to the top.