만족스러운 모델의 수를 세는 - 수학적 제약 조건이 주어진다.

Question

질문

#sat 문제를 해결하기위한 많은 알고리즘이 있습니다. DPLL 알고리즘은 모든 종류의 프로그래밍 언어에 대해 구현됩니다. 내가 보았던 한, 그들은 모두 CNF에서 입력으로서 부울 수식을 취하여 만족스러운 해석의 수를 출력합니다.

수학 제약 조건 , 인스턴스를 정의하는 또 다른 방법입니다 SAT 문제의 경우 종종 이들 제약 조건과 관련하여 일부 기능을 최적화하려고 시도하는 이산 최적화에 종종 사용됩니다. 은 수학적 제약 조건을 입력으로 취하는 프로그램이 있으며 만족스러운 해석의 수를 출력합니까?

예제

우리는 부울 수식 $ q= (a \ lor b) \ 웨지 (C \ lor d) \ 웨지 (c \ lor d) $ 은 $$ a + b \ geq 1 \\ c + d \ geq 1 $$ 또는 matrix $ a $ 및 지원 벡터 < SPAN 클래스="수학 용기"> $ B $ $$ = \ 시작 {bmatrix} 1 & 1 & 0 & 0 \\ 0 & 0 & 1 및 1. \ end {bmatrix} \\ b=begin {bmatrix} 1 & 1 \ END {bmatrix} $$

모든 변수 $ a, b, c, d \ in \ {0,1 \} $ . 우리는 $ q $ 을 입력으로 복용하고 해석의 수를 출력하지만 $ a $ < / span> 및 $ b $ 입력 (또는 유사한 건설)으로서 동일한 수의 해석 수를 출력합니까?

Answer 1

두 가지 합리적인 접근법을 알고 있습니다.

접근법 # 1 : convex polytope 내부의 정수 포인트의 수를 계산합니다.

당신이 제공 한 선형 불평등 세트 $ 0 \ LE A, B, C, D \ LE 1 $ , 볼록한 폴리 토프를 정의합니다. 이제 이 polytope 내에있는 정수 지점의 수를 계산하십시오. 직접 신청할 수있는 표준 알고리즘이 있습니다. "Polytope의"정수 지점 계산 "또는"Polytope의 격자 지점 계산 "을 검색하면 많은 연구 논문이 있습니다. 예를 들어, https://cstheory.stackexchange.com/q/k/22880/5038 모든 솔루션을 정수 선형 프로그래밍 (ILP) 문제점 에 대한 .

접근법 # 2 : cnf로 변환 한 다음 #sat solver를 사용하십시오.

항상 제약 조건을 CNF 수식으로 변환 할 수 있습니다. 각 선형 불평등은 CNF 절의 세트로 변환 될 수 있습니다. $ x_i + dots + x_j \ ge 1 $ 은 CNF 절 $ (x_i)에 해당합니다. \ lor \ dots \ lor x_j) $ . $ x_i + \ dots + x_j \ ge c $ 형식의보다 일반적인 선형 불평등을 위해, 적어도 $ c $ $ k $ 변수 $ x_i, \ dots, x_j $ 은 true입니다. 인코딩의 많은 표준 방법이 있습니다. https://cstheory.stackexchange.com/q/23771/5038 Sat , 인코딩 1 SAT 솔버에 대한 제약 조건 ,

(하나의 접근법은 $ x_i + dots + x_j $ 을 계산하는 부울 회로를 변환하고 를 비교하는 것입니다. $ C $ , 그런 다음 Tseitin Transform 를 사용하여 부울 회로를 CNF로 변환하십시오. 표준 가산기 및 비교기 회로를 사용하여 이러한 부울 회로를 만들 수 있습니다. 그러나 다른 많은 방법이 있습니다.)

제약 조건 집합과 동일한 CNF 수식이 있으면 오프 - 샤프 #SAT 솔버를 사용하여 CNF 수식에 대한 해결 수를 계산할 수 있습니다.

---

이 두 가지 접근법 중 어느 것이 더 잘 작동하는지 말하기가 어렵습니다. 당신은 확실히 알아야 할 인스턴스의 종류 모두에서 그들 모두를 시도해야 할 수도 있습니다. $ x_i + \ dots + x_j \ ge c $ $ C $ 은 크게, 접근법 # 1이 우월 할 수 있습니다. 그러나 $ C $ 이 일반적으로 작 으면 접근법 # 2가 우월 할 수 있습니다.

Answer 2

절이 대신 제약 조건을 사용하여 직접 DPLL을 구현할 수 있습니다.이를 위해서는 데이터 구조와 전파 알고리즘을 수정해야하지만 모두 동일하게 작동합니다.

제약 조건의 모든 변수가 하나를 제외하고는 단위 전파가 발생할 수 있습니다.

제약 조건의 모든 변수가 설정 되 자마자 충돌이 발생할 수 있습니다.

나머지 알고리즘은 동일하게 유지됩니다.

부울 변수를 통한 제약 조건은 숨겨진 CNF 절을 컬렉션 (제약 조건에 따라 잠재적으로 기하 급수적으로 많은 조항) 컬렉션 일뿐입니다.

Answer 3

질문은 답변 됨 on 또는기존 소프트웨어 및 스크립트의 예 (CPLEX, SCIP, ...)의 예를 들어, 혼합 정수 프로그래밍 소프트웨어에 대한 stackexchange.

DPLL보다 CDCL 알고리즘과 비슷합니다. 새 솔루션이 발견되면 문제가 불가능 해지 전까지는 새로운 솔루션이 발견되면 새로운 제약 조건이 추가됩니다.