80년 된 '심플렉스 알고리즘'의 미스터리, 두 명의 수학자가 마침내 풀다

전 세계 물류 및 공급망 최적화의 근간을 이루는 '심플렉스 알고리즘(Simplex Method)'은 거의 80년 동안 한 가지 모순을 안고 있었습니다. 실제로는 놀랍도록 빠르게 작동하지만, 이론적으로는 최악의 경우 기하급수적으로 느려질 수 있다는 '그림자'가 따라다녔죠. 이제 두 명의 연구자가 이 오랜 난제를 해결하며 알고리즘의 효율성을 수학적으로 완벽히 증명해냈습니다.

프랑스 국립과학연구센터(CNRS)의 소피 후이버츠와 뮌헨 공과대학의 박사과정생 엘레온 바흐는 이번 달 열리는 컴퓨터 과학 재단 컨퍼런스에서 발표할 논문을 통해 이 문제를 해결했다고 밝혔습니다. 그들의 연구는 심플렉스 알고리즘이 실제로 왜 빠른지를 이론적으로 설명했을 뿐만 아니라, 알고리즘을 더욱 빠르게 만들었습니다.

숙제로 탄생한 세계적인 알고리즘

심플렉스 알고리즘의 역사는 1939년 UC 버클리의 대학원생이었던 조지 단치그의 일화에서 시작됩니다. 수업에 늦게 들어온 그는 칠판에 적힌 두 문제를 숙제인 줄 알고 베껴갔습니다. 평소보다 어렵다고 느끼며 며칠을 고생해 풀어서 제출했는데, 몇 주 뒤 교수는 그가 통계학계의 유명한 미해결 난제 두 개를 풀었다는 사실을 알려주었습니다.

이후 단치그는 제2차 세계대전 직후인 1946년 박사 학위를 받고 미 공군의 수학 고문이 되었습니다. 당시 군은 수백, 수천 개의 변수가 얽힌 상황에서 한정된 자원을 어떻게 효율적으로 배분할지, 즉 '최적화 문제'에 깊은 관심을 보였습니다. 단치그는 이 문제를 해결하기 위해 10년 전 칠판 문제를 풀며 개발했던 수학적 기법을 바탕으로 심플렉스 알고리즘을 발명했습니다.

'무작위성'이라는 열쇠

실제로는 이런 최악의 상황이 거의 발생하지 않았지만, 이론과 현실의 괴리는 오랫동안 학계의 숙제로 남아있었습니다. 2001년, 대니얼 스필먼과 샹화텅이 알고리즘에 약간의 '무작위성'을 추가하면 최악의 경우를 피하고 다항 시간(예: n의 제곱) 내에 문제를 해결할 수 있음을 증명하며 돌파구를 열었습니다.

후이버츠와 바흐는 이 연구를 한 단계 더 발전시켰습니다. 그들은 더 많은 무작위성을 알고리즘에 주입하여, 기존에 증명된 어떤 이론보다도 실행 시간이 훨씬 짧다는 것을 보장했습니다. 또한 스필먼-텅 모델 기반의 알고리즘이 자신들이 얻은 값보다 더 빨라질 수는 없다는 것, 즉 이론적 한계에 도달했음을 증명했습니다. 본 대학의 컴퓨터 과학자 하이코 뢰글린은 이 연구를 "알고리즘의 실제 효율성에 대한 최초의 진정으로 설득력 있는 설명"이라고 평가했습니다.

이 연구가 당장 상용 소프트웨어를 바꾸지는 않겠지만, 심플렉스 기반 솔루션에 의존하는 기업과 개발자들에게 이론적 확신을 심어주었습니다. 에든버러 대학의 줄리안 홀은 "실제 실험에서는 항상 다항 시간 내에 문제가 해결된다는 것을 보여주었지만, 바흐와 후이버츠는 그 직관에 더 강력한 수학적 근거를 제공했다"며, "이제 기하급수적 복잡성을 두려워하는 사람들을 설득하기가 더 쉬워졌다"고 말했습니다.