Learning efficient representations of complex constraints for scalable optimization

현대 사회에서 우리의 가장 중요한 결정 중 상당수는 복잡한 수학적 퍼즐을 푸는 것에 의존합니다. 전력망의 균형을 맞춰 불이 꺼지지 않게 하든, 도시를 통과하는 수천 대의 배송 트럭 경로를 설정하든, 혹은 거대한 투자 포트폴리오를 관리하든, 이러한 과업들은 물리적 한계인 전압 안전성, 도로 용량, 또는 재무적 리스크와 같은 엄격한 규칙인 제약 조건을 준수하면서 최선의 결과를 찾는 과정을 포함합니다. 문제는 우리의 시스템이 더 커지고 상호 연결될수록, 이러한 규칙의 수가 폭발적으로 증가한다는 점입니다. 의사결정자가 수백만 개의 제약 조건 사이에서 최적의 경로를 계산하려고 할 때, 컴퓨터는 종나히 벽에 부딪히곤 합니다. 계산 시간이 너무 오래 걸리거나, 가용 메모리가 부족하거나, 혹은 결정을 내려야 할 시점까지 계산을 끝내지 못하고 단순히 실패하기도 합니다. 이는 신속하고 최적인 결정을 내려야 하는 필요성이 현재의 컴퓨터가 이를 찾아내는 능력을 앞지르는 병목 현상을 만듭니다.

이를 해결하기 위해 연구자들은 전통적으로 두 가지 주요 접근 방식을 시도해 왔습니다. 한 가지 방법은 광범위한 수학적 근사를 통해 규칙을 단순화하려고 시도하지만, 이는 때때로 너무 느슨하여 서류상으로는 좋아 보이지만 실제로는 실패하는 솔루션을 초래할 수 있습니다. 다른 접근 방식은 머신러닝을 사용하여 답을 직접 예측하는 것이지만, 이러한 예측은 솔루션이 실제로 규칙을 따르고 있다는 보장이 부족한 경우가 많습니다. 새로운 연구는 다른 길을 제시합니다. 이는 답을 추측하거나 기존 계산을 단순히 가속화하려는 것이 아닙니다. 대신, 컴퓨터에게 규칙 자체의 형태를 이해하도록 가르치고, 그 후 복잡하고 지저도한 규칙을 표준 소프트웨어로 풀기 쉬운 훨씬 단순한 기하학적 버전으로 교체하는 방식입니다.

칭화대학교와 베이징 공업대학교를 포함한 기관의 연구진이 이끄는 연구팀은 '폴리포머(PolyFormer)'라고 부르는 프레임워크를 개발했습니다. 핵심 아이디어는 수천 개의 변수와 비선형 방정식을 포함할 수 있는 가장 복잡한 규칙 집합이라 할지라도, 공간 내에 특정한 형태를 정의한다는 것입니다. 이 형태는 허용되는 모든 가능한 솔루션을 나타냅니다. 원래의 형태는 울퉁불퉁하거나 뒤틀려 있거나 믿을 수 없을 정도로 복잡할 수 있지만, 연구진은 이를 평평한 면들로 이루어진 훨씬 단순한 형태인 '폴리토프(polytope)'로 근사할 수 있다는 것을 발견했습니다. 이것은 마치 매우 불규칙하고 울퉁불퉁한 바위를 그것을 딱 맞게 담을 수 있을 만큼만 충분히 조이는 매끄러운 다면체 상자에 넣는 것과 같습니다. 원래의 풀기 어려운 규칙을 이 단순화된 기하학적 상자로 교체함으로써, 컴퓨터는 표준적인 기성 소프트웨어를 사용하여 거의 즉각적으로 최적의 솔루션을 찾을 수 있습니다.

연구팀은 이 방법이 복잡한 시스템에서 발견되는 다양한 도전 과제들을 처리할 수 있는지 확인하기 위해 세 가지 매우 다른 유형의 실제 문제에 대해 테스트를 진행했습니다. 첫 번째 테스트는 전기 자동차, 배터리 저장 시스템, 히트 펌프와 같은 개별 자원의 대규모 집합을 관리하는 것이었습니다. 각자의 물리적 제한 사항을 가진 1,000개의 장치가 있는 시나리오에서, 원래의 수학적 모델은 시스템을 설명하기 위해 거의 58,000개의 별도 제약 조건을 필요로 했습니다. 폴리포머 프레임워크는 이 거대한 복잡성을 단 96개의 제약 조건으로 압축하는 법을 배웠습니다. 이러한 감소를 통해 시스템은 높은 수준의 정확도를 유지하면서도 원래 제약 조건의 99.83%를 제거할 수 있었습니다. 연속적인 설정과 온-오프 스위치를 모두 포함하는 혼합 유형의 제어가 있는 두 번째 시나리오에서는, 이 방법이 모든 이진 변수를 제거하고 제약 조건의 수를 거의 98.5% 줄이는 데 성공했으며, 이는 기존의 다른 단순화 방법들이 달성할 수 없었던 성과였습니다.

