Kodowanie ograniczenia 1 na n dla solverów SAT

Używam solwera SAT do zakodowania problemu, a jako część instancji SAT mam zmienne logiczne gdzie jest zamierzone, że dokładnie jedna z nich powinna być prawdziwa, a reszta powinna być fałszywa . (Czasami widziałem to opisywane jako kodowanie „na gorąco”).$x_1,x_2,\dots,x_n$

Chcę zakodować ograniczenie „dokładnie jeden z musi być prawdziwe” w SAT. Jaki jest najlepszy sposób na zakodowanie tego ograniczenia, aby solver SAT działał tak skutecznie, jak to możliwe?$x_1,\dots,x_n$

Widzę wiele sposobów kodowania tego ograniczenia:

• Wiązania parami. Mógłbym dodać ograniczenia parowe dla wszystkich aby upewnić się, że co najmniej jeden x_i jest prawdziwy, a następnie dodać x_1 \ lor x_2 \ lor \ cdots \ lor x_n, aby upewnić się, że co najmniej jeden jest prawdziwy . i , j x i x 1 ∨ x 2 ∨ ⋯ ∨ x $\neg x_i \lor \neg x_j$$i,j$$x_i$$x_1 \lor x_2 \lor \cdots \lor x_n$

  Dodaje to klauzule $\Theta(n^2)$ i żadnych dodatkowych zmiennych boolowskich.

• Kodowanie binarne. Mógłbym wprowadzić $\lg n$ nowych zmiennych boolowskich $i_1,i_2,\dots,i_{\lg n}$ aby reprezentować (binarnie) liczbę całkowitą $i$ taką, że $1 \le i \le n$ (dodając kilka ograniczeń boolowskich, aby zapewnić, że $i$ jest w żądanym zakresie). Następnie mogę dodać ograniczenia wymuszające, że $x_i$ jest drzewem i że wszystkie inne $x_j$ są fałszywe. Innymi słowy, do każdego $j$ dodajemy klauzule wymuszające, że $i=j \Leftrightarrow x_j$ .

  Dodaje to klauzule $\Theta(n \lg n)$ i nie wiem, ile dodatkowych zmiennych boolowskich.

• Policz liczbę prawdziwych wartości. Mógłbym zaimplementować drzewo boolowskich obwodów sumujących i wymagać, aby $x_1+x_2+\dots+x_n=1$ , traktując każdy $x_i$ jako 0 lub 1 zamiast fałszu lub prawdy, i użyj transformacji Tseitin do przekształcenia obwodu w klauzule SAT. Wystarczy drzewo pół-sumatorów: ogranicz wyjściową wartość przenoszenia każdego pół-sumatora do 0, a końcową moc wyjściową końcowego pół-sumatora w drzewie należy wynosić 1. Drzewo można wybrać tak, aby miało dowolny kształt ( zrównoważone drzewo binarne, niezrównoważone lub cokolwiek innego).

  Można to zrobić w $\Theta(n)$ bramy i w ten sposób zwiększa $\Theta(n)$ rozdziałów i $\Theta(n)$ nowych zmiennych logicznych.

  Szczególnym przykładem tego podejścia jest wprowadzenie zmiennych boolowskich $y_1,\dots,y_n$ , przy założeniu, że $y_i$ powinien zawierać wartość $x_1 \lor x_2 \lor \cdots \lor x_i$ . Tę intencję można egzekwować, dodając klauzule $y_i \lor \neg x_i$ , $y_i \lor \neg y_{i-1}$ i $\neg y_i \lor x_i \lor y_{i-1}$ (gdzie traktujemy $y_0$ jako synonimem false) dla $i=1,\dots,n$ . Następnie możemy dodać ograniczenia $\neg y_i \lor \neg x_{i+1}$ dla $i=1,2,\dots,n-1$ . Zasadniczo jest to równoważne transformacji Tseitin drzewa pół-sumatora, w którym drzewo ma maksymalnie niezrównoważony kształt.

