한국어 초록
대칭 의사 부울(PB) 제약이 있는 부울 만족성(SAT) 문제에 대한 해법으로 병렬 연속 국소 탐색(CLS)을 연구한다. 여기서 $n$변수 PB-만족성 문제는 $n$차원 하이퍼큐브 위의 미분 가능한 목적 함수를 갖는 연속 최적화 문제로 완화된다. 만족 가능한 인스턴스에 대해, 이 최적화 문제의 전역 최소화점은 해당 SAT 문제의 만족 대입에 대응한다. 실험을 통해 여러 새로운 발견을 제시한다: (i) 중복 제약은 수렴을 가속하기보다 오히려 저해할 수 있다; (ii) CLS는 하이브리드 설정에서 부분 대입을 빠르게 완성하는 부분 솔버(sub-solver)로서 유망하다; (iii) 추가 솔버 단계가 수익 체감을 낳는 안장점(saddle) 밀집 목적 함수로 인해, 국소 탐색은 해 품질(즉, 만족 정도)의 안정적인 분포에 빠르게 수렴한다. 이러한 결과는 현대 가속기 하드웨어에서 SAT를 위한 CLS의 실용적 활용에 대한 시사점을 제공한다.
원문 초록
We study parallel Continuous Local Search (CLS) as a solution approach for Boolean satisfiability problems with symmetric pseudo-Boolean (PB) constraints. Here, the $n$-variable PB-satisfiability problem is relaxed to a continuous optimisation problem with a differentiable objective function on an $n$-dimensional hypercube. For satisfiable instances, the global minimisers of this optimisation problem correspond to satisfying assignments of the SAT problem at hand. We present several novel findings via empirical experiments: (i) redundant constraints can inhibit rather than accelerate convergence; (ii) CLS shows promise as a sub-solver in hybridised settings, quickly completing partial assignments; and (iii) local search rapidly converges to a stable distribution of solution quality (i.e., degree of satisfaction), due to saddle-dense objectives where additional solver steps yield diminishing returns. Our findings inform practical uses of CLS for SAT on modern accelerator hardware.
제출 이력
확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.
- arXiv:2606.06656v1제출 시각 미확인
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
차량 경로 문제에서 유도 국소 탐색 학습을 위한 행동 기반 니칭 유전 프로그래밍
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 보정 후에도 유의하게 남는다. 이 결과는 평가된 설정 내에서 유용한 해 품질과 프로그램 크기 간의 트레이드오프를 밝히며, 크기 감소를 행동 표현만으로 귀인하지는 않는다.
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개 인스턴스에서는 유의미한 차이가 없었습니다.
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)만 필요하게 한다.
CayleyR: 순환 교집합을 통한 TopSpin 퍼즐 풀이
CayleyR: Solving the TopSpin puzzle via cycle intersection
cayleyR는 Cayley 그래프에서 순환 교집합을 탐지하여 순열 퍼즐을 풀기 위한 R 패키지입니다. 핵심 알고리즘은 반복적 양방향 탐색을 수행합니다. 초기 순열 상태와 목표 순열 상태 모두에서 무작위 연산 시퀀스가 대칭군 Sn의 Cayley 그래프에서 순환을 생성하며, 이들 순환의 교집합이 연결 경로를 제공합니다. 직접적인 교집합이 발견되지 않으면 거리 기반 브리지 선택이 간격을 좁히고, 이 과정이 반복됩니다. 이 패키지는 TopSpin(n,k) 퍼즐을 대상으로 하며, 그 상태 공간은 순환 시프트와 접두 반전으로 생성된 Sn의 Cayley 그래프입니다. 수학적 프레임워크, 알고리즘, 그리고 C++ 해시 인덱스 상태 저장소와 선택적 Vulkan GPU 가속을 결합한 구현을 설명합니다. 이 소프트웨어는 CRAN에서 공개적으로 이용할 수 있습니다.
교통 관리를 위한 비용 최적 파운데이션 모델 배포 포트폴리오
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 가격이 두 배로 오를 때만 합리적이 된다.
Prioritizing Search Space Regions in the Low Autocorrelation Binary Sequences Problem
낮은 자기상관 이진 수열 문제(LABS)는 통신, 신호 처리, 위성 항법 분야에서 중요한 응용을 갖는 어려운 조합 최적화 과제이다. 본 논문은 LABS 탐색 공간의 제한 클래스에 걸쳐 계산 노력을 적응적으로 배분하기 위해 Thompson 샘플링과 병렬 자기회피 보행(self-avoiding walk)을 결합한 하이브리드 탐색 프레임워크를 제안한다. 파티션을 다중 팔 밴딧(multi-armed bandit) 설정의 팔(arm)로 모델링함으로써, 제안된 방법은 덜 샘플링된 영역의 탐험(exploration)을 유지하면서도 경험적으로 더 높은 성능 지수(merit factor)를 산출하는 파티션 쪽으로 탐색 자원을 동적으로 전환한다. 이 접근법은 GPU 병렬 실행, 공유 사후 업데이트, 효율적인 이웃 평가, 그리고 사이클 방지를 위한 블룸 필터(Bloom filter)를 통해 추가로 가속된다. 또한 제약된 분할 비대칭 공간(partitioned skew-symmetric space)을 먼저 탐색한 후 비제약 공간에서 최적 후보를 정제하는 2단계 최적화 전략을 사용한다. 긴 이진 수열에 대한 실험 결과, 제안된 방법은 $450 \le L \le 527$ 범위의 35개 수열 길이와 $L=573$에 대해 이전에 알려진 최선의 결과를 개선하였다. 특히 $L=451$에서 성능 지수 8.0을 초과하는 새로운 최장 수열을 보고한다. 결과는 또한 Thompson 샘플링이 더 나은 관측 성능을 보이는 파티션을 효과적으로 우선시함을 보여주며, LABS 최적화에서 온라인 데이터 기반 자원 배분의 가치를 확인한다. 전반적으로 제안된 프레임워크는 고성능 성능 지수 최대화를 위한 확장 가능하고 효과적인 전략을 제공한다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.