Ising-Machine-Assisted Large Neighborhood Search with Flexibly Tunable Subproblem Size

기술 요약: 유연하게 조절 가능한 부문제 크기를 갖춘 이싱 머신 보조 대규모 근방 탐색 (LNS)

문제 정의
이싱 머신은 이싱(Ising) 또는 이차 무제약 이진 최적화(QUBO) 모델의 저에너지 상태를 탐색함으로써 조합 최적화를 해결하는 휴리스틱 솔버 역할을 합니다. 그러나 이를 대규모 제약 조건 문제에 직접 적용하는 것(소위 "나이브 방식")은 두 가지 주요 어려움에 직면합니다:

1. 확장성: QUBO 정식화 과정에서 발생하는 이진 변수의 수가 현재 이싱 머신의 하드웨어 용량을 초과하는 경우가 많습니다.
2. 실행 가능성: 제약 조건은 일반적으로 페널티 항으로 통합됩니다. 결과적으로 탐색 공간에는 실행 불가능한 해가 포함될 수 있으며, 저에너지 상태가 반드시 원래 문제의 고품질 실행 가능 해를 의미하지는 않습니다.

변수 고정(variable fixing)이나 분할 정복(divide-and-conquer)과 같은 기존 접근 방식은 문제 크기를 줄이려고 시도하지만, 부문제 크기와 원래 문제의 실행 가능한 해를 재구성하는 능력 사이의 균형을 맞추는 데 어려움을 겪는 경우가 많습니다. 대규모 근방 탐색(Large Neighborhood Search, LNS)은 현재의 실행 가능한 해를 반복적으로 개선하기 위해 부문제(즉, "근방")를 재최적화하는 프레임워크를 제공합니다. LNS는 부문제 생성 방법이 적절히 설계된 경우 실행 가능성을 보존하지만, 이싱 머신 보조 LNS의 성능은 부문제의 크기에 매우 민감합니다. 부문제가 너무 작으면 반복당 잠재적 개선량이 제한되며, 너무 크면 확장된 탐색 공간으로 인해 이싱 머신의 해 품질이 저하됩니다.

방법론
본 논문은 차량 경로 문제(VRP)와 이차 다중 배낭 문제(QMKP) 두 가지 문제에 집중합니다.

• 기존 방식 (LNS-V): VRP에 대해, 저자들은 선택된 차량들의 전체 경로를 재최적화하는 기존 방식(LNS-V)을 분석합니다. 이 방식은 실행 가능성을 보존하지만, 부문제 크기가 선택된 차량의 수($V'$)에 의해서만 결정됩니다. 선택된 차량의 전체 경로를 재최적화하기 때문에 변수의 수는 $(V')^2(T-2)^2$ (여기서 $T$는 총 단계 수)로 스케일링됩니다. 이는 입자가 거칠다는 것을 의미하며, $V'$를 1만큼 변경하는 것만으로도 변수 개수가 급격히 변하여 이싱 머신의 최적 범위에 맞춰 부문제 크기를 미세하게 조정하기 어렵게 만듭니다.

