arXiv:2606.06641v1 cs.AI

가속 푸리에 SAT (AFSAT): GPU 기반 대칭 의사-불리언 SAT 솔버의 완전한 구현

Accelerated Fourier SAT (AFSAT): Fully Realising a GPU-based Symmetric Pseudo-Boolean SAT Solver

Cody J Christopher, Charles Gretton

제출 2026-06-04

한국어 초록

본 논문에서는 연속 지역 탐색(CLS)을 기반으로 한 의사-불리언 만족가능성(pseudo-Boolean satisfiability)을 위한 GPU 가속 솔버인 Accelerated Fourier SAT (AFSAT)를 제안한다. AFSAT는 개념 증명 수준의 접근 방식인 FastFourierSAT를 단일 문제 인스턴스 내에서 대칭 제약 유형과 길이의 임의적인 이종 혼합을 지원하는 완전히 공학적으로 구현된 솔버로 발전시킨다. JAX 컴파일러를 활용하여 AFSAT는 순수 함수 합성, 자동 벡터화, 자동 미분, 그리고 JIT(just-in-time) 컴파일을 통해 후보 할당의 배치 전체에 걸쳐 대규모 병렬 CLS를 수행한다. 메모리 지연 및 부동소수점 표현에서 발생하는 다양한 한계를 식별하고 해결하는 동시에 자동 병렬화 및 컴팩트 표현을 활용함으로써, 개념 증명 대비 수치 안정성, 실행 시간 성능, 메모리 효율성을 크게 향상시켰다. 부동소수점의 본질적인 표현 및 안정성 한계는 맞춤형 이산 푸리에 변환(DFT) 구현을 통해 부분적으로 해소된다. JAX 배열 샤딩을 통해 다중 가속기로 확장 시 거의 선형에 가까운 처리량을 달성한다.

원문 초록

We present Accelerated Fourier SAT (AFSAT), a GPU-accelerated solver for pseudo-Boolean satisfiability based on continuous local search (CLS). AFSAT realises the proof-of-concept approach, FastFourierSAT, into a fully-engineered solver supporting any heterogeneous mixture of symmetric constraint types and lengths within a single problem instance. Using the JAX compiler, AFSAT leverages pure function composition, automatic vectorisation, automatic differentiation, and just-in-time (JIT) compilation to perform massively parallel CLS across batches of candidate assignments. We demonstrate substantially improved numerical stability, runtime performance, and memory efficiency over the proof-of-concept. We achieve this by way of identifying and addressing various limitations that arise from memory latency and floating-point representation, as well as leveraging automatic parallelisation and compact representations. The inherent representational and stability limitations of floating point are partially addressed by a tailored discrete Fourier transform implementation. We achieve near-linear throughput when scaling to multiple accelerators via JAX array sharding.

제출 이력

확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.

  1. arXiv:2606.06641v1제출 시각 미확인

함께 살펴볼 논문

공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.

arXiv:2609.24104v1cs.NE공통 태그 Combinatorial Optimization, local search

차량 경로 문제에서 유도 국소 탐색 학습을 위한 행동 기반 니칭 유전 프로그래밍

Genetic Programming with Behaviour-based Niching for Learning Guided Local Search in Vehicle Routing Problems

유전 프로그래밍 유도 국소 탐색(GPGLS)은 차량 경로를 위한 국소 탐색을 유도하는 효용 함수를 학습한다. 진화하는 프로그램은 서로 다른 탐색 행동을 유발하면서 유사한 적합도를 가질 수 있어, 적합도만으로는 개체군 다양성 관리의 불완전한 기준이 된다. 우리는 국소 탐색 중 수집된 여섯 가지 연산자 수준 기술자로 프로그램을 특성화하는 행동 기반 니칭 GPGLS(BN-GPGLS)를 제안한다. 현 세대 아카이브는 행동 점수의 층에서 적합도 경쟁력이 있고 compact한 대표를 선정한다. 고정 정책은 아카이브 부모를 지속적으로 사용하는 반면, 적응형 정책은 학습 적합도와 표준화된 행동 분산 신호를 사용하여(선택적으로 트리 크기 조건과 함께) 이를 활성화한다. 우리는 생성된 200-고객 인스턴스에서 30회 시드 매칭 실행에 걸쳐 아카이브 없는 GPGLS 대조군 및 적합도 기반 니칭과 네 가지 행동 기반 변형을 비교한다. BN-Adaptive는 별도의 90-인스턴스 모니터링 세트에서 최고의 평균 순위를 달성한다; 집계된 경로 비용 차이는 작다. 다섯 가지 아카이브 정책 모두 GPGLS 대조군보다 낮은 최종 개체군 중앙값 트리 크기를 산출하며, 쌍체 Wilcoxon 비교는 Holm 보정 후에도 유의하게 남는다. 이 결과는 평가된 설정 내에서 유용한 해 품질과 프로그램 크기 간의 트레이드오프를 밝히며, 크기 감소를 행동 표현만으로 귀인하지는 않는다.

