정수 계획법을 위한 자기회귀 미분 가능 방법
Autoregressive Differentiable Method for Integer Programming
한국어 초록
본 논문에서는 0-1 정수 계획법(0-1 integer programs) 문제를 해결하기 위한 자기회귀(autoregressive) 미분 가능 방법을 소개합니다. 이진 변수의 임의의 순서를 고정한 후, 실행 가능 영역(feasible set) 내에 머무르면서 다음 비트를 예측하도록 트랜스포머(transformer)를 학습시킵니다. 제안하는 방법은 먼저 임의의 솔버가 제공한 실행 가능한 초기 해(incumbent)를 바탕으로 학습되어 트랜스포머를 실행 가능 영역 내에서 초기화할 수 있도록 합니다. 이후 실행 불가능한 해에 페널티를 부여하기 위해 라그랑주 페널티(Lagrangian penalty)를 적용하며, 완화된 목적 함수에서 검벨-소프트맥스(Gumbel-softmax) 활성화 함수를 사용하여 트랜스포머가 실행 가능 영역을 탐색하도록 추가 학습을 진행합니다. 본 연구는 이차 배낭 문제(quadratic knapsack problem)의 비볼록(non-convex) 인스턴스에 대해 제안 방식을 테스트하였으며, 최대 10,000개의 이진 변수를 갖는 조밀한(dense) 문제에서 최고 수준의 오픈소스 솔버 대비 일관된 성능 향상을 입증했습니다. 특히, 이진 변수에서 트랜스포머의 연속 가중치로의 실질적인 변수 변환을 통해 완화된 목적 함수 지형의 장벽을 넘어설 수 있게 하는 터널링 효과(tunneling effect)와 유사한 현상을 실증적으로 보여줍니다.
원문 초록
We introduce an autoregressive differentiable method to solve 0-1 integer programs. We fix an arbitrary order of the binary variables and we train a transformer to predict the next bit while remaining in the feasible set. Our method is first trained on feasible incumbents provided by any solver, thus allowing us to initialize the transformer in the feasible set. Our procedure then implements a Lagrangian penalty to penalize infeasible solutions, and the transformer is further trained to explore the feasible set using Gumbel-softmax activations on the relaxed objective. We have tested our method on non-convex instances of quadratic knapsack problem and demonstrated consistent improvement upon state-of-the-art open-source solvers for dense problems up to 10,000 binary variables. In particular, we empirically demonstrate a phenomenon akin to a tunneling effect where the effective change of variables from binary variable to the continuous weights of the transformer that the method implements enables crossing barriers in the relaxed objective landscape.
제출 이력
확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
정수 선형 프로그램을 위한 정확한 데이터 기반 역최적화의 명시적 반복 복잡도
Explicit Iteration Complexity of Exact Data-Driven Inverse Optimization for Integer Linear Programs
데이터 기반 역최적화 문제(DDIOP)는 관측된 최적해 데이터를 설명하는 목적 함수 매개변수(가중치)를 추정하는 문제이며, 정수 선형 프로그래밍(ILP)을 포함한 다양한 응용에서 발생한다. 알려진 바와 같이, 최적성 부족 손실(suboptimality loss)에 그래디언트 기반 최적화 방법을 적용하면 ILP의 역최적화를 유한한 수의 오라클 반복 내에서 정확히 풀 수 있으며, 필요한 반복 횟수는 문제에 따라 달라지는 기하 상수 $γ(\ell_{\mathrm{sub}})$에 대해 $T=O(1/γ(\ell_{\mathrm{sub}})^2)$로 상한이 주어진다. 그러나 $γ(\ell_{\mathrm{sub}})$를 문제 크기의 함수로 아래에서 제한하는 방법은 알려져 있지 않았으므로, 반복 횟수를 문제 크기의 명시적 함수로 제시할 수 없었다. 따라서 본 논문에서는 순방향 문제가 정수 선형 프로그램(ILP)일 때, 관측 데이터와의 정확한 일치를 달성하기 위해 최적성 부족 손실에 투영 부분그래디언트 하강(projected subgradient descent)을 적용하는 데 충분한 반복 횟수를, 표본 수, 특징(feature)의 차원, 특징의 범위, 제약 계수 행렬의 구조에 대한 완전히 명시적인 함수로 제시하며, 기본 상수(가중치 집합의 지름, 스텝 크기 매개변수, 최적성 부족 손실의 Lipschitz 상수)에 대한 다항식 인수까지 포함한다.
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)만 필요하게 한다.
Opti-Agent-Bench: 실제 비즈니스 문제에 대한 엔드투엔드 최적화 R&D 에이전트 벤치마킹
Opti-Agent-Bench: Benchmarking End-to-End Optimization R&D Agents on Real-World Business Problems
대규모 언어 모델(LLM) 기반 에이전트는 최적화 문제를 풀기 위해 점점 더 많이 활용되고 있으나, 기존 벤치마크는 사전 구조화된 수학적 공식을 대상으로 평가를 수행함으로써 가장 핵심적인 과제, 즉 복잡한 비즈니스 요구사항을 올바른 모델로 변환하고 효율적으로 풀어내는 과정을 생략하고 있다. 우리는 Opti-Agent-Bench를 소개한다. 이는 비즈니스 언어 설명 이해부터 수학적 모델링, 알고리즘 선택, 코드 구현, 그리고 솔루션 보고서 생성에 이르는 완전한 최적화 R&D 파이프라인 전반에 걸쳐 LLM을 평가하는 엔드투엔드 벤치마크이다. 본 설계는 세 가지 핵심 요소에 기반한다: (1) 패턴 매칭을 차단하는 안티 템플릿 트랩을 갖춘 비즈니스-의미론적 진정성; (2) 문제 이해, 형식적 모델링, 구현, 보고에 걸친 모듈 간 일관성 검사를 포함하는 모듈식 평가; (3) 과제 품질과 채점 무결성을 동시에 보장하는 ORAC 이중 수준 유효성 프레임워크. 정수 계획법, 강건 최적화, 확률적 프로그래밍, 비볼록 최적화를 아우르는 여러 산업 규모의 과제에 걸쳐, 우리는 제약 조건 누락, 모델-코드 불일치, 보고서-구현 간 괴리 등 기존의 단일 지표 평가에서는 드러나지 않는 현재 모델들의 치명적인 실패 유형을 규명한다.
적응형 컨테이너 추정을 통한 비정형 3D 객체의 미분 가능한 패킹
Differentiable Packing of Irregular 3D Objects with Adaptive Container Estimation
기존 접근법의 대부분은 컨테이너를 사전에 고정하거나 외부 탐색 루프를 통해 단일 컨테이너 차원만 최적화하여, 나머지 차원들을 수동 튜닝 문제로 남겨둔다. 본 논문에서는 단일 그래디언트 기반 루프 내에서 6N개의 객체 포즈 파라미터 전체와 세 컨테이너 변의 길이 전체를 공동으로 최적화하는 미분 가능한 패킹 프레임워크를 제안한다. 이 공식화는 축 정렬 경계 박스(axis-aligned bounding-box) 프록시를 통해 삼각형 메시에서 직접 계산되는 여섯 가지 물리 영감 미분 가능 손실 항을 결합한다. 적응형 압축 메커니즘은 중첩 손실이 쌍 수 기반 스케일 임계값 아래로 떨어질 때마다 주기적으로 컨테이너를 축소하여, 컨테이너 부피의 초기 대폭 감소에 이어 소폭의 반복 정제를 생성한다. 모든 쌍별 계산은 텐서 브로드캐스팅 형식으로 작성되어, 참조 루프 기반 구현 대비 3.4배에서 54배의 속도 향상을 제공한다. 파이프라인은 물리 엔진, FFT 라이브러리, 볼록 분해 없이 Python과 PyTorch로 구현된다. 여러 객체 카테고리에서, 본 방법은 N=100일 때 동일 시간 조건의 DBLF 및 시뮬레이티드 어닐링 베이스라인 대비 11~32% 더 작은 컨테이너를 생성하며, 단일 소비자용 GPU에서 인스턴스당 4분 이내로 실행된다.
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
토론
이 논문과 연결된 포럼 글이 아직 없습니다.