입력 데이터와 양성 및 음성 예시 해로부터 크기 독립적 제약 모델 학습
Learning Size Independent Constraint Models from Input Data and Positive and Negative Example Solutions
한국어 초록
본 논문에서는 여러 문제 인스턴스의 입력 데이터와 양성 및 음성 예시 해로부터 크기 독립적인 제약 프로그램을 생성하는 제약 획득 도구(Constraint Acquisition Tool)를 설명한다. 이 시스템은 전역(global) 및 이진(binary) 제약에 대한 일반적인 제약 패턴을 기반으로 크기 특정 모델을 찾은 후, 이를 일반화하여 보지 못한 입력 데이터에서도 실행할 수 있는 크기 독립적 모델로 만든다. 이 시스템은 모델에 대한 텍스트 설명뿐만 아니라 MiniZinc 코드도 생성한다. 우리는 PTHG21 챌린지의 예제 문제들에 대해 이 도구를 평가하여 접근 방식의 실현 가능성을 보여준다.
원문 초록
In this paper we describe a Constraint Acquisition Tool that generates size independent constraint programs from input data and positive and negative example solutions of multiple problem instances. The system finds size specific models based on typical constraint patterns over global and binary constraints, then generalizes the models to a size independent model that can be run on unseen input data. The system produces MiniZinc code as well as a textual description of the model. We evaluate the tool on the example problems of the PTHG21 Challenge and show the feasibility of the approach.
제출 이력
확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
Learn2Zinc: MiniZinc에서의 텍스트-모델 변환을 위한 소형 언어 모델 미세조정
Learn2Zinc: Fine-tuning Small Language Models for Text-to-Model Translation in MiniZinc
대규모 언어 모델(LLM)은 주류 프로그래밍 언어에 대한 코드 생성에는 뛰어나지만, 조합 문제를 위한 제약 모델링 언어인 MiniZinc와 같은 희귀하고 도메인 특화된 언어에서는 어려움을 겪는다. 우리는 표적 미세조정이 소형 언어 모델(0.6B~20B 파라미터)에게 자연어 문제 설명으로부터 구문적으로 올바르고 의미적으로 유효한 MiniZinc 모델을 생성하도록 가르칠 수 있는지 조사한다. 핵심 발견은 이 도메인 특화 언어를 다룰 때 구문 오류가 실패를 지배한다는 것이다: Qwen3, LLaMa, Gemma, GPT-OSS와 같은 소형 언어 모델의 기본(out-of-the-box) 실행 정확도는 거의 0에 가깝다. 우리는 여러 LLM 실행에서 구문 오류를 수집하고 이를 활용해 오류 수정 학습 데이터셋을 구축하는 교차 모델 오류 부트스트래핑 접근법을 제안한다. 이 데이터셋을 통해 모든 모델 크기에 걸쳐 직접 코드 생성과 사고의 연쇄(Chain-of-Thought) 접근법 모두를 일관되게 개선하는 소형 언어 모델을 미세조정할 수 있다. 자기 성찰(self-reflection)과 앙상블링(ensembling)을 통해 우리 접근법은 최대 98% 실행 정확도를 달성한다. 한편, 해법 정확도는 여전히 35%에 머물러, 구문은 학습 가능하지만 제약 추론은 여전히 과제로 남아 있음을 시사한다. 우리는 텍스트-모델 변환에 대한 추가 연구를 위해 미세조정 파이프라인, 데이터셋, 모델을 오픈소스로 공개한다.
제약 프로그래밍을 위한 전역 차분 제약 전파
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)하는 방법을 제시한다. 차분 제약을 전역적으로 처리하면 표준 전파 접근법보다 상당히 개선될 수 있음을 보여주는 실험 결과를 제시한다.
EZSMT Version 3, 성숙화
EZSMT Version 3, Matured
제약 답 집합 프로그래밍(CASP)은 답 집합 프로그래밍(ASP)과 제약 처리 및 이론 모듈 만족가능성(SMT)을 결합한 하이브리드 추론 패러다임으로, 복잡한 조합 탐색 문제에 대한 강력한 선언적 인코딩을 가능하게 한다. 본 논문은 CASP 해결의 번역적 접근 방식을 발전시키는 확장 가능한 SMT 기반 CASP 프레임워크인 EZSMTV3의 설계와 구현을 제시한다. EZSMT+ 시스템의 기반 위에 구축된 EZSMTV3는 보다 표현력 있는 입력 언어를 도입하고, 약제약(weak constraints)을 통한 최적화를 지원하며, 새로운 제약 유형의 원활한 통합을 위한 기반을 제공한다. EZSMTV3는 사용자 정의 탐색 절차를 구현하는 대신 CVC5, YICES, Z3와 같은 최첨단 SMT 솔버를 활용하여 추론을 수행한다. 본 논문은 EZSMTV3를 CLINGCON, CLINGO[DL], CLINGO[LP] 등 CASP 동료 시스템과 비교한 벤치마크 결과를 제공하며, 정수와 실수를 모두 포함하는 혼합 영역 제약을 처리할 수 있는 능력을 보여준다. 이 시스템은 CASP 영역 내에서 향후 확장 및 이론적 탐험을 위한 견고한 플랫폼을 제공한다.
CP-WSP: 설정 가능한 다중 제약 인력 스케줄링을 위한 선언형 CP-SAT 프레임워크
CP-WSP: A Declarative CP-SAT Framework for Configurable Multi-Constraint Workforce Scheduling
인력 스케줄링은 노동 규정, 커버리지 요구사항, 직원 선호도, 운영 목표를 동시에 만족해야 하는 NP-난해 조합 최적화 문제다. 기존 CP 공식화는 일반적으로 교대 수준 세분성에서 6~12개의 제약 조건을 가진 단순화된 인스턴스를 모델링하며, 다음에 대한 명시적 지원이 결정적으로 부족하다: 중점 배치 제어를 갖춘 필수 휴식 스케줄링, 중증도 가중 업무 부담 형평성, 수요 기반 인력 배치를 가능하게 하는 교대 내 시간 세분성, 주간(週間) 스케줄 안정성, 24시간 운영에서 흔한 자정 초과 교대 패턴. 본 논문은 CP-WSP를 제시한다: 14개의 하드 제약 조건을 수학적으로 위반 불가능한 요구사항으로 강제하고(구조적으로 규정 위반 제로), 통합 가중 패널티 함수를 통해 15개의 소프트 목표를 최적화하는 선언형 CP-SAT 프레임워크로, 코드 변경 없이 JSON 명세를 통해 모두 설정 가능하다. 주요 기여는 다음과 같다: 중심성 제어를 갖춘 필수 휴식 스케줄링을 가능하게 하는 교대-윈도우 변수 분해, 중증도 가중 업무 부담 형평성, 30분에서 2시간까지의 다중 세분성 시간 해상도, 주간 스케줄 안정성, 자정 초과 교대를 위한 그리드-오프셋 전처리 기법, 커뮤니티 비교를 위한 재현 가능한 36개 설정 벤치마크 스위트. 시간별 및 교대 수준 세분성 모두에서 INRC-II 벤치마크와 36개 합성 설정에 대해 평가되었다.
MMAO: 연속 및 이산 최적화를 위한 내인성 자원 할당 기반 대사적 다중 에이전트 옵티마이저
MMAO: A Metabolic Multi-Agent Optimizer with Endogenous Resource Allocation for Continuous and Discrete Optimization
Minimal MMAO: 적응형 메타휴리스틱 탐색을 위한 자원 폐쇄 루프 프레임워크
Minimal MMAO: A Resource-Closed-Loop Framework for Adaptive Metaheuristic Search
토론
이 논문과 연결된 포럼 글이 아직 없습니다.
저자 비고
arXiv Comments
19 pages