diff options
author | Mathias Soeken <mathias.soeken@gmail.com> | 2017-03-03 10:33:59 +0100 |
---|---|---|
committer | Mathias Soeken <mathias.soeken@gmail.com> | 2017-03-03 10:33:59 +0100 |
commit | f03871ab22b6c8a487e8fce19ab6b8a540b849f8 (patch) | |
tree | b2c4c1fad6f8b5ce111e0545ed34c89d38397fc9 /src/sat/bsat/satSolver.c | |
parent | 28e8e7f3e79d1391a2f3a31cefe3afe234aa3b8e (diff) | |
parent | b1907e909d92d1147937b26b5e97fb344647f719 (diff) | |
download | abc-f03871ab22b6c8a487e8fce19ab6b8a540b849f8.tar.gz abc-f03871ab22b6c8a487e8fce19ab6b8a540b849f8.tar.bz2 abc-f03871ab22b6c8a487e8fce19ab6b8a540b849f8.zip |
Merged alanmi/abc into default
Diffstat (limited to 'src/sat/bsat/satSolver.c')
-rw-r--r-- | src/sat/bsat/satSolver.c | 147 |
1 files changed, 147 insertions, 0 deletions
diff --git a/src/sat/bsat/satSolver.c b/src/sat/bsat/satSolver.c index df9ada8e..fe7e65fe 100644 --- a/src/sat/bsat/satSolver.c +++ b/src/sat/bsat/satSolver.c @@ -2168,6 +2168,153 @@ int sat_solver_solve_lexsat( sat_solver* s, int * pLits, int nLits ) return status; } +// This procedure is called on a set of assumptions to minimize their number. +// The procedure relies on the fact that the current set of assumptions is UNSAT. +// It receives and returns SAT solver without assumptions. It returns the number +// of assumptions after minimization. The set of assumptions is returned in pLits. +int sat_solver_minimize_assumptions( sat_solver* s, int * pLits, int nLits, int nConfLimit ) +{ + int i, k, nLitsL, nLitsR, nResL, nResR; + if ( nLits == 1 ) + { + // since the problem is UNSAT, we will try to solve it without assuming the last literal + // if the result is UNSAT, the last literal can be dropped; otherwise, it is needed + int status = l_False; + int Temp = s->nConfLimit; + s->nConfLimit = nConfLimit; + status = sat_solver_solve_internal( s ); + s->nConfLimit = Temp; + return (int)(status != l_False); // return 1 if the problem is not UNSAT + } + assert( nLits >= 2 ); + nLitsL = nLits / 2; + nLitsR = nLits - nLitsL; + // assume the left lits + for ( i = 0; i < nLitsL; i++ ) + if ( !sat_solver_push(s, pLits[i]) ) + { + for ( k = i; k >= 0; k-- ) + sat_solver_pop(s); + return sat_solver_minimize_assumptions( s, pLits, i+1, nConfLimit ); + } + // solve for the right lits + nResL = sat_solver_minimize_assumptions( s, pLits + nLitsL, nLitsR, nConfLimit ); + for ( i = 0; i < nLitsL; i++ ) + sat_solver_pop(s); + // swap literals +// assert( nResL <= nLitsL ); +// for ( i = 0; i < nResL; i++ ) +// ABC_SWAP( int, pLits[i], pLits[nLitsL+i] ); + veci_resize( &s->temp_clause, 0 ); + for ( i = 0; i < nLitsL; i++ ) + veci_push( &s->temp_clause, pLits[i] ); + for ( i = 0; i < nResL; i++ ) + pLits[i] = pLits[nLitsL+i]; + for ( i = 0; i < nLitsL; i++ ) + pLits[nResL+i] = veci_begin(&s->temp_clause)[i]; + // assume the right lits + for ( i = 0; i < nResL; i++ ) + if ( !sat_solver_push(s, pLits[i]) ) + { + for ( k = i; k >= 0; k-- ) + sat_solver_pop(s); + return sat_solver_minimize_assumptions( s, pLits, i+1, nConfLimit ); + } + // solve for the left lits + nResR = sat_solver_minimize_assumptions( s, pLits + nResL, nLitsL, nConfLimit ); + for ( i = 0; i < nResL; i++ ) + sat_solver_pop(s); + return nResL + nResR; +} + +// This is a specialized version of the above procedure with several custom changes: +// - makes sure that at least one of the marked literals is preserved in the clause +// - sets literals to zero when they do not have to be used +// - sets literals to zero for disproved variables +int sat_solver_minimize_assumptions2( sat_solver* s, int * pLits, int nLits, int nConfLimit ) +{ + int i, k, nLitsL, nLitsR, nResL, nResR; + if ( nLits == 1 ) + { + // since the problem is UNSAT, we will try to solve it without assuming the last literal + // if the result is UNSAT, the last literal can be dropped; otherwise, it is needed + int RetValue = 1, LitNot = Abc_LitNot(pLits[0]); + int status = l_False; + int Temp = s->nConfLimit; + s->nConfLimit = nConfLimit; + + RetValue = sat_solver_push( s, LitNot ); assert( RetValue ); + status = sat_solver_solve_internal( s ); + sat_solver_pop( s ); + + // if the problem is UNSAT, add clause + if ( status == l_False ) + { + RetValue = sat_solver_addclause( s, &LitNot, &LitNot+1 ); + assert( RetValue ); + } + + s->nConfLimit = Temp; + return (int)(status != l_False); // return 1 if the problem is not UNSAT + } + assert( nLits >= 2 ); + nLitsL = nLits / 2; + nLitsR = nLits - nLitsL; + // assume the left lits + for ( i = 0; i < nLitsL; i++ ) + if ( !sat_solver_push(s, pLits[i]) ) + { + for ( k = i; k >= 0; k-- ) + sat_solver_pop(s); + + // add clauses for these literal + for ( k = i+1; k > nLitsL; k++ ) + { + int LitNot = Abc_LitNot(pLits[i]); + int RetValue = sat_solver_addclause( s, &LitNot, &LitNot+1 ); + assert( RetValue ); + } + + return sat_solver_minimize_assumptions2( s, pLits, i+1, nConfLimit ); + } + // solve for the right lits + nResL = sat_solver_minimize_assumptions2( s, pLits + nLitsL, nLitsR, nConfLimit ); + for ( i = 0; i < nLitsL; i++ ) + sat_solver_pop(s); + // swap literals +// assert( nResL <= nLitsL ); + veci_resize( &s->temp_clause, 0 ); + for ( i = 0; i < nLitsL; i++ ) + veci_push( &s->temp_clause, pLits[i] ); + for ( i = 0; i < nResL; i++ ) + pLits[i] = pLits[nLitsL+i]; + for ( i = 0; i < nLitsL; i++ ) + pLits[nResL+i] = veci_begin(&s->temp_clause)[i]; + // assume the right lits + for ( i = 0; i < nResL; i++ ) + if ( !sat_solver_push(s, pLits[i]) ) + { + for ( k = i; k >= 0; k-- ) + sat_solver_pop(s); + + // add clauses for these literal + for ( k = i+1; k > nResL; k++ ) + { + int LitNot = Abc_LitNot(pLits[i]); + int RetValue = sat_solver_addclause( s, &LitNot, &LitNot+1 ); + assert( RetValue ); + } + + return sat_solver_minimize_assumptions2( s, pLits, i+1, nConfLimit ); + } + // solve for the left lits + nResR = sat_solver_minimize_assumptions2( s, pLits + nResL, nLitsL, nConfLimit ); + for ( i = 0; i < nResL; i++ ) + sat_solver_pop(s); + return nResL + nResR; +} + + int sat_solver_nvars(sat_solver* s) { |