I am trying to solve a combinatorial problem by using a SAT Solver.
This involves the following steps:
- Encode the problem as set of boolean expressions.
- Translate a conjunction of the expressions into CNF/DIMACS
(using home grown tools, bc2cnf, bool2cnf or Limboole) - Solve the CNF
(using SAT Solvers like Cryptominisat, Plingeling, Clasp or Z3) - Translate the solution (assuming a "SAT" result) back into the problem domain
This works in my case for small samples. But for more challenging ones, the SAT solver takes hours or even days without coming to a SAT/UNSAT conclusion. I try to tune my encoding to arrive at a solution. But the more effort I put in my encoding, the less certain I can be that my encoding is actually correct (i.e. "satisfiability equivalent").
The step from boolean expression to CNF is rather convoluted to be efficient in terms of a managable number of clauses and variables. It is painful to wait ages for the SAT solver and not be sure that the time is spent on the right track.
The boolean expression might be wrong. Therefore, I'd like to validate that the CNF actually represents the original problem not just the boolean expression.
My Question:
How could I verify that a given encoding is a valid representation of the original boolean expression?
From the literature, I have known solutions for some problems which I could translate into variable assignments to gain trust in my encoding process. But due to Tseitin encoding, most of the variables in my CNF are auxiliary (switching) variables. Without Tseitin encoding, my CNF would be far too big to be solvable. I therefore cannot simply check if every CNF clause is fulfilled by the known solution.
I have tried to translate the CNF back into boolean expressions using cnf2aig, but the tool is still in its infancy. Without switching variables, it is straightforward to check an assigment against boolean expressions of the primary problem variables.
There are a couple of publications about "CNF to circuit" approaches, but none of them provides a usable tool.
Is there any best practice to accomplish such a check?