NuCS vs Choco: 순수 파이썬 제약 솔버, JVM 베테랑과 대결

Source: Towards Data Science

NuCS 는 100% 파이썬으로 작성된 제약 해결기이며, 제가 개발했으며, NumPy 와 Numba 로 가속됩니다. Choco 는 자바로 작성된 대표적인 오픈소스 제약 해결기 중 하나이며, 20년 넘게 개발되어 왔습니다.

두 솔버를 비교하면 한쪽은 인터프리터 언어, 다른 한쪽은 풍부한 아크-일관성 전역 제약 카탈로그를 갖춘 고도로 최적화된 JVM 해결기라는 불균형이 보입니다. 실제 상황은 더 흥미롭습니다. 두 솔버가 동일한 모델을 실행할 때, 실질적으로 동일한 속도를 보이며—가장 큰 인스턴스에서는 NuCS 가 실제로 앞서갑니다, 왜냐하면 Numba 가 내부 루프를 컴파일한 뒤에는 파이썬 오버헤드가 사라지고 노드당 비용만 남기 때문입니다. 모델이 달라지면 결과는 완전한 패배가 아니라 진정한 트레이드오프가 됩니다: 어떤 문제에서는 Choco 의 아크 일관성이 빠르고 올바른 도구이고; 다른 문제에서는 NuCS 의 저렴한 경계 일관성과 약간의 리모델링이 압도적으로 승리합니다; 그리고 최소 한 문제에서는 NuCS 의 모델링 자유도가 양쪽 솔버가 풀 수 없는 인스턴스를 해결하게 합니다.

이 글에서는 다섯 개의 벤치마크 문제를 살펴보고, 각 문제에 대한 정확한 NuCS 명령줄을 제시하며, 제약과 탐색 전략을 상세히 설명하고, 성능 곡선을 그린 뒤, 전체 그림을 설명하는 설계 결정을 제시합니다: NuCS 는 도메인을 min..max 구간으로 표현하므로 경계 일관성에만 제한되고, Choco 는 구멍이 있는 도메인도 표현할 수 있어 완전한 아크 일관성을 수행할 수 있습니다.

여기에 표시된 모든 NuCS 코드는 NuCS 저장소 의 MIT 라이선스 하에 제공됩니다.

NuCS

History

NuCS 는 제가 최근에 시작한 프로젝트입니다. 첫 공개 릴리스는 2024년에 이루어졌으며, 이후 매우 빠르게 진화했습니다—여기서 벤치마크한 버전은 11.2.0 입니다. 이 프로젝트는 의도적으로 이색적인 베팅을 중심으로 구축되었습니다: 전적으로 파이썬만으로 경쟁력 있는 유한 도메인 제약 해결기를 작성하고, C 혹은 C++ 코어 대신 JIT 컴파일을 통해 해석에 따른 성능 손실을 회복한다는 것이었습니다. PyPI(pip install nucs) 에 배포되어 설치가 다른 파이썬 패키지와 마찬가지로 간단합니다—네이티브 툴체인도, JVM 도 필요 없습니다.

Architecture

Problem 은 변수 도메인의 NumPy 배열을 보관합니다—변수당 하나의 (min, max) 쌍이며, min == max 일 때 변수가 바인드 된 것으로 간주합니다—그리고 propagator 리스트를 함께 가집니다. propagator 는 제약의 필터링 알고리즘이며, 숫자형 ALG_* 식별자로 등록됩니다. 각 propagator 는 세 개의 작은 함수로 구성됩니다:

• compute_domains_* — 실제 필터링을 수행하며 불일치, 일치, 혹은 엔테일먼트 를 반환합니다;
• get_triggers_* — 어떤 도메인 이벤트가 propagator 를 다시 깨워야 하는지 정의합니다;
• get_complexity_* — 전파 큐를 정렬하는 데 사용되는 비용 추정치입니다.

BacktrackSolver 는 전파를 고정점까지 진행한 뒤, 변수 휴리스틱 (어떤 바인드되지 않은 변수를 분기할지) 과 도메인 휴리스틱 (어떤 값을 시도할지) 으로 선택된 분기 결정을 교차시킵니다. MultiprocessingSolver 는 탐색 공간을 분할하여 여러 백트래킹 탐색을 병렬로 수행합니다.

