Quando usar SAT vs satisfação de restrições?

18

Se eu tiver um problema difícil, uma abordagem padrão é expressá-la como uma instância SAT e tentar executar um solucionador SAT nela. Outra abordagem padrão é expressá-lo como um problema de satisfação de restrições e tentar usar um solucionador de CSP. Os dois se sentem de alguma forma vagamente semelhantes em que tipos de problemas podem ser naturalmente expressos em seu formato de entrada.

Existem diretrizes ou regras práticas para reconhecer, para um determinado problema, qual abordagem tem maior probabilidade de produzir bons resultados? Existe alguma orientação que alguém possa oferecer sobre quais tipos de problemas podem ser tratados melhor pelos solucionadores SAT do que pelos solucionadores CSP, ou vice-versa?

(Obviamente, existem alguns problemas fáceis que podem ser resolvidos pelas duas abordagens. Também existem alguns problemas difíceis que não podem ser resolvidos de maneira útil por nenhuma das abordagens. Vamos deixar isso de lado. O caso em que a orientação é mais útil são os problemas em que o SAT Os solucionadores têm um desempenho melhor que os solucionadores de CSP ou onde os solucionadores de CSP têm melhor desempenho que os solucionadores de SAT.Como reconheço quando é provável que um solucionador de SAT seja mais adequado que um solucionador de CSP ou quando é provável que um solucionador de CSP seja mais adequado um solucionador SAT - ou seja, qual abordagem tentar primeiro?)

heuristics sat-solvers constraint-programming DW
fonte
1
Observe que um problema não pode ser muito difícil se você deseja reduzir para SAT.
Raphael
1
Ou por que focar apenas no SAT / CSP, e o SMT?
Juho 28/05
O uso de uma ferramenta de resolução de restrições tem a vantagem de poder facilmente tentar algumas otimizações (por exemplo, técnicas de quebra de simetria) em instâncias que não são muito difíceis (e verificar a eficácia de tais otimizações). Além disso, muitos deles podem gerar um arquivo CNF padrão como saída intermediária.
Vor
Ótimo ponto, @Juho! Também vale a pena considerar o SMT - fique à vontade para comparar todos os três (SAT, CSP, SMT), se você tiver alguma idéia sobre isso.
DW
Eu tive a mesma pergunta, obrigado por perguntar.
xxx ---

Respostas:

8

Eu acho que essa é uma pergunta muito boa. Você também pode perguntar: quando usar um solucionador SMT? Sinto que pode ser difícil determinar antes de modelar o problema e realmente executar os solucionadores CSP / SAT / SMT e descobrir. É sabido que até diferentes solucionadores têm um desempenho muito diferente nas mesmas instâncias! Minha intuição também vem do fato de que existem potencialmente muitas maneiras de modelar um problema. Além disso, existem muitas maneiras de fazer pesquisa e inferência, dependendo de que tipo de restrições é usado (se o formalismo em questão permitir tipos diferentes).

8×89+9+9=2732.×32. Em quebra-cabeças de Sudoku, os solucionadores SAT seriam mais rápidos que os CSP.

Diferentes formalismos são capazes de capturar informações específicas do domínio e explorá-las melhor e de maneiras diferentes. Para um pouco mais sobre isso, veja a resposta e os comentários aqui .

Juho
fonte