• 제안된 방식 (LNS-VT): 이러한 입자성 문제를 해결하기 위해, 저자들은 LNS-VT를 제안합니다. LNS-VT는 선택된 차량의 수($V'$) 외에도 새로운 파라미터인 각 선택된 차량에 대해 재최적화할 연속 단계의 수($T'$)를 도입합니다.

  • 메커니즘: 각 선택된 차량에 대해, 경로의 연속적인 세그먼트(길이 $T_{seg} = \min(T', \text{실제 유효 단계})$)를 추출합니다. 부문제는 추출된 세그먼트 내에서의 할당 및 순서를 재최적화하는 동시에 나머지 경로는 고정된 상태로 유지합니다.
  • 실행 가능성: 추출 구간 외부의 사이트들을 고정하고, 추출된 세그먼트가 비(non)-데포(depot) 사이트들만을 포함하도록 보장함으로써, 추출된 세그먼트의 실행 가능한 부문제 해를 재삽입했을 때 원래 VRP의 실행 가능한 해가 되도록 보장합니다.
  • 변수 제어: LNS-VT의 자유 변수 수는 약 $(V'T')^2$입니다. 이를 통해 전체 문제 단계 $T$와 독립적으로 부문제 크기를 미세하게 제어할 수 있습니다.

• QMKP로의 확장: 저자들은 동일한 설계 원칙을 QMKP에 적용합니다. 이들은 선택된 배낭의 부분 집합($K'$)과 선택된 아이템의 부분 집합($N'$)을 선택하여 재최적화하는 부문제 생성 방법을 구축합니다. 이 방법은 선택되지 않은 아이템을 고정하고 선택된 배낭들의 잔여 용량에 맞춰 용량 제약을 조정함으로써 실행 가능성을 보존합니다.

주요 결과
수치 실험은 Fixstars Amplify AE 이싱 머신을 사용하여 300개 사이트, 5대 차량 VRP와 200개 아이템, 5개 배낭 QMKP를 대상으로 수행되었습니다.

• VRP 성능:

  • LNS-VT가 나이브 방식과 기존의 LNS-V보다 우수한 성능을 보였습니다.
  • 최적의 LNS-VT 설정(구체적으로 $V'=2, T'=40$)은 100회 반복 후 LNS-V 대비 약 **10%**의 목적 함수 값 감소를 달행했습니다.
  • LNS-VT는 LNS-V가 도달한 최종 해 품질에 약 **30%**의 반복 횟수만으로 도달했습니다.
  • 변수 민감도: (비-데포 사이트 할당 변수 기준) 최적의 부문제 크기는 6,000에서 10,000 사이로 나타났습니다. 기존의 LNS-V는 $V' \ge 2$인 상태에서 이 범위를 달성할 수 없었으며(최솟값이 약 14,400개 변수), 이것이 LNS-V의 성능이 저하된 이유입니다.
  • 동적 요구 사항: 적절한 부문제 크기는 탐색 과정 중에 변화했습니다. 초기 반복(높은 목적 함수 값)에서는 더 큰 부문제 가 효과적이었고, 후기 반복(고품질 해 정밀화)에서는 더 작은 부문제가 더 효과적이었습니다.

• QMKP 성능:

  • QMKP에 적용된 LNS 역시 나이브 방식보다 우수한 성능을 보였습니다.
  • QMKP의 최적 부문제 크기는 약 100에서 150개의 변수로 훨씬 작게 나타났습니다.
  • VRP(6,000–10,000)와 이 극명한 차이는 최적의 부문제 크기가 이싱 머신의 능력뿐만 아니라 특정 문제 클래스와 QUBO 정식화에 따라 달라짐을 나타냅니다.

의의 및 주장
본 논문은 이싱 머신 보조 LNS가 대규모 제약 조건 문제를 효과적으로 해결하기 위해서는 실행 가능성 보존만으로는 불충분하다고 주장합니다. 이싱 머신의 성능 최적 지점(sweet spot)에 맞추어 부문제 크기를 유연하게 조절할 수 있는 능력이 핵심적인 설계 요소라는 것입니다.

연구 결과는 다음을 입증합니다:

1. 추가적인 제어 파라미터(VRP의 경우 연속 단계, QMKP의 경우 아이템/배낭 개수)를 도입하면, 선택된 엔티티의 수만을 변화시키는 방식으로는 불가능했던 미세한 부문제 크기 조절이 가능해집니다.
2. 이싱 머신의 성능을 극대화하는 변수의 최적 범위가 존재하며, 이 범위는 서로 다른 문제 클래스(VRP vs. QMKP) 간에 크게 다릅니다.
3. 최적의 부문제 크기는 현재 해의 품질에도 의존할 수 있으며, 이는 정적인 파라미터 설정이 전체 탐색 과정 동안 최적이 아닐 수 있음을 시사합니다.

저자들은 자신의 결과가 테스트된 인스턴스와 머신 설정에 국한적임을 인정하면서도, 구조를 인식하고 유연하게 조절 가능한 부문제 생성 원칙이 제약 조건이 있는 조합 최적화 분야의 유망한 방향임을 결론짓습니다. 향서 연구는 탐색 단계와 문제 구조에 따라 부문제 파라미터를 자동으로 선택하는 적응형 전략 개발에 집중해야 한다고 언급했습니다.