SAT Solver 에서이 하위 집합 커버 문제를 해결하는 것이 가능합니까?

Question

문제는 $ \ mathcal {s} $ 을 찾는 것입니다. $ \ {1 , \ dots, 17 \} $ 2 조건이 만족되도록 $ :

1. $ s \ subeteq \ mathcal {s} $ 다음 $ | s |= 6 $ ;
$ a \ subeteq \ {1, \ dots, 17 \} $ $ |= 3 $ 에는 $ a \ subset s와 함께 $ s \ \ mathcal {s} $ \ \ mathcal> $ .

여기를 참조하십시오. 관련 조합 문제가 있습니다 ..

이것은 이것이 최소 SAT 문제로 공식화 될 수 있다고 생각합니다.

$ s \ subetq \ {1, \ dots, 17 \} $ $ | s |= 6 $ 은 변수 $ x_s $ 을 소개합니다. 각 $ a \ subeteq \ {1, \ dots, 17 \} $ $ | a |= 3 $ , 우리는 조항을 소개합니다 $$ \ Vee_ {s : a \ subetetq s, | s |= 6} x_ {s} $$ 그런 다음 교장에서 우리는 SAT 솔버를 사용하여 모든 조항을 충족시키기 위해 충족해야 할 $ x_s $ 을 찾을 수 있습니다.

이 필요성 $ \ binom {17} {6}= 12376 $ 변수, $ \ binom {17} { 3}= 680 $ 길이 $ \ binom {17-3} {3}= 364 $ .

SAT 솔버를 사용하는 데 실제로 경험이 거의 없습니다. 그래서 이것은 실제로 노트북을 노력할 가치가 있거나 전혀 희망이 없습니다.

---

업데이트

촬영에 대한 많은 연구가 있습니다. 매개 변수 (17, 6, 3)의 문제를 해결하기 위해 야심적이었던 것 같습니다.

(12, 5, 3)에 대한 공개 문제가 있습니다.

자세한 내용은 여기를 참조하십시오.

---

업데이트 2

순수한 SAT에 모든 것을 쓰려고했는데 Z3보다 CADICAL을 사용하여 더 빨리

또한 해결책을 나타내는 것보다 해결책을 찾는 것보다 훨씬 더 빠릅니다.

Lexicon Order의 첫 번째 및 마지막 하위 집합이 선택되어야하는 제약 조건을 추가하여 대칭을 끊으려고했습니다.

Answer 1

SAT로 최적화는 일반적으로 MIN SAT 대신 MAXSAT라고합니다.특히, "가중치 부분 maxsat", 예를 들어 MAXHS 및 RC2에 대한 솔버를 찾는 것이 좋습니다.

당신이 가진 문제는 현대 maxsat-solvers의 맥락에서 상당히 작습니다. 그렇습니다. 그렇습니다.해결사가 효율적으로 작동 할 것이라는 보장은 없으며 효율적으로 작동하는지 예측하기가 매우 어렵습니다. 그래서 가장 좋은 일은 시도하는 것입니다.

Answer 2

에 앉아서, 그것은 실현 가능할 것을 예측하는 것이 어려울 수 있습니다. 시도할만한 가치가 있습니다.

Minsat 대신 $ n= | \ mathcal {s} | $ 에서 바이너리 검색을 먼저 사용해보십시오. 필요한 것. $ x_s $ $ n $ -3e-of-12376 제약을 사용할 수 있습니다. > 변수. 여러 기술 토끼에서 그 안에있는 인코딩은 실제로 처음 z3 솔버를 사용하여

문제는 많은 대칭이 있습니다. SAT 솔버는 때때로 대칭으로 어려움을 겪을 수 있습니다. 대칭을 깨뜨릴 수있는만큼 많은 것을하려고 할 수도 있습니다. 예를 들어, 일반성 손실없이 $ \ {1,2,3,4,5,6 \} $ 은 세트 중 하나입니다 (그렇지 않으면 그래서 모든 숫자는) 이므로이 사실을 SAT 인스턴스로 하드 코드 할 수 있습니다. Sat Solver가 수행 할 수있는 더 많은 lemmas가 더 잘 될 수 있습니다.

세트를 다르게 인코딩 할 수도 있습니다. $ S_I $ 은 $ \ mathcal {s} $ \ span>. $ j \ s_i $ 및 변수 < $ x_ {i, j} $ 을 소개합니다. Span 클래스="수학 용기"> $ y_ {i, a} $ \ span class="수학 컨테이너"> $ a \ subset s_i $ 을 나타내는 span {i, a} $ \ span>, class="수학 컨테이너"> $ a \ subetetq \ {1, \ dots, 17 \} $ $ |= 3 $ 및 각 $ i \ \ {1, \ dots, n \} $ 및 각 $ j \ in \ {1, \ dots, 17 \} $ . 각 $ A $ 에 대해 CLSER 클래스="수학 용기"> $ \ bigvee_i y_ {i, a} $ _ / span>을 추가하십시오. $ a $ $ a $ 은 적어도 하나의 세트로 덮여 있습니다. 각 $ I $ 에 대해 6-out-17 제한 조건을 추가하여 정확히 6 개의 $ x_ {i , j} $ 의 사실입니다. 마지막으로 $ x $ 수학 컨테이너 "> $ y $ 의 $ a={a_1, a_2, a_3 \} $ , 클로스 $ \ neg x_ { i, a_1} \ lor \nneg x_ {i, a_2} \ lor \nneg x_ {i, a_3} \ lor y_ {i, a_ $ 및 $ \ Neg Y_ {i, a} \ lor x_ {i, a_1} $ 및 $ \ neg y_ {i, a} \ lor x_ {i, a_2} $ < / span> 및 $ \ neg y_ {i, a} \ lor x_ {i, a_3} $ . $ (17 + 680) N $ 변수 및 $ 4 \ CDOT 680 n $ 클로스가 필요합니다. $ n $ 6-out-of-17 제약 조건을 계산하지 않음); $ n \ 약 35 $ 을 기대하므로 약 24K 변수와 100K 조항이 있습니다. 그것은 인코딩보다 더 조항이며 더 많은 대칭이므로 더 짧은 조항이지만 SAT에서 가장 효과적으로 작동하는 인코딩을 예측하기가 어렵습니다. 이를 SAT 대신 ILP 인스턴스로 표현할 수도 있습니다.