Evaluating the Performance of Direct Higher-Order Formulations in Combinatorial Optimization Problems

기술 요약: 조합 최적화 문제에서 직접적인 고차 형식(Direct Higher-Order Formulations)의 성능 평가

문제 정의
조합 최적화 문제는 물류, 재료 설계, 포트폴리오 최적화와 같은 분야에서 빈번하게 접하게 됩니다. 이러한 문제 중 상당수는 NP-hard에 해당하여 휴리스틱 접근 방식이 필요하지만, "이징 머신(Ising machines)"(양자 어닐링 하드웨어 및 물리 기반 솔버 포함)에 이를 구현하는 데에는 상당한 장벽이 존재합니다. 대부분의 기존 하드웨어 플랫폼은 이진 변수의 선형 및 이차 항만을 목적 함수로 허용하는 이차 무제약 이진 최적화(QUBO) 형식으로만 입력을 받습니다.

그러나 폴리머 샘플링, 단백질 구조 예측, 특정 라우팅 작업과 같이 본질적으로 고차 상호작용(3차, 4차 등)을 포함하는 수많은 실제 문제들이 존재합니다. 이러한 문제를 표준 하드웨어에서 해결하기 위해 연구자들은 다항 무제약 이진 최적화(PUBO) 문제를 QUBO 형태로 변환하는 "차수 감소(order-reduction)" 기술을 적용해야 합니다. 이 과정은 논리적 일관성을 유지하기 위해 보조 변수와 패널티 항을 도입합니다. 저자들은 이러한 변환이 필연적으로 문제의 크기와 구조적 복잡성을 증가시키며, 잠재적으로 솔루션의 품질과 안정성을 저하시킬 수 있다고 주장하지만, 직접적으로 고차 항을 처리하는 것과 차수를 감소시키는 것 사이의 구체적인 영향이 실질적인 대규모 인스턴스에 대해 통일된 플랫폼상에서 충분히 정량화되지 않았습니다.

방법론
이러한 격차를 해소하기 위해, 본 연구는 **Fixstars Amplify Annealing Engine (Amplify AE)**을 사용하여 비교 평가 프레임워크를 채택하였습니다. 시뮬레이티드 어닐링(SA)과 대규모 GPU 병렬화를 기반으로 하는 이 고성능 솔버는 두 가지 뚜로 구별되는 모드를 제공합니다:

1. PUBO 솔버: 수정 없이 최대 4차 항을 포함하는 목적 함수를 직접 최적화합니다.
2. QUBO 솔버: 차수 감소를 위해 **치환법(substitution method)**을 적용한 후 동일한 문제를 해결합니다. 이 방법은 이진 변수들의 곱을 새로운 보조 변수로 대체하고, 제약 조건(예: $x_1x_2 = y_{1,2}$)을 패널티 항을 통해 강제합니다.

본 연구는 고차 항을 자연스럽게 포함하는 두 가지 벤치마크 문제를 통해 두 접근 방식을 비교합니다:

• 저자기상관 이진 수열(Low Autocorrelation Binary Sequence, LABS): 최소 자기상관 에너지를 갖는 이진 수열을 찾는 문제입니다. 에너지 함수는 제곱 자기상관 항을 포함하며, 결과적으로 4차 상호작용($s_i s_{i+k} s_j s_{j+k}$)을 생성합니다.
• 거리 균형을 고려한 차량 경로 문제(Vehicle Routing Problem, VRP): 총 이동 거리를 최소화하는 동시에 차량 간 거리의 분산을 최소화하는 다목적 문제입니다. 분산 항은 전개 시 4차 상호작용을 도입합니다.

실험은 고정된 계산 시간(60초)과 다양한 문제 규모에 걸쳐 수행되었습니다. LABS의 경우 수열 길이($N$)는 5에서 99까지였습니다. VRP의 경우 고객 위치 수($P$)와 차량 수($V$)를 다양하게 변화시켰습니다. QUBO 솔버는 치환법을 위해 고정된 패널티 계수($p=1$)를 사용한 반면, PUBO 솔버는 별도의 매개변수 튜닝을 필요로 하지 않았습니다.

