제약 충족 문제

수치해석 최적설계 마지막 수정: 2026-09-02 04:51:05

1. 개요[편집]

제약 충족 문제 Constraint Satisfaction Problem (CSP)
정의	삼중항 $\langle X, D, C \rangle$ — 변수·정의역·제약
묻는 것	모든 제약을 만족하는 할당이 있는가 (충족)
복잡도	일반적으로 NP-완전. 유한 정의역 CSP는 이분법이 성립
완전 탐색	백트래킹 + 제약 전파(AC-3, MAC)
불완전 탐색	min-conflicts 등 국소 탐색
환원 대상	SAT · 정수계획법

“이런 조건들을 전부 만족하는 배치가 있냐”는 질문은 공학의 절반이다. 나머지 절반은 그중 제일 싼 걸 고르는 것이고.

제약 충족 문제(Constraint Satisfaction Problem, CSP)는 변수 집합 $X = \{x_1,\dots,x_n\}$ , 각 변수의 정의역 $D = \{D_1,\dots,D_n\}$ , 그리고 변수들의 부분집합 위에 허용되는 값 조합을 규정하는 제약 집합 $C$ 로 이루어진 삼중항 $\langle X, D, C\rangle$ 에 대해, 모든 제약을 동시에 만족하는 완전 할당을 찾거나 없음을 증명하는 문제다. 스도쿠·시간표 짜기·주파수 배정·설비 배치가 전부 같은 틀 하나로 표현된다는 것이 이 형식의 힘이다.

핵심은 목적함수가 없다는 점이다. 답이 “된다/안 된다”이지 “얼마나 좋다”가 아니다. 여기에 목적함수를 얹으면 조합 최적화가 되고 도구가 분지한정법·정수계획법으로 갈린다. 반대로 값이 0/1뿐이고 제약이 절(clause)이면 SAT 풀이기의 세계다. CSP는 이 둘 사이에서 **“구조를 그대로 드러낸 채 표현한다”**는 자리를 차지한다 — 원래 문제의 변수와 제약이 모델 안에 그대로 살아 있어, 문제 지식을 알고리즘에 직접 꽂아 넣을 수 있다.

푸는 절차(백트래킹, 전방 검사, AC-3, MRV/LCV, 백점핑) 자체는 백트래킹 문서가 자세히 다루므로, 이 문서는 문제를 어떻게 정식화하고, 어떤 구조가 문제를 쉽게 만들며, 언제 다른 형식으로 넘길 것인가에 무게를 둔다.

2. 형식 — 제약 그래프와 항수[편집]

제약 $c \in C$ 는 범위(scope, 관여하는 변수들)와 관계(허용되는 값 조합)의 쌍이다. 관여 변수 수를 항수(arity)라 한다.

단항 제약: $x_3 \ne 5$ . 정의역을 미리 깎아 없애면 그만이라 이론적으로는 의미가 없다.
이항 제약: $x_i \ne x_j$ , $|x_i - x_j| > 2$ . 두 변수를 정점, 제약을 간선으로 그리면 제약 그래프가 되고, CSP 이론의 대부분이 이 그래프 위에서 전개된다.
$k$ -항 제약: 세 변수 이상. 이때는 그래프가 아니라 제약 하이퍼그래프다.

모든 CSP는 이항으로 환원할 수 있다. 이중 인코딩(dual encoding)은 각 제약을 하나의 변수로 삼고 그 정의역을 “그 제약을 만족하는 튜플들”로 두어, 변수를 공유하는 제약 쌍 사이에 일관성 제약을 건다. 은닉 변수 인코딩(hidden variable encoding)은 원 변수를 남긴 채 제약마다 튜플 변수를 하나씩 추가한다. 이론 논문이 “일반성을 잃지 않고 이항 CSP만 다룬다”고 선언할 수 있는 근거가 이것이다. 다만 실무에서 그렇게 하면 대개 손해다 — 환원 과정에서 원 제약이 품고 있던 구조가 뭉개져 전파가 약해지기 때문이다. 그 구조를 지키려고 만든 것이 다음 절의 전역 제약이다.

3. 전역 제약 — 제약 프로그래밍의 진짜 무기[편집]