파이썬임에도 불구하고 빠른 이유는 사실상 모든 핫 함수가 @njit(cache=True, fastmath=True) 로 데코레이트되기 때문입니다. Numba 가 처음 사용될 때 이 함수들을 네이티브 코드로 컴파일하고 결과를 디스크에 캐시하므로, 워밍 된 프로세스는 인터프리터 바이트코드가 아니라 컴파일된 머신 코드를 실행합니다. 도메인은 제자리에서 변형되는 순수 NumPy 배열이며, propagator 들은 타입이 지정된 NDArray 와 정수만 교환합니다—파이썬 객체는 절대 사용되지 않습니다. 비용은 (캐시 덕분에 완화된) 콜드 스타트 컴파일과 JIT 코드 내부에서의 코딩 규율(딕셔너리, 예외, isinstance, 문자열 사용 금지) 입니다. 얻는 이점은 두 가지: C 수준의 처리량, 그리고 저렴하고 빠른 모델링—불필요한 제약을 추가하거나, 휴리스틱을 교체하거나, 문제 특화 일관성 알고리즘을 작성하는 것이 일반 파이썬 몇 줄이면 충분합니다. 이 두 번째 특성이 NuCS 가 여러 차례 승리를 거두는 핵심입니다.

가장 중요한 설계 선택은 도메인이 언제나 구간이라는 점입니다. 도메인 중간에 구멍을 표현할 방법이 없으며, 이는 엔진 전체를 두 개의 NumPy 배열 연산으로 구현할 수 있게 하는 동시에 NuCS 를 경계 일관성에만 제한합니다. 이 점은 아래 결과들을 살펴볼 때 계속해서 등장합니다.

Choco

History

Choco 는 제약 프로그래밍 분야의 베테랑입니다. 2000년대 초에 처음 등장했으며 여러 차례 전면 개편을 거쳤습니다. 현대 라인—Choco 3, 4, 그리고 현재 6—은 주로 IMT Atlantique(프랑스 낭트의 TASC / LS2N 연구 그룹)에서 Charles Prud’homme, Jean‑Guillaume Fages 및 기여자들이 설계한 전면 재구성입니다. 오픈소스 자바 라이브러리이며 BSD 라이선스로 배포되고, 연구와 산업 현장에서 널리 사용됩니다. 여기서 벤치마크한 버전은 6.0.1 로, 최신 릴리스입니다.

Architecture

Choco 는 JVM 위에서 동작하는 이벤트 기반 제약 해결기입니다. Model 은 정수, 불리언, 집합, 실수 변수를 Constraint 와 함께 보관하며, 각 제약은 하나 이상의 propagator 로 필터링을 위임하고, 이들은 세밀한 이벤트/전파 엔진에 의해 구동됩니다. 그 위에 다양한 분기 전략, 재시작 정책, 그리고 설명(conflict‑based learning)이라는 독특한 기능을 갖춘 구성 가능한 탐색 루프가 존재합니다.

Choco 가 NuCS 와 근본적으로 다른 점은 도메인 표현입니다: 구간(경계) 도메인뿐 아니라 열거형 도메인(비트셋)도 지원해 임의의 부분집합—즉 구멍이 있는 도메인—을 표현할 수 있습니다. 이 풍부한 표현 덕분에 allDifferent(여러 일관성 수준, Régin 의 아크‑일관성 알고리즘 포함), 카디널리티·카운팅 제약, cumulative, circuit, 자동화/정규식 제약 등 방대한 전역 제약 카탈로그를 제공하며, 대부분은 정교하게 구현된 아크‑일관성 필터를 사용합니다.

성숙한 JVM 해결기는 오늘날 젊은 파이썬 프로젝트가 따라잡기 힘든 두 가지를 제공합니다: 20년 넘게 다듬어진 HotSpot JIT, 그리고 모델에 바로 끼워넣어 신뢰할 수 있는 강력한 전역 제약 라이브러리. 반면, 이러한 강력한 필터가 바로 비용이 되는 경우도 있습니다: 아크‑일관성 전역 제약은 노드당 많은 작업을 수행하며, 그 작업이 항상 비용 대비 효율을 보장하는 것은 아닙니다.

The comparison setup

몇 가지 솔직한 주의사항을 먼저 알려드립니다:

• 모든 측정값은 밀리초 단위이며 동일한 머신에서 측정되었습니다. 언어 간 마이크로‑벤치마크는 언제나 근사치이므로, 절대값보다 비율과 곡선 형태에 주목하세요.
• NuCS 측정은 Numba JIT 캐시가 워밍된 이후에 수행되었습니다—한 번 발생하는 컴파일 비용은 측정 대상이 아닙니다. 워밍된 상태에서도 NuCS 는 수백 밀리초 수준의 고정 시작 비용을 갖는데, 이는 가장 작은 인스턴스에서 바닥값으로 나타납니다. 이 비용은 프로