정규화된 대규모 이웃 탐색 (Regularized Large Neighborhood Search)

운영 연구 (Operations research) 실무자들은 일반적으로 대규모 이웃 탐색 (Large Neighborhood Search, LNS)을 사용하여 NP-hard 조합 최적화 문제 (combinatorial problems)를 해결합니다. LNS는 변수의 부분 집합을 국소적으로 재최적화함으로써 현재 솔루션을 반복적으로 개선하는 확장 가능한 휴리스틱 (heuristic)입니다. 이와 대조적으로, 조합 최적화 레이어를 신경망 (neural networks)에 통합하려는 대부분의 기존 접근 방식은 여전히 계산적으로 다루기 힘든(intractable) 정확한 전역 솔루션 (exact global solution)에 접근할 수 있다고 가정합니다. 우리는 정규화된 LNS (Regularized LNS, RLNS)를 도입함으로써 이 간극을 메웁니다. 국소적 부분 문제 (local subproblems)를 정규화하거나 섭동 (perturbing)함으로써, 우리는 LNS 휴리스틱을 실행 가능한 솔루션의 조합 집합에 대한 효율적인 MCMC 샘플러 (MCMC sampler)로 변환하며, 이와 관련된 Fenchel-Young 손실 (losses)을 적용합니다. 엔트로피 정규화 (entropic regularization) 하에서, 우리는 RLNS가 정확한 블록 깁스 샘플링 (block Gibbs sampling)을 수행함을 증명합니다. 또한, RLNS 반복 횟수를 조정함으로써 전역 솔버 (global solvers) 없이도 엔드투엔드 학습 (end-to-end learning)을 위해 의사 우도 (pseudolikelihood)와 정확한 최대 우도 추정 (exact maximum likelihood estimation) 사이를 보간 (interpolate)할 수 있습니다. 우리는 $k$-부분 집합 선택 ($k$-subset selection), 일반화된 할당 (generalized assignment), 그리고 확률적 차량 스케줄링 (stochastic vehicle scheduling) 문제에서 우리의 접근 방식을 입증합니다.