전역 제약(global constraint)은 여러 변수에 한꺼번에 걸리되, 그 제약만을 위한 전용 필터링 알고리즘을 갖는 제약이다. CSP를 SAT나 ILP로 안 내리고 굳이 제약 프로그래밍으로 푸는 이유의 90%가 여기에 있다.

가장 유명한 것이 all-different( $x_1,\dots,x_k$ 가 모두 다르다)다. 이걸 $\binom{k}{2}$ 개의 이항 $\ne$ 제약으로 쪼개면 전파가 놀랍도록 약해진다. 예를 들어 변수 셋의 정의역이 모두 $\{1,2\}$ 라면 사람 눈에는 즉시 모순인데, 이항 $\ne$ 만으로는 어떤 값도 못 지운다 — 각 값에 대해 다른 변수가 취할 수 있는 값이 여전히 남아 있기 때문이다.

레진(1994)은 값 그래프의 이분 매칭으로 이 문제를 정확히 푼다. 변수를 한쪽, 값을 다른 쪽에 놓은 이분 그래프에서 크기 $k$ 의 매칭이 존재해야 해가 있고(홀의 결혼 정리), 어떤 최대 매칭에도 속하지 않는 간선에 해당하는 값은 어떤 해에도 못 들어가므로 지워도 안전하다. 그런 간선은 매칭 하나를 호프크로프트-카프로 구한 뒤 잔여 그래프의 강한 연결 요소와 교대 경로를 보면 한꺼번에 찾을 수 있다.¹ 결과는 일반화 호 일관성(GAC) — 그 제약 하나에 관한 한 지울 수 있는 값을 전부 지운 상태다.

같은 발상의 전역 제약이 수십 종 있다.

cumulative — 자원 용량 제약. 시각마다 동시에 돌아가는 작업의 자원 합이 상한 이하. 스케줄링의 핵심 부품이고, 에너지 논증·타임테이블 필터링 같은 전용 추론이 붙는다.
element — $y = a[x]$ , 즉 배열 인덱싱을 제약으로. 조건부 모델링의 만능 도구.
table / extensional — 허용 튜플 목록을 통째로 주는 제약. 공정 조합표처럼 규칙이 없는 데이터에 쓴다.
regular — 변수열이 주어진 유한 오토마타를 통과해야 한다. “근무 패턴은 야간 3연속 금지” 같은 순서 규칙을 오토마타로 적으면 필터링이 공짜로 따라온다.

4. 일관성의 계층[편집]

제약 전파는 “이 값은 어떤 해에도 들어갈 수 없다”를 탐색 없이 국소적으로 증명해 정의역을 깎는 일이다. 얼마나 넓게 보느냐로 계층이 생긴다.

수준	무엇을 보장하나	비용
노드 일관성	단항 제약 위반 값 없음	$O(nd)$
호 일관성	모든 값에 이웃의 지지자가 하나씩 존재	AC-3 이 $O(ed^3)$
경로 일관성	두 변수의 모든 허용 쌍이 임의의 제3 변수로 확장 가능	$O(n^3d^3)$
$k$ -일관성	일관된 $k-1$ 개 할당이 임의의 $k$ 번째 변수로 확장 가능	$k$ 에 대해 지수

$1$ 부터 $k$ 까지 전부 만족하면 강한 $k$ -일관성이라 하고, 강한 $n$ -일관성이면 백트래킹 없이 변수를 하나씩 채워도 절대 막히지 않는다. 문제는 이걸 달성하는 비용이 문제를 그냥 푸는 비용보다 비싸다는 것. 그래서 실무는 호 일관성 언저리에서 멈추고, 나머지는 탐색에 맡긴다. 전파를 얼마나 세게 걸 것인가가 이 분야의 영원한 튜닝 손잡이이며, 자세한 알고리즘과 MAC 전략은 백트래킹 문서로 넘긴다.

5. 구조가 쉬움을 결정한다[편집]

제약 그래프의 모양만으로 다항 시간이 보장되는 경우가 있다. 이것이 CSP 이론의 가장 실용적인 부분이다.