두 번째 응용 분야는 전력 그리드, 구체적으로 고전압 송전선과 가정 및 기업에 전력을 공급하는 지역 배전 네트워크 간의 관계에 초점을 맞췄습니다. 이러한 네트워크는 서로 깊이 연결되어 있어 의존성의 그물을 형성하며, 이는 최적화를 극도로 느리게 만듭니다. 가장 큰 테스트 케이스 중 하나에서, 원래 모델은 715,000개 이상의 제약 조건과 거의 480,000개의 변수를 포함하고 있었습니다. 이를 직접 푸는 데 표준 솔버는 1,476초가 소요되었고 800MB 이상의 메모리가 필요했습니다. 폴리포머 단순화를 적용한 후, 문제는 단 2,000여 개의 제약 조건으로 축소되었습니다. 결과는 극적인 개선이었습니다. 솔버는 0.25초 미만에 솔루션을 찾아냈으며, 메모리는 3.5MB만을 사용했습니다. 이는 6,400배 이상의 속도 향상을 의미합니다. 결정적으로, 솔루션은 매우 높은 신뢰성을 유지했으며, 안전 규칙을 위반할 위험은 실질적인 목적으로 볼 때 거의 제로에 가까운 수준으로 감소했습니다.

세 번째 테스트는 미래의 결과가 알려지지 않은 금융 분야와 같이 불확실성이 존재하는 상황을 다루었습니다. 포트폴리오 관리에서 투자자는 시장 조건이 예상치 못하게 변하더라도 손실 위험이 허용 범위 내에 있도록 보장하면서 자산을 어떻게 배분할지 결정해야 합니다. 불확실성을 처리하기 위한 표준적인 방법들은 흔히 모델에 엄청난 수의 추가 변수와 규칙을 추가해야 하며, 이는 계산적으로 무겁게 만듭니다. 400개의 자산이 포함된 포트폴리오를 다룬 테스트에서, 전통적인 방식은 100만 개 이상의 제약 조건과 변수를 필요로 했습니다. 폴리포머는 이를 단 1,617개의 제약 조건과 400개의 변수로 압축했습니다. 이 감소 덕분에 시스템은 전통적인 방식의 513초와 비교하여 0.725초 만에 문제를 해결할 수 있었으며, 동시에 위험과 수익 사이의 경쟁력 있는 절충안을 제공하는 솔루션을 제공했습니다.

이 새로운 프레임워크의 핵심적인 특징은 처음부터 다시 학습할 필요 없이 변화하는 조건에 빠르게 적응할 수 있는 능력입니다. 많은 실제 상황에서 환경은 변합니다. 온도가 변하고, 시장 가격이 요동치며, 수요 패턴이 진화합니다. 연구진은 입력값에 따라 규칙의 형태가 어떻게 변하는지를 인식하도록 시스템을 학습시켰기 때문에, 모델은 새로운 상황에 대한 새로운 단순화된 제약 조건 세트를 즉각적으로 생성할 수 있습니다. 이는 일단 시스템이 학습되면 다양한 시나리오를 즉석에서 처리할 수 있음을 의미하며, 실시간으로 의사결정을 내려야 하는 동적인 환경에 적합하게 만듭니다.

이 연구는 이 접근 방식이 단순한 이론적 연습이 아니라 다양한 영역에 적용될 수 있는 실용적인 도구임을 입증합니다. 제약 조건의 기하학적 구조를 학습함으로써, 이 시스템은 상세하고 정확한 모델링의 필요성과 빠르고 확장 가능한 계산의 필요성 사이의 간극을 효과적으로 메웁니다. 연구진은 단 하나의 파라미터를 조정함으로써 규칙에 대한 엄격한 준수와 솔루션의 품질 사이의 절충안을 조절할 수 있다는 것을 발견했으며, 이를 통해 사용자는 상황의 특정 요구에 따라 안전성이나 효율성을 우선시할 수 있습니다. 이러한 유연성은 이 방법이 작은 오류가 심각한 결과로 이어질 수 있는 전력망과 같은 안전 필수 애플리케이션뿐만 아니라, 수익 극대화가 목표인 금융 애플리케 Anwendungen에도 충분히 견고하게 만들 수 있게 합니다.

이 방법은 볼록한(convex) 형태에 대해서는 매우 잘 작동하지만, 연구진은 일부 복잡한 시스템이 구멍이나 움푹 들어간 부분이 있는 비볼록(non-convex) 영역을 포함한다는 점을 인정합니다. 이러한 경우, 단순화된 모델은 형태의 외곽 경계를 근사하며, 이는 많은 응용 분야에는 충분하지만 모든 내부 세부 사항을 포착하지는 못할 수 있습니다. 그러나 엔지니어링과 경제학에서 마주하는 대다수의 대규모 최적화 문제에 있어, 이 근사는 강력한 새로운 방법을 제공합니다. 연구진은 원시적이고 복잡한 방정식을 푸는 것에서 벗어나 솔루션 공간의 형태를 학습하는 데 집중함으로써, 컴퓨터가 효과적으로 처리하기에는 너무 크거나 너무 빨랐던 시스템을 관리할 수 있는 능력을 끌어낼 수 있다는 것을 보여주었습니다.

이 연구의 함의는 테스트된 특정 사례들을 넘어 확장됩니다. 복잡하고 상호 의존적인 규칙을 압축하여 솔버 친화적인 형식으로 만드는 능력은, 점점 커지는 사회 기술적 시스템을 관리하기 위한 새로운 경로를 제공합니다. 세상이 수십억 개의 장치와 엔티티가 실시간으로 상호 작용하는 더욱 연결된 세상이 됨에 따라, 신속하고 신뢰할 수 있는 의사결정에 대한 수요는 계속 증가할 것입니다. 이 프레임워크는 한 번에 해결하기에는 계산적으로 불가능했던 과제들을 눈 깜짝할 사이에 해결할 수 있는 작업으로 바꾸어 놓음으로써, 그 수요를 충족할 수 있는 확장 가능한 경로를 제공합니다. 폴리포머의 성공은 최적화의 미래가 단순히 더 빠른 컴퓨터에 있는 것이 아니라, 문제 자체를 표현하는 더 스마트한 방식에 있다는 것을 시사합니다.