대규모 파라메트릭 혼합 정수 프로그램을 위한 백도어, 머신러닝, 최적화의 융합
Fusing Backdoors, Machine Learning, and Optimization for Large-Scale Parametric Mixed-Integer Programs
한국어 초록
대규모 최적화 문제는 유사한 구조적 조건 하에서 반복적으로 풀리는 경우가 많아 상당한 계산 비용이 발생한다. 이는 전력 시스템, 교통, 공급망 네트워크와 같은 응용 분야에서 나타나며, 여기서 기저 구조는 고정되어 있는 반면 파라미터는 교란에 의해 빈번하게 변한다. 본 논문은 백도어(backdoor), 즉 대부분의 계산 복잡도를 결정하는 변수들의 부분집합 개념을 활용하여 대규모 일반 혼합 정수 문제의 풀이를 가속화하는 학습 기반 최적화(LTO) 프레임워크를 제안한다. 제안된 BIPC 프레임워크는 세 단계로 구성된다. 1단계는 분포 내 인스턴스 집합에 대한 백도어를 발견하는 식별 절차이다. 2단계는 지도 학습을 사용하여, 주어진 인스턴스에 대해 유계 도메인 백도어 변수의 값과 광역 도메인 백도어 변수의 구간을 예측하는 머신러닝 모델을 개발한다. 이 예측값은 백도어 변수를 제약하고 나머지 변수는 자유롭게 두는 축소된 최적화 문제를 정의한다. 3단계는 이 축소된 문제를 최적화하고, 필요한 경우 실현 가능성 또는 최적성 보장을 복원하기 위한 보정 단계를 적용한다. 실제 대규모 문제에 대한 실험에서 풀이 품질의 제한적인 손실만으로 풀이 시간이 크게 단축됨을 보인다. 이 프레임워크는 예기치 않은 이벤트, 수요 변동, 운영 변화와 같은 빈번한 교란이 발생하는 상황에서 조직이 대규모 최적화 문제를 효율적으로 풀 수 있게 한다. 이러한 변화는 문제 구조가 아닌 파라미터에 영향을 미치므로, BIPC는 고품질의 실현 가능한 해를 신속하게 제공하여 머신러닝을 기존 최적화 파이프라인에 통합하는 실용적인 접근 방식을 제시한다.
원문 초록
Large-scale optimization problems are often solved repeatedly under similar structural conditions, leading to substantial computational overhead. This occurs in applications such as power systems, transportation, and supply chain networks, where the underlying structure is fixed while parameters frequently vary under perturbations. This paper proposes a Learning to Optimize (LTO) framework that accelerates the solution of large-scale general mixed-integer problems by leveraging the concept of a backdoor, i.e., a subset of variables that drive most of the computational complexity. The proposed BIPC framework consists of three phases. Phase I is an identification procedure that discovers a backdoor for a set of instances in the distribution. Phase II uses supervised learning to develop machine learning models that, given an instance, predict values for bounded-domain backdoor variables and intervals for wide-domain backdoor variables. These predictions define a reduced optimization problem where the predictions constrain the backdoor variables, while the other variables remain free. Phase III optimizes this reduced problem and, if necessary, applies a correction step to restore feasibility or the optimality guarantees. Experiments on real-world, large-scale problems show substantial reductions in solution time with only a limited loss in solution quality. The framework enables organizations to solve large-scale optimization problems efficiently in the presence of frequent perturbations, such as unexpected events, demand fluctuations, or operational changes. Because these changes affect parameters rather than the problem structure, BIPC can quickly provide high-quality, feasible solutions, offering a practical approach to integrating machine learning into existing optimization pipelines.
제출 이력
확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.
- arXiv:2606.21440v1제출 시각 미확인
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
분류 성능의 지표로서 라이프-유사 네트워크 오토마타 규칙의 형태 불규칙성
Shape irregularity of Life-Like Network Automaton rules as an indicator of classification performance
복잡 네트워크(Complex Network, CN) 분류는 스케일 불변(scale-invariant)이면서도 계산적으로 효율적인 고수준의 구조적 특성화를 필요로 합니다. 라이프-유사 네트워크 오토마타(Life-Like Network Automata, LLNA) 기반 방법은 사전에 제공된 특징 없이도 창발적 시간 패턴을 활용하여 네트워크 기술자(descriptor)를 추출하는 흥미로운 방식을 제공하지만, 그 효과는 오토마타 전이 규칙의 선택이라는 높은 비용의 조합 최적화 문제로 인해 병목 현상을 겪습니다. 기존 연구들은 대규모 응용에 실현 불가능한 전수 탐색(exhaustive search)에 의존하는 반면, 본 연구는 규칙 공간이 LLNA 전이 함수와 톱니 형태의 유사성을 정량화하는 '들쭉날쭉함(jaggedness)'이라는 특성으로 근본적으로 구조화되어 있음을 밝힙니다. 우리는 이 지표가 혼돈성(chaoticity)과 민감도(sensitivity)에 대한 이론적 대리 지표로 작용함을 입증하며, 이러한 특성은 네트워크 범주 간의 식별력 있는 동적 동작을 생성하는 데 필수적입니다. 나아가, 우리는 들쭉날쭉함을 활용하여 규칙 선택을 유도하는 휴리스틱 탐색 전략을 도입합니다. 실험 결과에 따르면 본 접근법은 전수 탐색 방식에 비해 계산 오버헤드를 90% 줄이면서도 전역 최적값 대비 5% 이내의 분류 정확도를 달성합니다. 우리의 발견은 패턴 인식을 위한 오토마타 기반 방법을 최적화하는 새롭고 효율적인 프레임워크를 제공합니다.
혼합 정수 선형 및 비선형 프로그래밍에서의 자동 연구
Autoresearch in Mixed-Integer Linear and Nonlinear Programming
자동 연구(autoresearch)의 최근 발전에도 불구하고, 전형적으로 NP-난해(NP-hard) 혼합 정수 선형 또는 비선형 프로그램(MILP 또는 MINLP)으로 공식화되는 실제 운영 연구(operations research) 문제에 이를 적용하는 것은 여전히 어렵습니다. 효과적인 연구를 위해서는 상충하는 아이디어들과 장기적(long-horizon) 실험 궤적을 체계적으로 관리해야 하기 때문입니다. 본 논문에서는 아이디어 풀링(pooling)과 알고리즘 트리 탐색을 통해 혼합 정수 프로그래밍에서 장기적 자동 연구를 체계화하는 재사용 가능한 에이전트(agent) 스킬인 AutoMIP을 소개합니다. AutoMIP은 상호보완적인 후보 아이디어들의 지속적인 풀을 유지하는 동시에 실행 가능한 실험들을 알고리즘 트리로 구성하여, 에이전트가 탐색되지 않은 가설을 보존하고 유망한 알고리즘을 개선하며 과거 상태를 기반으로 대안적 방법론 방향으로 전환할 수 있도록 지원합니다. MILP 및 MINLP 벤치마크(benchmark) 코호트에서 AutoMIP은 평가된 자동 연구 프레임워크 중 가장 높은 최종 성공률을 달성했습니다. MIPLib에서 AutoMIP은 60개 인스턴스 중 31개에서 새로운 최적해를 발견하여 기존 자동 연구 프레임워크를 능가했습니다. MINLPLib에서는 60개 인스턴스 중 52개에서 새로운 최적해를 달성했습니다. 절제 연구(ablation study)는 아이디어 풀링과 알고리즘 트리 탐색의 상호보완적 기여를 추가로 입증하며, 장기적 자동 연구를 위해 다양한 연구 아이디어와 구조화된 실험 궤적을 함께 유지하는 것의 중요성을 강조합니다.
JOVE: 자원 인지형 LLM 태스크 그래프를 위한 공동 실행 및 검증
JOVE: Joint Execution and Verification for Resource-Aware LLM Task Graphs
복잡한 추론 질의는 방향성 비순환 그래프(DAG) 형태의 태스크 그래프로 분해되어 이종 대규모 언어 모델(LLM)에 분산될 수 있으며, 이를 통해 병렬 처리를 통한 지연 시간을 줄이고 더 작은 모델이 복잡한 태스크를 해결하도록 지원할 수 있습니다. 그러나 실제로는 주어진 서브태스크에 대한 특정 LLM의 적합성을 사전에 알 수 없을 수 있으며, 단순 실행만으로는 출력의 정확성을 파악할 수 없습니다. 본 논문에서는 실행기 LLM을 할당하는 동시에 유료 검증을 거칠 중간 출력을 함께 선택하는 온라인 프레임워크인 JOVE를 제안합니다. 검증은 비동기식으로 실행되며 향후 할당 결정을 개선하는 데 사용되므로, 시스템은 현재 실행에 드는 비용과 향후 학습을 위한 지출 사이의 균형을 유지해야 합니다. 본 연구에서는 확률적이며 초기에는 알려지지 않은 LLM 서비스 품질, 호출 비용 및 실행 시간 환경에서 장기 예산과 질의별 지연 시간 제약 조건 하에 이러한 트레이드오프를 최적화하는 방법을 연구합니다. JOVE는 질의별 일련의 혼합 정수 선형 계획법(MILP) 문제를 해결하여 실행 및 검증 결정을 내립니다. 온라인 학습은 검증 피드백을 기반으로 LLM 품질에 대한 태스크 의존적 추정치를 업데이트하며, 정보 이득 보너스를 통해 학습의 가치를 할당 결정에 반영합니다. 자연스러운 일련의 가정 하에 본 연구는 JOVE의 준선형(sublinear) 품질 학습 후회(regret)를 입증합니다. 4가지 추론 벤치마크 전반에서 JOVE는 표준 추론(inference) 베이스라인 대비 경쟁력 있는 정확도를 달성하는 동시에 평균 비용과 지연 시간을 최소 3.17배 단축합니다.
확산과 규모: 테스트-시간 예산 할당의 효용성을 결정하는 요인은 무엇인가
Spread and Scale: What Determines Whether Test-Time Budget Allocation Pays
신경 조합 최적화(Neural combinatorial optimization) 솔버는 난이도와 무관하게 모든 문제 인스턴스에 동일한 샘플 예산을 사용하여, 인스턴스당 여러 후보 해를 생성하고 그중 발견된 최선의 해를 보고합니다. 한 후속 연구에서는 고정된 예산을 더 어려운 인스턴스에 재할당함으로써 해의 품질을 향상할 수 있음을 보여주었으나, 이러한 개선을 측정하는 표준 방식에 편향이 존재함을 지적했습니다. 즉, 동일한 데이터에서 할당을 결정하고 평가하면 실제로는 이득이 없음에도 겉보기에 이득이 있는 것처럼 만들어낼 수 있다는 것입니다. 이로 인해 워크로드의 어떠한 특성이 재할당을 수행할 가치가 있는지를 결정하는지, 그리고 나머지 예산의 할당 방식을 결정하기 위해 예산의 일부를 소비하는 정책이 해당 비용을 감안한 후에도 여전히 유효한지(pays)에 대한 의문이 미해결 상태로 남았습니다. 본 논문은 외판원 문제(traveling salesman problem)에 대해 독립적으로 학습(training)된 세 가지 솔버와 더 어려운 워크로드를 구성하는 두 가지 방식을 대상으로, 데이터 수집 전에 분석 및 판정 기준을 확정한 사전 등록 확인 실험(pre-registered confirmatory experiments)을 통해 두 질문에 모두 답합니다. 우리가 연구한 워크로드 내에서 결정적인 특성은 워크로드의 평균 난이도가 아니라 워크로드 내 인스턴스들의 난이도가 얼마나 다양한지 여부입니다. 균일하게 쉽거나 균일하게 어려운 워크로드는 재할당의 여지가 거의 없는 반면, 난이도가 혼합된 워크로드는 상당한 여지를 제공합니다. 인스턴스 난이도에 대한 정보를 얻기 위해 자체 비용을 지불하는 예산 인식 정책은, 해당 정보가 무료라고 가정했을 때 얻을 수 있는 개선의 전부는 아니지만 대부분을 회수합니다. 모든 실험은 작성된 명세에 따라 독립적으로 재계산되었으며, 논문 자체의 주장을 약화시킨 두 가지 수정을 포함하여 이전 버전에 대한 모든 수정 사항은 결론이 바뀐 방향과 함께 보고됩니다. 본 논문은 구체적인 실증적 해답과 함께, 해당 해답이 측정 방식에 의해 발생한 인위적 결과(artifact)가 아님을 검증하기 위한 템플릿을 제공합니다.
잡 샵 스케줄링을 위한 GNN 기반 강화학습에서의 커리큘럼 러닝
Curriculum Learning with GNN-based Reinforcement Learning for Job Shop Scheduling
잡 샵 스케줄링 문제(job shop scheduling problem)는 까다로운 조합 최적화(combinatorial optimization) 문제이며, 최근 그래프 신경망(GNN)을 활용한 강화학습(RL) 접근법은 문제 인스턴스로부터 스케줄링 정책을 직접 학습하는 데 유망함을 보여주었다. 그러나 대규모 인스턴스에 대한 학습은 여전히 연산 비용이 많이 들고, 다양한 인스턴스 크기에 걸친 일반화는 여전히 어려운 과제로 남아 있다. 본 논문에서는 잡 샵 스케줄링 문제에서 그래프 신경망 기반 강화학습을 위한 커리큘럼 러닝(curriculum learning)을 연구하며, 세 가지 타깃 크기인 20 x 20, 25 x 25, 30 x 30에 대해 단일 크기 학습(single-size training)과 비교한다. 커리큘럼 환경에서는 정책을 먼저 더 작은 인스턴스에서 학습시킨 후 점진적으로 더 큰 타깃 크기에 적응시켜, 초기 단계에서 학습된 스케줄링 동작이 더 큰 인스턴스에서의 학습을 뒷받침하도록 한다. 모델은 모든 평가 크기에 걸친 일반화와 타깃 크기에 대한 특화(specialization)를 모두 고려하여, 최적성 갭(optimality gap)을 사용해 8 x 8부터 30 x 30까지의 미확인(unseen) 인스턴스에서 평가된다. 실험 결과에 따르면 커리큘럼 러닝은 실제 학습 소요 시간(wall-clock training time)을 일관되게 단축하며, 타깃 크기가 커질수록 그 이점이 더 커지는 것으로 나타났다. 가장 강력한 이점은 30 x 30에서 관찰되었는데, 커리큘럼 러닝은 모든 평가 크기에 걸친 평균 최적성 갭을 약 8.1%포인트 줄이고, 타깃 크기의 평균 최적성 갭을 약 8.6%포인트 줄였으며, 학습 시간을 약 50시간 절약했다.
재해결 없이 온라인 선형 계획을 위한 자원 적응형 확률적 경사하강법
Resource-Adaptive Stochastic Gradient Descent for Online Linear Programming without Re-solving
대규모 언어 모델(LLM) 추론과 검색 서비스의 확대는 온라인 선형 계획 문제의 규모를 키우며, 계산적으로 효율적인 알고리즘을 요구한다. 본 연구는 확률적 온라인 선형 계획을 위한 자원 적응형 확률적 경사하강법(RASGD)을 제안한다. 이 알고리즘은 요청 하나와 현재 재고(inventory)만으로 자원 가격을 갱신하며, 자원 m개에 대해 도착(arrival)마다 O(m) 연산과 메모리만 필요하고 LP나 표본 평균 최적화(sample-average optimization)는 사용하지 않는다. 핵심은 재해결(re-solving)에서 쓰이는 현재 자원 가격 책정 로직을 1차 SGD 갱신으로 표현하는 것이다. 각 도착마다 이중 목적(dual objective)의 잔여 재고 허용량(allowance)을 갱신하고, 스텝 크기(stepsize)는 초기에는 학습을 위해 작아지다가 이후에는 재고 조정 속도에 맞추어 커진다. 표준 비퇴화(non-degeneracy) 조건 하에서 알고리즘은 모든 표본 경로(sample path)에서 실행 가능(feasible)하며, 실현된 분수적 후견 최적(realized fractional hindsight optimum) 대비 O(\log T) 기대 후회(expected regret)를 달성한다. 이는 분포를 알고 계산 제약이 없는 정책에 대한 하한과 일치한다. 분석은 변화하는 자원 수준에서 최적 가격을 추적하지 않고, 고정 참조 가격 주변의 곡률(curvature)을 재고 안정성(inventory stability)으로 전환한다. 수치 실험에서 RASGD는 도착마다 LP 재해결과 견줄 만한 후회를 달성하고, 시험한 1차 기준선(first-order baselines)보다 나으면서 1차 방법의 계산 효율은 유지한다. 이 결과는 RASGD가 대규모 OLP에서 높은 할당 품질을 계산 효율적으로 달성하는 접근임을 보여준다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.