arXiv:2509.04007v2 cs.AI

AutoPBO: 국소 탐색 PBO 해결기를 위한 LLM 기반 최적화

AutoPBO: LLM-powered Optimization for Local Search PBO Solvers

Yi Chu, Jinyuan Li, Yiwen Sun, Mengchuan Zou, Shaowei Cai

제출 2026-11-18

한국어 초록

유사 불리언 최적화(Pseudo-Boolean Optimization, PBO)는 유사 불리언(PB) 제약을 통해 조합 문제를 모델링하는 강력한 틀을 제공한다. 국소 탐색 해결기는 PBO 풀이에서 뛰어난 성능을 보였으며, 그 효율은 탐색을 이끄는 내부 휴리스틱에 크게 좌우된다. 그러나 이러한 휴리스틱의 설계에는 실제로 상당한 전문가의 노력과 수작업 조정이 필요한 경우가 많다. 대규모 언어 모델(LLM)이 알고리즘 설계 자동화에서 잠재력을 보여 왔지만, PBO 해결기 최적화에 대한 적용은 아직 탐구되지 않았다. 본 연구에서는 PBO 국소 탐색 해결기를 자동으로 향상시키는 새로운 LLM 기반 프레임워크인 AutoPBO를 제안한다. 실제 문제 벤치마크 하나, PB 대회 벤치마크 하나, 정수 선형 계획 최적화 벤치마크 하나, 직접 구성한 조합 벤치마크 하나를 포함한 네 가지 공개 벤치마크에서 실험을 수행하여 AutoPBO의 성능 향상을 평가하고, 이를 여섯 가지 최신 경쟁 해결기와 비교한다. 비교 대상은 국소 탐색 PBO 해결기 NuPBO와 OraSLS, 완전(complete) PB 해결기 PBO-IHS와 RoundingSat, 혼합 정수 계획(MIP) 해결기 Gurobi와 SCIP이다. AutoPBO는 기존 국소 탐색 방식보다 크게 향상된 성능을 보이면서도 최신 경쟁 해결기와 대등한 성능을 유지한다. 이 결과는 AutoPBO가 국소 탐색 해결기 설계를 자동화하는 유망한 접근임을 시사한다.

원문 초록

Pseudo-Boolean Optimization (PBO) provides a powerful framework for modeling combinatorial problems through pseudo-Boolean (PB) constraints. Local search solvers have shown excellent performance in PBO solving, and their efficiency is highly dependent on their internal heuristics to guide the search. Still, their design often requires significant expert effort and manual tuning in practice. While Large Language Models (LLMs) have demonstrated potential in automating algorithm design, their application to optimizing PBO solvers remains unexplored. In this work, we introduce AutoPBO, a novel LLM-powered framework to automatically enhance PBO local search solvers. We conduct experiments on a broad range of four public benchmarks, including one real-world benchmark, a benchmark from PB competition, an integer linear programming optimization benchmark, and a crafted combinatorial benchmark, to evaluate the performance improvement achieved by AutoPBO and compare it with six state-of-the-art competitors, including two local search PBO solvers NuPBO and OraSLS, two complete PB solvers PBO-IHS and RoundingSat, and two mixed integer programming (MIP) solvers Gurobi and SCIP. AutoPBO demonstrates significant improvements over previous local search approaches, while maintaining competitive performance compared to state-of-the-art competitors. The results suggest that AutoPBO offers a promising approach to automating local search solver design.

제출 이력

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

  1. arXiv:2509.04007v2제출 시각 미확인

함께 살펴볼 논문

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

공통 태그로 연결된 공개 논문이 아직 없습니다.

토론

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