SAT solvers to determine features of multivariate functions?

178 views Asked by At

The Boolean Satisfiabiity problem is a generalization for checking the satisfiability of a boolean expression. Now the boolean expression is generated by the nonnegativity algorithm of a polynomial. The polynomial could for example be $x_1x_2+x_2x_3$ and $x_1$ with some interval such as $x_i\in[0.1,0.3]\;\;\forall i=1,...,n$ where $n$ is the amount of variables. I currently check the features of polynomials such as nonnegativity with special algorithms such as branch-and-bound algorithm where I make the large problem into smaller problems but missing features such as learning promised by some SAT solvers such as MiniSat. So

  1. Some SAT solvers designed to check properties of polynomials such as multilinear functions or general multivariate functions?

  2. Any easy way to convert a multivariate function and the non-negativity algorithm into a boolean expression?

1

There are 1 answers

6
Lars Kotthoff On BEST ANSWER

After a cursory search, there don't seem to be any SAT solvers specifically for this purpose or algorithms to do the conversion you've mentioned. So it would appear that the answer to both of your questions is "no".

There are also some conceptual problems with using SAT solvers for this. It appears that the domains of your variables are continuous, which means that it cannot be converted to SAT directly. You would need to discretise your domains. The second problem is that you need to check an inequality, which you can encode in SAT, but you're risking an exponential increase in problem size.

A more suitable paradigm would be constraint programming, although solvers that support continuous domains are rare.

Altogether, it seems to me that your current branch and bound approach is probably the most suitable one. I am unconvinced that techniques like clause learning would be useful for your particular application, as you are dealing with real intervals. What clause learning essentially does is identify hidden problem structure that can be leveraged in solving the problem. It might help for a SAT encoding of your problem, but all the structure that would be there to discover is what would be lost by encoding the original problem into SAT.