arXiv:2609.24105v1cs.NE공통 태그 Combinatorial Optimization, local search

DCL-GPGLS: 대규모 차량 경로 문제를 위한 유전 프로그래밍 유도 국소 탐색 기반 동적 커리큘럼 학습

DCL-GPGLS: Dynamic Curriculum Learning for Genetic Programming Guided Local Search in Large-Scale Vehicle Routing

유전 프로그래밍 유도 국소 탐색(GPGLS)은 대규모 차량 경로 문제(LSVRP)의 유도 국소 탐색에 사용할 효용 함수(utility function)를 진화시키기 위해 유전 프로그래밍을 활용합니다. 매 세대마다 모든 학습(training) 인스턴스에 걸쳐 모든 GP 개체를 평가(evaluation)하는 것은 비용이 많이 들기 때문에, GPGLS는 통상적으로 작은 인스턴스 배치(batch)로 학습됩니다. 기존의 커리큘럼 기반 GPGLS는 주로 인스턴스 크기에 따라 이러한 배치의 순서를 정합니다. 적응형 커리큘럼 학습 GPGLS(ACL-GPGLS)는 고정된 커리큘럼 단계 간 이동 시점을 조정하여 학습 효율을 개선하지만, 인스턴스 난이도 순서는 여전히 사전에 정의된 상태로 유지됩니다. 본 논문에서는 현재 모집단(population)의 해 품질을 바탕으로 각 학습 인스턴스의 난이도를 추정하고 진화 과정 동안 이를 업데이트하는 DCL-GPGLS를 제안합니다. 이후 각 세대는 계획된 난이도 수준에 근접한 배치를 전달받으며, 동일 인스턴스의 반복 선택을 제한하는 보정이 함께 적용됩니다. CVRPLIB X 세트의 고정된 학습-테스트 분할에 대한 실험 결과, DCL-GPGLS는 6가지 학습 정책 중 가장 우수한 평균 순위와 평균 테스트 비용을 달성함을 보여줍니다. 또한 65개의 미확인(unseen) 테스트 인스턴스 중 36개에서 가장 낮은 평균 비용을 기록했으며, 총 평가자 호출 횟수가 동일한 정적 피드백 기반 커리큘럼과 비교했을 때 6개 인스턴스에서 유의미하게 우수했고 나머지 59개 인스턴스에서는 유의미한 차이가 없었습니다.

arXiv:2607.21354v1cs.AI공통 태그 GPU, Combinatorial Optimization

SPORD: 공급망 계획을 위한 Simulation-Propose-then-OR-Dispose 접근법

SPORD: A Simulation-Propose-then-OR-Dispose Approach for Supply Chain Planning

수년간 이커머스 기업의 공급망 계획은 서로 분리된 프로젝트들의 모음 형태로 운영되어 왔다. 정적 네트워크 계획부터 동적 창고 품목 구성(assortment) 계획에 이르는 각 계획 업무는 분석가들이 처음부터 모델을 구축하고, 보정하고, 검증할 수 없는 결과물을 바탕으로 경영진을 설득하여 실행에 옮기도록 하는 데 수주가 걸리게 한다. 이를 야기하는 세 가지 장벽이 있다: 표준화가 어렵기 때문에 맞춤형 모델이 난립한다(운영 분절); 일단 통합되면 수백만 SKU, 수천 개 노드, 복잡한 라우팅 로직이라는 조합적 규모가 솔버가 짧은 시간 창 내에 처리할 수 있는 범위를 초과한다(계산적 난해성); 수학적으로 최적의 해도 경영진이 신뢰하지 않으면 실행되지 못한다(실행 장벽). 이 격차를 메우기 위해 JD.com의 NetSim 플랫폼으로 배포된 Simulation-Propose-then-OR-Dispose(SPORD) 방법을 제안하고 구현했다. 핵심 통찰은 분리(decoupling)이다: 시뮬레이션이 모든 고유한 비즈니스 로직을 흡수하면서 운영상 유효한 후보 경로의 전체 집합을 생성하고 평가하여 제안(propose)하고, 정수 계획(integer program)이 전역적으로 최적인 부분집합을 선택하여 처리(dispose)한다. 계산 측면에서 행렬-벡터화 CPU/GPU 가속 시뮬레이션은 순차 방식 대비 10~100배 속도 향상을 달성했고, 리스트 스케줄링 알고리즘은 결합 주문 처리를 수 시간에서 수 분으로 단축했다. 운영 측면에서 지능형 진단 엔진을 통해 폐루프(closed loop)를 구축했다. 2025년 이후 NetSim은 20,000개 이상의 공급업체에 대한 end-to-end 서비스를 최적화했고, 지역 간 이행(fulfillment)률은 6.1%에서 4.9%로 감소했으며, 월평균 탄소 감축량은 약 5,745 tCO2e이다. SPORD는 시뮬레이션을 모니터링에서 능동적 계획으로 전환한다. 투명한 출력은 회의적인 경영진을 적극적으로 참여하는 협력자로 바꾸고, 모듈형 아키텍처는 다음 계획 수립에 재구축이 아닌 구성(configuration)만 필요하게 한다.