• Sieć motyli. Mógłbym zbudować sieć motylkową na bitach, ograniczyć wejście bitowe do , ograniczyć wyjście bitowe do i traktować każdą 2-bitową bramę motylkową jako niezależną bramę, która albo zamienia, albo nie zamienia danych wejściowych przy podejmowaniu decyzji na podstawie nowej zmiennej boolowskiej, która nie jest ograniczona. Następnie mogę zastosować transformację Tseitin, aby przekształcić obwód w klauzule SAT.n 000 ⋯ 01 n x 1 x 2 ⋯ x $n$$n$$000\cdots 01$$n$$x_1 x_2 \cdots x_n$

  Wymaga bramy i w ten sposób zwiększa i zawartych nowe zmienne logiczne.Θ ( n lg n ) Θ ( n lg n $\Theta(n \lg n)$$\Theta(n \lg n)$$\Theta(n \lg n)$

Czy są jakieś inne metody, które przeoczyłem? Którego powinienem użyć? Czy ktoś to przetestował lub wypróbował eksperymentalnie, czy też ktoś ma z tym jakieś doświadczenie? Czy liczba klauzul i / lub liczba nowych zmiennych boolowskich jest dobrą miarą zastępczą do oszacowania wpływu tego na wydajność solvera SAT, a jeśli nie, jakiej metryki byś użył?

Właśnie zauważyłem, że w tej odpowiedzi znajdują się odniesienia do egzekwowania ograniczeń liczności dla SAT, tj. Wymuszania ograniczenia, że ​​dokładnie spośród zmiennych jest prawdziwe. Moje pytanie sprowadza się więc do szczególnego przypadku, w którym . Może literatura na temat ograniczeń liczności pomoże rzucić światło na moje pytanie.n k = $k$$n$$k=1$

Dla specjalnego przypadku k spośród n zmiennych true, gdzie k = 1, istnieje kodowanie zmiennych dowódcy, jak opisano w Efektywnym kodowaniu CNF do wybierania obiektów 1 na N przez Kliebera i Kwon. Uproszczone: Podziel zmienne na małe grupy i dodaj klauzule, które powodują, że stan zmiennej dowódcy sugeruje, że grupa zmiennych jest fałszywa lub fałszywa „wszystko oprócz jednego”. Następnie rekurencyjnie zastosuj ten sam algorytm do zmiennych dowódcy. Pod koniec procesu żądaj, aby dokładnie jedna z niewielu ostatnich zmiennych dowódcy była prawdziwa. Wynikiem jest O (n) nowe klauzule i O (n) nowe zmienne.

Biorąc pod uwagę wszechobecność literałów o dwóch obserwacjach w rozwiązaniach opartych na DPLL, myślę, że wzrost klauzuli O (n) jest decydującą przewagą nad schematami kodowania, które dodałyby więcej klauzul.

Artykuł Magnusa Björka opisuje dwie techniki, które mogą być warte wypróbowania.

Dla 1-out- można jednocześnie używać kodowania binarnego i binarnego. Zatem mamy x 1 , … , x n jako kodowanie jednorazowe, i y 1 , … , y b jako kodowanie binarne, gdzie b = lg n . Możemy łatwo zakodować ograniczenie „co najmniej jednego” w jednej klauzuli: ( x 1 ∨ ⋯ ∨ x n ) . Możemy również wymusić, aby oba kodowania były spójne z 2 lg $n$$x_1,\dots,x_n$$y_1,\dots,y_b$$b = \lg n$$(x_1 \lor \dots \lor x_n)$$2 \lg n$klauzule: dodajemy po prostu lub x $x_i \implies \neg y_j$ , zgodnie z tym, czy j- ty bit binarnego kodowania i wynosi 0 czy 1. W końcu ograniczenie „co najwyżej jeden” następuje automatycznie. Pozwala to również pozostałej części instancji SAT na korzystanie z dowolnego wygodniejszego kodowania.$x_i \implies y_j$$j$$i$

W przypadku -out-of- n można zastosować sieć sortującą do danych wejściowych x 1 , … , x n, aby uzyskać posortowane dane wyjściowe y 1 , … , y n , a następnie dodać klauzulę wymagającą, aby y k było prawdziwe i y k + 1 jest fałszem. Istnieje wiele prostych sieci sortujących, które wymagają jedynie jednostek porównawczych O ( n lg 2 n ) . Dlatego otrzymujemy kodowanie wykorzystujące O ( n lg $k$$n$$x_1,\dots,x_n$$y_1,\dots,y_n$$y_k$$y_{k+1}$$O(n \lg^2 n)$ klauzule i zmienne tymczasowe.$O(n \lg^2 n)$

Papier jest

Magnus Björk. Skuteczne techniki kodowania SAT . 25 lipca 2009 r.

Poniższy artykuł zawiera szczegółową listę kodowań dla 1-out-of- i k -out-of- n , z pewną eksperymentalną oceną każdego z nich. Wnioski nie są do końca jasne (kodowanie poleceń w ich eksperymentach wygląda całkiem nieźle).$n$$k$$n$

Alan M. Frisch, Paul A. Giannaros. Kodowania SAT ograniczenia At-Most-k: Niektóre stare, niektóre nowe, niektóre szybkie, niektóre powolne . ModRef 2010.