트리 구조. 제약 그래프에 고리가 없으면, 잎에서 루트 방향으로 한 번만 호 일관성을 걸고(방향성 호 일관성) 루트에서 잎 방향으로 값을 확정하면 백트래킹이 단 한 번도 일어나지 않는다. 시간은 $O(nd^2)$ .
컷셋 조건화(cutset conditioning). 정점 $c$ 개를 제거하면 트리가 되는 그래프라면, 그 $c$ 개에 모든 값 조합을 대입해 보고 나머지를 트리로 푼다. $O(d^c \cdot (n-c)d^2)$ — $c$ 가 작을 때만 쓸모 있다.
트리 분해와 트리폭. 그래프를 겹치는 덩어리들의 트리로 덮고 덩어리 안을 통째로 푼다. 트리폭 $w$ 이면 $O(n d^{w+1})$ . 트리폭이 상수로 묶인 문제군은 다항 시간에 풀린다는 뜻이고, 이는 동적 계획법을 그래프 분해 위에 올리는 일반적 기법과 정확히 같은 이야기다.

여기서 실무적 교훈이 하나 나온다. 모델링을 잘하면 그래프가 성겨진다. 제약을 잘게 쪼개 변수 사이를 촘촘히 잇는 대신, 전역 제약으로 묶어 하이퍼간선 하나로 만들면 구조가 단순해지고 전파도 강해진다.

6. 왜 어렵고, 어디까지 알려져 있나[편집]

일반 CSP의 충족 판정은 NP-완전이다. 3-SAT과 그래프 3-색칠이 둘 다 CSP의 특수 사례이므로 자명하다. 그런데 제약 관계의 종류를 고정하면 이야기가 달라진다.

셰이퍼의 이분법 정리(1978). 정의역이 $\{0,1\}$ 인 불리언 CSP는, 허용 관계 집합이 여섯 가지 유형(2-SAT형, 혼 절형, 쌍대 혼 절형, 아핀, 0-유효, 1-유효) 중 하나에 속하면 다항 시간에 풀리고 그렇지 않으면 예외 없이 NP-완전이다. “중간 난이도”가 존재하지 않는다는 것이 요점이며, 일반 NP에서는 (P≠NP 가정 아래) 중간 난이도 문제가 존재하므로 이건 CSP만의 특별한 성질이다.
CSP 이분법 정리. 페더와 바르디(1993)가 이 이분법이 모든 유한 정의역으로 확장되리라 추측했고, 2017년 불라토프와 주크가 각각 독립적으로 증명했다. 판정 기준은 관계 집합이 특정 다형성(polymorphism)을 갖느냐라는 대수적 조건이다.

실용적 함의는 “내 문제가 다항인지 대수적으로 판정하자”가 아니다. 문제 인스턴스의 난이도가 매개변수 하나에 따라 급격히 갈린다는 관측 쪽이 훨씬 유용하다. 무작위로 생성한 CSP는 제약이 너무 적으면 해가 널려 있어 쉽고, 너무 많으면 모순이 금방 드러나 쉬우며, 그 사이 좁은 구간에서 어려운 인스턴스가 몰린다. SAT 풀이기 문서가 다루는 랜덤 3-SAT 상전이가 같은 현상의 가장 잘 연구된 사례다.

7. 국소 탐색과 n-퀸의 교훈[편집]

완전 탐색을 포기하고 완전 할당에서 출발해 위반을 줄여 나가는 방법도 있다. min-conflicts 휴리스틱이 대표적이다.

무작위(또는 탐욕적) 완전 할당에서 시작
반복:
    충돌에 관여한 변수 하나를 무작위로 고른다
    그 변수의 값을 "충돌 수가 최소가 되는 값"으로 바꾼다

민턴 등(1990)이 허블 우주망원경 관측 스케줄링(SPIKE) 작업에서 뽑아낸 방법인데,² n-퀸에서의 결과가 유명하다. 백만 퀸이 평균 50여 번의 이동으로 풀린다. 백트래킹으로는 수만 퀸도 버거운데 무슨 일인가.

이유는 문제의 구조에 있다. 첫째, n-퀸은 해가 지독히 많다. $n$ 이 커지면 해의 개수가 초지수적으로 늘어나 임의의 배치에서 가장 가까운 해까지의 거리가 매우 짧다. 둘째, 국소 최소에 갇힐 여지가 적다. 제약이 전부 “같은 행/대각선 금지”라는 동종의 이항 제약이라, 충돌 수 지형이 평탄하고 한 퀸을 옮기는 것이 다른 퀸에 미치는 영향이 국소적이다. 셋째, 위 상전이 관점에서 n-퀸은 제약이 헐거운 쪽(under-constrained)에 한참 치우쳐 있다.

