Yi Shang, Markus P.J. Fromherz, Lara S. Crawford, and Ying Zhang
In the past decade, significant progress has been made in understanding problem complexity of discrete constraint problems. In contrast, little similar work has been done for constraint problems in the continuous domain. Towards understanding the complexity of continuous constraint problems, in this paper, we investigate complexity phase transition phenomena in solving such problems with increasing constraint-to-variable ratios. Based on two newly proposed generic test-case generators that are modeled after control problems in robotics, we empirically study the complexities of representative deterministic and stochastic local search methods, such as sequential quadratic programming (SQP), Nelder-Mead simplex method and simulated annealing (SA), as well as the complexities of cooperative solvers, in solving both constraint satisfaction and constrained optimization problems. Our results show that problem parameters, including constraint-to-variable ratio and constraint tightness, are useful, but not sufficient in characterizing problem complexity. Regarding deterministic vs. stochastic solvers, we found that SQP is efficient for weakly constrained problems, whereas combining SA and SQP is much better for highly constrained, harder problems. Going from constraint satisfaction problems to constrained optimization problems, our results show that adding a simple objective to the constraint problem could affect the solution time significantly.
This work has been supported in part by DARPA under contract F33615-01-C-1904.