# software for numerical constraint satisfaction problems

Let $m$ be an even integer greater than $8$. Is there any software I can use to determine for some small $m$ whether the following constraints on $t_0,\ldots,t_{m-1}$ and $w$ have solutions?

$-\pi\leq t_r\leq\pi,\ r=0,\ldots,m-1,$

$0\leq w\leq\frac{1}{m},$

$\sum\limits_{j=1}^{2r-1}\cos(t_j+t_{2r-j})+\sum\limits_{j=2r+1}^{m-1}\cos(t_j+t_{2r+m-j})=2w\cos t_{2r},\ r=1,\ldots,\frac{m}{2}-1,$

$\sum\limits_{j=1}^{2r-1}\sin(t_j+t_{2r-j})+\sum\limits_{j=2r+1}^{m-1}\sin(t_j+t_{2r+m-j})=2w\sin t_{2r},\ r=1,\ldots,\frac{m}{2}-1,$

$t_r+t_{m-r}=0,\ r=1,\ldots,\frac{m}{2},$

$\cos(t_r+t_{\frac{m}{2}+r})=\cos(t_{2r}+rt_0),\ r=1,\ldots,\frac{m}{2}-1,$

$\sin(t_r+t_{\frac{m}{2}+r})=\sin(t_{2r}+rt_0),\ r=1,\ldots,\frac{m}{2}-1,$

$\cos(\frac{mt_0}{2})=1.$

-
The constraint on $w$ seems to be crucial, otherwise we'd immediately get the trivial solution $w=2$, $t_r=0$ for all $r$. – Suvrit Jul 21 '12 at 13:46
Yes, actually I'm considering how small can $w$ be. – Binzhou Xia Jul 22 '12 at 8:45

It seems to me that methods based on interval analysis are very efficient for solving hard constraints satisfaction problems. In particular, SIVIA (Set Inversion Via Interval Analysis) is an algorithm which can approximate using small "boxes" a subset of $\mathbb{R}^n$ satisfying a given set of constraints. It's a branch and bound algorithm, with quite a big complexity, but if the set is actually empty it can answer rather quickly. To be precise, it find an "inner" and an "outer" approximation of this set: if the outer approximation is empty, then your set is guaranteed to be empty, if the inner approximation is non empty then your set is guaranteed to be non empty, otherwise you can't tell and have to try with a higher precision, which increase the computing time and memory usage exponentially.
Yes, it is theoretically convergent. The point is that if $f$ is an elementary function/operation, then $f$ applied to an interval is not generally an interval. So it's replaced by an "interval valued" function which satisfy some conditions which guarantee that you recover the true function when the size of the interval is small enough. Then the precision of the algorithm is roughly related to the size of boxes you allows at the boundary, i.e. between the inner and outer approximation. – Adrien Jul 22 '12 at 15:26
As the name suggest, the general goal of SIVIA is to approximate the inverse image of some subset of $\mathbb{R}^k$ by some function, and when the precision goes to 0, the abovementionned conditions implies that bot the inner and the outer approximation goes to the exact set you're looking for. – Adrien Jul 22 '12 at 15:28