I detta dokument beskriver och utvärderar vi tre olika tekniker för att översätta pseudobooleska begränsningar (linjära begränsningar över booleska variabler) till klausuler som kan hanteras av en standard SAT-solver. Vi visar att genom att tillämpa en ordentlig blandning av översättningstekniker, en SAT-solver kan utföra på samma sätt som de bästa befintliga infödda pseudo-booleska lösare. Detta är särskilt värdefullt i de fall där det restriktiva problemet av intresse naturligtvis uttrycks som ett SAT-problem, med undantag för en handfull begränsningar. Att översätta dessa begränsningar för att få en ren klausal problem kommer att dra full nytta av de senaste förbättringarna inom SAT-forskning. Ett särskilt intressant resultat av detta arbete är effektiviteten i sorteringsnätverken för att uttrycka pseudobooleska begränsningar. Även tangentiell till denna presentation, ger resultatet ett förslag på hur syntesverktyg kan modifieras för att producera aritmetiska kretsar mer lämplig för SAT-baserade resonemang.
Sortera nätverk har befintliga applikationer i t.ex. SAT-kodningar av pseudo-Booleska begränsningar REF.
Translating Pseudo-Boolean Constraints into SAT
{'venue': 'J. Satisf. Boolean Model. Comput.', 'journal': 'J. Satisf. Boolean Model. Comput.', 'mag_field_of_study': ['Computer Science', 'Mathematics']}