Contando o número de modelos satisfeitos - dadas as restrições matemáticas

Question

Pergunta

Existem muitos algoritmos para resolver o #SENTADO problema, sendo um deles o algoritmo DPLL e é implementado para todos os tipos de linguagens de programação.Pelo que vi, todos eles usam uma fórmula booleana no CNF como entrada e geram o número de interpretações satisfeitas.

Restrições matemáticas, por outro lado, é outra forma de definir uma instância do problema SAT e é frequentemente usado em otimização discreta, onde se tenta otimizar alguma função com relação a essas restrições. Existe um programa que toma restrições matemáticas como entrada e produz o número de interpretações satisfeitas?

Exemplo

Representamos a fórmula booleana $Q = (a \lor b) \cunha (c \lor d)$ tão restrições quanto $$a + b \geq 1 \\ c + d \geq 1$$ ou como uma matriz $A$ e vetor de suporte $b$ $$ a = Begin {bMatrix} 1 & 1 & 0 & 0 0 & 0 & 1 & 1 end {bMatrix} b = Begin {bMatrix} 1 & 1 end {BMatrix} $$

onde todas as variáveis $a,b,c,d\in\{0,1\}$.Sabemos que existem programas que levam $Q$ como entrada e saída o número de interpretações, mas existem programas que levam $A$ e $b$ como entrada (ou construção semelhante) e produz o mesmo número de interpretações?

Answer 1

Conheço duas abordagens razoáveis.

Abordagem nº 1: Conte o número de pontos inteiros dentro de um politopo convexo.

O conjunto de desigualdades lineares que você forneceu, juntamente com as desigualdades $0 \le a,b,c,d \le 1$, define um politopo convexo.Agora, você quer conte o número de pontos inteiros que se enquadram neste politopo.

Existem algoritmos padrão para fazer isso, que você pode aplicar diretamente.Se você pesquisar "contando pontos inteiros em politopo" ou "contando pontos de rede em politopo", encontrará muitos artigos de pesquisa.Veja, por exemplo, https://cstheory.stackexchange.com/q/22280/5038, Encontrando todas as soluções para um problema de programação linear inteira (ILP).

Abordagem nº 2: Converta para CNF e use um solucionador #SAT.

Você sempre pode converter suas restrições em uma fórmula CNF.Cada desigualdade linear pode ser convertida em um conjunto de cláusulas CNF.Uma desigualdade linear da forma $x_i + \pontos + x_j \ge 1$ corresponde imediatamente à cláusula CNF $(x_i \lor \pontos \lor x_j)$.Para uma desigualdade linear mais geral da forma $x_i + \pontos + x_j \ge c$, você deseja expressar a restrição de que pelo menos $c$ Fora de $k$ variáveis $x_i,\pontos,x_j$ são verdadeiros.Existem muitas maneiras padrão de codificar isso.Ver https://cstheory.stackexchange.com/q/23771/5038, Reduza o seguinte problema para SAT, Codificando restrição 1 de n para solucionadores SAT,

(Uma abordagem é converter um circuito booleano que calcula $x_i + \pontos + x_j$ e compara com $c$, em seguida, converta o circuito booleano em CNF usando o Transformada de Tseitin.Você pode criar esse circuito booleano usando circuitos somadores e comparadores padrão.No entanto, existem muitas outras maneiras também.)

Depois de ter uma fórmula CNF que seja equivalente ao conjunto de restrições, você poderá usar qualquer solucionador #SAT disponível no mercado para contar o número de soluções para essa fórmula CNF.

---

É difícil dizer qual destas duas abordagens funcionará melhor;talvez você precise experimentar os dois nos tipos de instância com os quais está lidando, para ter certeza.Eu esperaria que se você tivesse desigualdades lineares da forma $x_i + \pontos + x_j \ge c$ onde $c$ for grande, então a Abordagem nº 1 pode ser superior;mas se $c$ é normalmente pequeno, então a Abordagem nº 2 pode ser superior.

Answer 2

Você pode implementar DPLL diretamente usando restrições em vez de cláusulas.Isso requer a modificação da estrutura de dados e do algoritmo de propagação, mas funciona da mesma forma.

Assim que todas as variáveis ​​da restrição forem definidas, exceto uma, a propagação da unidade poderá ocorrer.

Assim que todas as variáveis ​​da restrição forem definidas, poderá ocorrer um conflito.

O resto do algoritmo permanece o mesmo.

Uma restrição sobre variáveis ​​booleanas é apenas uma coleção de cláusulas CNF ocultas (potencialmente exponencialmente muitas cláusulas dependendo da restrição).

Answer 3

A questão tem sido respondidas em or.stackexchange para software de programação inteira mista, com exemplos de software e scripts existentes (CPLEX, SCIP, ...).

Isso é mais semelhante ao algoritmo CDCL do que ao DPLL:quando uma nova solução é encontrada, uma nova restrição é adicionada para proibi-la e a busca é retomada, até que o problema se torne inviável.