arXiv:2607.20022v1cs.AI공통 태그 Combinatorial Optimization, sat solving

제약 프로그래밍을 위한 전역 차분 제약 전파

Global Difference Constraint Propagation for Constraint Programming

$x - y \leq d$ 형태의 차분 제약(difference constraints)은 최단 경로와의 연관성 때문에 만족(satisfaction)과 함의(implication)에 대한 효율적인 알고리즘이 잘 연구되어 있다. 그러나 유한 영역(finite domain) 전파 알고리즘은 일반적으로 이러한 알고리즘을 활용하지 않고, 각 차분 제약을 별도의 전파기(propagator)로 취급한다. 전파는 해결의 완전성(completeness)을 보장하지만 불필요하게 느릴 수 있다. 본 논문에서는 모든 차분 제약을 동시에 처리하는 (경계 일관(bounds consistent)) 전역 전파기를 구축하는 방법을 설명한다. SAT modulo theory(SMT) 솔버는 한동안 차분 제약에 대한 이론 솔버(theory solver)를 포함해 왔다. 차분 제약용 이론 솔버가 전역 차분 제약 전파기의 기반이 되지만, 전파기에 대한 요구사항은 상당히 다름을 보인다. 핵심적으로, lazy clause generation 솔버 내에서 사용하기 위해 전역 차분 제약 전파기에 의한 전파를 설명(explain)하는 방법을 제시한다. 차분 제약을 전역적으로 처리하면 표준 전파 접근법보다 상당히 개선될 수 있음을 보여주는 실험 결과를 제시한다.

arXiv:2607.13219v1cs.AI공통 태그 GPU, Combinatorial Optimization

CayleyR: 순환 교집합을 통한 TopSpin 퍼즐 풀이

CayleyR: Solving the TopSpin puzzle via cycle intersection

cayleyR는 Cayley 그래프에서 순환 교집합을 탐지하여 순열 퍼즐을 풀기 위한 R 패키지입니다. 핵심 알고리즘은 반복적 양방향 탐색을 수행합니다. 초기 순열 상태와 목표 순열 상태 모두에서 무작위 연산 시퀀스가 대칭군 Sn의 Cayley 그래프에서 순환을 생성하며, 이들 순환의 교집합이 연결 경로를 제공합니다. 직접적인 교집합이 발견되지 않으면 거리 기반 브리지 선택이 간격을 좁히고, 이 과정이 반복됩니다. 이 패키지는 TopSpin(n,k) 퍼즐을 대상으로 하며, 그 상태 공간은 순환 시프트와 접두 반전으로 생성된 Sn의 Cayley 그래프입니다. 수학적 프레임워크, 알고리즘, 그리고 C++ 해시 인덱스 상태 저장소와 선택적 Vulkan GPU 가속을 결합한 구현을 설명합니다. 이 소프트웨어는 CRAN에서 공개적으로 이용할 수 있습니다.

arXiv:2607.13239v1cs.AI공통 태그 GPU, Combinatorial Optimization

교통 관리를 위한 비용 최적 파운데이션 모델 배포 포트폴리오

Cost-Optimal Foundation Model Deployment Portfolio for Transportation Management

파운데이션 모델(foundation model)에는 대규모 언어 모델(LLM)과 비전-언어 모델(VLM)이 포함되며, 이상 탐지, 사고 보고, 여행자 정보 제공과 같은 교통 관리 센터(TMC) 업무에 점점 더 많이 사용되고 있다. 여러 이러한 모델을 TMC 기능 전반에 배포하는 것은 포트폴리오 질문을 제기한다: 각 기능에 어떤 모델이, 어떤 배포 모드로, 그리고 어떤 공유 하드웨어 예산 하에서 제공되어야 하는가? 우리는 이를 파운데이션 모델 배포 포트폴리오(FMDP) 문제로 공식화한다. 이는 공유 GPU 용량에 대해 기능별 품질, 지연 시간, 안전성 제약을 만족하면서 총 소유 비용(TCO)을 최소화하는 혼합 정수 프로그램이다. 0-1 배낭 문제로의 환원을 통해 이 문제가 NP-난해함을 증명하고, 다항 시간 탐욕적 휴리스틱을 제안한다. 다섯 가지 TMC 기능과 19개의 후보 (모델, 모드) 쌍을 포함한 예시 사례 연구에서, FMDP는 4개 기능을 오픈소스 API로, 오픈소스 모델이 품질 하한을 충족하지 못하는 1개 기능을 폐쇄형 API로 라우팅하는 혼합 포트폴리오를 식별하여 월 $34(가장 저렴한 실행 가능한 전체 폐쇄형 API 기준선 대비 97% 절감)의 비용을 산출한다. 손익분기 분석에 따르면, 온프레미스 GPU 투자는 시간당 약 309회의 비전 쿼리 이상이거나 API 가격이 두 배로 오를 때만 합리적이 된다.

토론

이 논문과 연결된 포럼 글이 아직 없습니다.