Solving Satisfiability Problems Using Elliptic Approximations-A Note on Volumes and Weights.

摘要

In this note the authors propose to use the volume of elliptic approximations of satisfiability problems as a measure for computing weighting coefficients of clauses of different lengths. It is confirmed experimentally that, when applied in a DPLL algorithm with branching strategy based on the ellipsoids, the weight the authors deduce yields better results than the weights that are used in previous studies.