This research introduces novel algorithms designed to provide scalable constructive nerual solver to a wide range of combinatorial optimization (CO) problems. These problems, characterized by their NP-completeness and their relationship to the traveling salesman problem, present formidable computational hurdles when attempting to find efficient solutions. In recent years, constructive RL methods have demonstrated competitive performance in small-scale instances (fewer than 100 nodes) when compared to heuristic methods. Their effectiveness diminishes significantly as the problem size increases. because existing constructive methods lack the ability to scale effectively. To address this challenge, our research aims to incorporate inductive bias during both the training and testing phases. Our research encompasses two main topics, namely, Meta-SAGE and Equity-Transformer. Firstly, our approach harnesses pre-trained models to handle larger-scale problems during testing, utilizing two components: a scale meta-learner (SML) and scheduled adaptation with guided exploration (SAGE). Secondly, we delve into the min-max VRPs problem, which adds an additional layer of complexity and closely mirrors real-world logistical challenges. Here, we employ a deep reinforcement learning approach and customize a transformer-based neural architecture, presenting the "Equity-Transformer" as a dedicated solution for effectively tackling min-max VRPs.
이 연구는 다양한 조합최적화 문제들에 대해 스케일러블한 건설적 신경망 솔버를 만들기 위한 새로운 알고리즘들을 제시한다. 조합 최적화 문제들은 NP-완전 성질을 가지고 있기 때문에 빠르게 좋은 솔루션을 찾는 것은 매우 어렵다. 최근 몇 년 동안 건설적 RL 방법은 휴리스틱 방법과 비교할 때 소규모 인스턴스(100개 노드 미만)에서 경쟁력 있는 성능을 입증했지만 문제의 크기가 커지면 작은 스케일에서 보여줬던 성능을 보여주지 못한다. 그 이유는 기존의 건설적인 방법은 스케일러블한 속성이 고려되어있지 않기 때문이다. 이러한 문제를 해결하기 위해 우리 연구에서는 훈련 및 테스트 단계 모두에서 귀납적 편견을 도입하여 스케일러블한 건설적 신경망 솔버가 되도록 디자인 하는 것을 목표로 한다. 우리의 연구는 Meta-SAGE와 Equity-Transformer라는 두 가지 주제가 포함되어있다. 첫째, 우리의 접근 방식은 사전 훈련된 모델을 활용하여 테스트 중에 더 큰 규모의 문제를 처리하며, 스케일에 대한 메타 학습기(SML)와 안내 탐색(SAGE)이라는 두 가지 구성 요소를 활용한다. 두번째 연구는 복잡성을 더욱 가중시키고 실제 물류 문제를 밀접하게 관련있는 최소-최대 VRP 문제를 심층 강화학습 기반 건설적 솔버인 "Equity-Transformer"를 제시하여 효과적으로 풀어낸다.