주요 기여 및 결과
본 논문은 직접적인 PUBO 공식화와 감소된 QUBO 공식화 사이의 트레이드오프에 대한 정량적 분석을 제공합니다:

1. 솔루션 품질 및 안정성:

   • LABS: PUBO 솔버는 QUBO 솔버에 비해 현저히 작은 표준 편차와 함께 일관되게 더 낮은 정규화된 에너지 값(최적해에 더 가까운 값)을 달산했습니다. 성능 격차는 수열 길이 $N$이 증가함에 따라 더욱 벌어졌습니다.
   • VRP: 단일 인스턴스 분석에서, PUBO 솔버는 총 이동 거리와 거리 분산 사이의 더 안정적인 트레이드오프를 생성했습니다. 산점도 분석 결과, QUBO 솔루션은 넓게 퍼져 있었으며 진정한 최소 분산 영역에 도달하지 못한 반면, PUO 솔루션은 파레토 프런트(Pareto front) 근처에 집중되었습니다.
   • 하이퍼볼륨 분석: 30개의 무작위 생성 VRP 인스턴스에 대해, PUBO 솔버는 QUBO 솔버보다 일관되게 더 큰 하이퍼볼륨 지표(솔루션 세트의 다양성과 품질을 나타내는 척도)를 달성하여 다목적 최적화에서의 우수성을 입증했습니다.

2. 변수 확장:

   • 본 연구는 차수 감소로 인한 "변수 폭발(variable explosion)"을 정량화했습니다. LABS와 VRP 모두에서, QUBO 공식화의 이진 변수 수는 문제 규모가 커짐에 따라 급격히 증가하여, 대규모 인스턴스의 경우 직접적인 PUBO 공식화보다 수십 배에 달했습니다. 이러한 확장은 탐색 공간을 넓혀 관찰된 솔루션 안정성 저하의 원인이 됩니다.

3. 패널티 계수에 대한 민감도:

   • 저자들은 치환법에 사용되는 패널티 계수($p$)에 대한 QUBO 방식의 민감도를 조사했습니다. LABS 문제에 대한 히트맵 분석은 최적의 패널티 계수가 문제 규모($N$)에 따라 크게 달라짐을 보여주었습니다. 모든 규모에 대해 일관된 성능을 제공하는 단일 $p$ 값은 존재하지 않았으며, 이는 일반적인 적용을 위한 감소된 공식화 튜닝의 어려움을 강조합니다.

의의 및 주장
본 논문은 현대적인 이징 유형 하드웨어에서 조합 최적화 문제를 해결할 때, PUBO 공식을 통해 고차 항을 직접 처리하는 것이 전통적인 차수 감소 방식보다 뚜렷한 이점을 제공한다고 주장합니다. 주요 의의는 다음과 같습니다:

• 구조적 무결성: 원래의 문제 구조(PULO)를 보존함으로써 보조 변수로 인한 인위적인 탐색 공간 확장을 방지합니다.
• 강건성: 직접적인 공식화는 문제 규모에 따라 민감하게 반응하며 탐색 과정을 불안정하게 만들 수 있는 패널티 계수 튜닝의 필요성을 제거합니다.
• 확장성: PUBO 방식은 문제 규모가 커짐에 따라 우수한 솔루션 품질과 안정성을 유지하는 반면, QUBO 방식은 변수 확장과 제약 조건 강제의 결합된 효과로 인해 어려움을 겪습니다.

저자들은 차수 감소가 다양한 문제에 효과적이었음에도 불구하고, 직접적인 PUBO 공식화가 구조적 단순성과 계산적 안정성을 모두 제공함으로써 실질적인 대규모 최적화 시나리오를 위한 유망한 접근 방식임을 결론지었습니다. 본 연구는 향-하드웨어 및 솔버 개발이 이러한 이점을 실세계 응용 분야에서 온전히 활용하기 위해 직접적인 고차 실행을 지속적으로 지원해야 함을 시사합니다.