그래서 여기서 끌어낼 교훈은 “국소 탐색이 백트래킹보다 낫다”가 아니다. n-퀸이 백트래킹 알고리즘의 벤치마크로 부적절하다는 것에 가깝다. 국소 탐색은 불완전해서 해가 없음을 증명할 수 없고, 제약이 빡빡한 문제에서는 만족스러운 해가 있어도 못 찾고 헤맨다. 실무 처방은 이중 전략이다 — 완전 탐색에 노드 수·시간 상한을 걸어 두고, 걸리면 담금질 모사나 min-conflicts로 넘어간다. 상용 솔버들은 이걸 “재시작”이라는 이름으로 내장하고 있다.

8. 다른 형식으로 넘기기[편집]

CSP를 직접 풀지 않고 잘 발달한 솔버에 던지는 것도 훌륭한 전략이다.

SAT 환원. 가장 흔한 것이 직접 인코딩(direct encoding)으로, 각 (변수, 값) 쌍에 불리언 $b_{i,a}$ 를 하나씩 두고 세 종류의 절을 만든다.

at-least-one: $\bigvee_{a \in D_i} b_{i,a}$ (변수마다 값이 하나는 있다)
at-most-one: $\lnot b_{i,a} \lor \lnot b_{i,a'}$ (값이 둘일 수 없다)
충돌 금지: 제약이 금지하는 조합 $(a,b)$ 마다 $\lnot b_{i,a} \lor \lnot b_{j,b}$

문제는 CDCL의 단위 전파가 원 CSP의 호 일관성만큼 강하지 않다는 것이다. 그래서 금지 조합 대신 “허용 조합의 논리합”을 절로 적는 지지 인코딩(support encoding)을 쓰면 단위 전파가 정확히 호 일관성을 흉내 내게 된다. at-most-one 절이 $O(d^2)$ 개로 불어나는 문제는 사다리 인코딩·정류자 인코딩 같은 보조 변수 기법으로 $O(d)$ 로 줄인다. 값이 많으면 $\lceil \log_2 d \rceil$ 개 비트로 값을 이진 표현하는 로그 인코딩도 있는데, 절 수는 적지만 전파가 훨씬 약해져 대개 손해다.

정수계획 환원. 같은 0-1 변수에 $\sum_a x_{i,a} = 1$ 과 $x_{i,a} + x_{j,b} \le 1$ 을 걸면 그대로 정수계획법이 된다. 이쪽의 강점은 선형완화 경계이므로, 목적함수가 있고 그 경계가 잘 조여지는 문제(배정·커버·흐름 구조)에서는 CP보다 크게 앞선다. 반대로 목적함수 없이 순수하게 조합적 충족만 따지거나, all-different·순서 제약이 지배적인 문제에서는 완화 경계가 무력해 CP·SAT이 이긴다. 그래서 현실의 큰 시스템은 둘을 섞는다 — 상용 솔버들이 CP 엔진 안에 선형 완화를 얹거나, 논리 기반 벤더스 분해로 상위 배정은 ILP, 하위 스케줄링은 CP로 나눠 푸는 식이다.

9. 어디에 쓰나[편집]

스케줄링. 잡숍·자원 제약 프로젝트 스케줄링이 CSP의 간판 응용이다. 작업 시작 시각이 변수, 정의역이 시간창, 제약이 선후 관계와 cumulative 자원. 목적(총 완료 시간 최소화)이 붙으면 CSP 위에 “최적값 $\le B$ “를 제약으로 얹고 $B$ 를 조여 가며 반복해 푸는 것이 표준 수법이다.
시간표·근무표. 강의실·교원·시간대 배정, 간호사 근무표. 규칙이 사람 말로 주어지고 자주 바뀌기 때문에, 모델을 읽을 수 있게 유지하는 것이 성능만큼 중요하다. CP 모델이 ILP보다 선호되는 전형적 자리.
주파수·채널 배정. 무선 링크에 주파수를 배정하되 간섭 제약을 지킨다. 본질적으로 가중 그래프 색칠이고, CELAR 벤치마크가 이 분야의 고전 문제집이다.
제품 구성과 설계 규칙. 자동차 옵션 조합, PCB 부품 선택처럼 “이 옵션을 고르면 저건 안 된다”가 수백 개인 문제. 사용자가 하나 고를 때마다 호 일관성을 실시간으로 다시 걸어 선택 불가능해진 옵션을 즉시 회색 처리하는 것이 전형적 UI 구현이다.
레지스터 할당과 컴파일러. 간섭 그래프 색칠이 CSP이며, 명령어 스케줄링도 마찬가지다.
해석 파이프라인. 실험 계획의 조합 생성, 격자 블록 배치, 다물체 조립 순서 결정, 분자 배좌 열거처럼 “이산 선택 + 양립 불가 규칙”이 있는 전처리 단계가 조용히 CSP다. 대개 손으로 짠 백트래킹 루프로 구현되어 있고, 문제가 커지면 그제서야 솔버를 찾게 된다.

10. 모델링이 알고리즘보다 중요하다[편집]

같은 문제를 어떻게 적느냐가 성능을 몇 자릿수 바꾼다.

대칭 깨기. $n$ -퀸의 해를 전부 세려는데 반사·회전 대칭이 있으면 같은 해를 8번 만난다. 변수 순서에 사전식 순서 제약을 걸어 대표 하나만 남기면 탐색 공간이 그만큼 줄어든다. 다만 대칭 깨기 제약이 전파를 방해해 오히려 느려지는 경우도 있어서, 이 판단은 실측이 필요하다.
중복 제약. 논리적으로는 다른 제약에서 따라 나오지만 전파에는 새 정보를 주는 제약을 일부러 추가한다. 마방진에 “각 행의 합”만 걸어 두는 대신 “전체 합”까지 명시하면 전파가 훨씬 빨리 모순을 잡는다. 수학적으로 잉여인 것을 일부러 넣는다는 점이 처음엔 어색하지만, 전파는 논리적 함의가 아니라 국소적으로 볼 수 있는 것만 쓰기 때문에 이게 통한다.
관점과 채널링. 같은 문제를 “각 여왕이 어느 행인가”로도, “각 행에 어느 여왕이 있나”로도 적을 수 있다. 두 모델을 동시에 두고 채널링 제약( $x_i = j \Leftrightarrow y_j = i$ )으로 이으면, 각 관점에서 강한 전파가 서로에게 전달된다. 변수가 두 배로 늘어나는데도 이득인 경우가 흔하다.

한 줄로 줄이면 이렇다. CSP에서 성능은 대체로 솔버가 아니라 모델이 만든다. 좋은 모델은 전파가 잘 먹히도록 구조를 드러내 놓은 모델이고, 그래서 전역 제약 카탈로그를 아는 것이 알고리즘 논문을 읽는 것보다 실무에서 더 자주 값을 한다.³

11. 관련 문서[편집]

Régin, J.-C. (1994). “A filtering algorithm for constraints of difference in CSPs”. AAAI-94. 매칭 이론이 제약 프로그래밍에 들어온 결정적 순간으로 꼽힌다. 요점은 “제약 하나에 대해 그래프 이론을 통째로 동원하면 전파가 얼마나 세지는가”의 시연이며, 이후 전역 제약 논문의 국룰이 “일단 이 제약의 조합구조부터 찾자”가 됐다. ↩
Minton, S., Johnston, M. D., Philips, A. B., Laird, P. (1992). “Minimizing conflicts: a heuristic repair method for constraint satisfaction and scheduling problems”. Artificial Intelligence 58(1–3), 161–205. 원래 목적은 망원경 관측 스케줄링이었고 n-퀸은 사실상 부록의 시연이었는데, 교과서에 실린 것은 부록 쪽이다. 응용 논문의 흔한 운명. ↩
그래서 CP 커뮤니티에는 전역 제약을 종류별로 정리한 카탈로그가 따로 존재한다. 수백 개가 등재되어 있고, 새 문제를 만나면 알고리즘을 짜기 전에 “이거 이미 있는 제약 아닌가”를 먼저 뒤지는 것이 정석이다. 라이브러리 검색이 곧 알고리즘 설계인 몇 안 되는 분야. ↩