d라이브러리

어느 섬나라에 8개의 도시가 있습니다. 서로 전화통화를 할 수 있도록 도시 사이에 광케이블을 설치하려고 합니다. 도시를 어떻게 연결하면 좋을까요?

가장 쉬운 방법은 두 도시마다 짝을 지어 광케이블을 놓는 것입니다. 총 (8×7)÷2=28개의 광케이블이 필요하지요. 문제는 이렇게 하면 비용이 많이 든다는 겁니다.

그래서 광케이블 선이 가장 적게 필요한 방법을 생각해 냈습니다. 그림❶처럼 광케이블을 설치하는 겁니다. 최소 7개의 광케이블 선만 있으면 모든 도시가 서로 통화할 수 있지요. 그런데 이 방법에는 문제가 있습니다. 어느 한 선이 끊어지면 여러 도시의 전화가 안 되는 사태가 발생할 수 있거든요.
 
선 8개로 동그랗게 광케이블 망을 놓으면 어떨까요? 그림❷처럼 연결하면 선 하나가 끊어지더라도 남은 광케이블 망을 이용해 전화를 할 수 있어 조금 더 안전합니다. 동시에 설치해야 할 광케이블 선의 수도 최소화할 수 있어 비용도 절약할 수 있지요.

실제로 광케이블을 사용한 통신망은 이처럼 동그랗게 네트워크 망을 놓습니다. 우리나라를 포함한 전 세계에서 사용하고 있지요.



무조건 짧다고 좋은 것 아냐

1990년대 초 미국의 벨연구소는 이런 네트워크 망에서 어떻게 하면 정보를 가장 효율적으로 전송할 수 있는지 연구했습니다. 광케이블에서 전송할 수 있는 데이터 용량은 그 양끝에 설치하는 장비의 성능에 따라 다릅니다. 데이터를 많이 보내려면 비싼 장비를 써야 하기 때문에, 각각의 광케이블을 지나는 정보의 양이 가장 적도록 망을 설계하는 것이 중요하지요.

예를 들어 위 그림과 같은 상황을 봅시다. 그림❸은 도시 사이의 통신 수요를 나타냅니다. 도시1과 도시6 사이에는 2라는 양의 통신 수요가 있지요. 만일 이런 상황에서 그림❹처럼 연결하면, 도시3과 도시4를 잇는 광케이블의 용량은 10(=2+2+3+3)이상이어야 합니다. 도시3과 도시4를 지나는 광케이블 선의 통신 수요의 값을 모두 더한 값이지요. 하지만 그림❺처럼 연결하면 광케이블의 용량이 5(=2+3)이상만 돼도 충분합니다.

이처럼 두 도시를 연결할 때는 원에서 짧은 쪽으로 연결하거나, 긴 쪽으로 연결하는 두 가지 선택이 있습니다. 언뜻 생각하기에는 원에서 짧은 쪽으로 연결하는 것이 좋을 것 같지만, 그러면 도시3과 도시4를 잇는 광케이블의 용량이 6이 돼 최적인 5보다 더 비싸집니다.

그렇다면 어떻게 연결해야 최적일까요? 도시가 8개라면 두 도시를 연결하는 방법의 수는 28가지입니다. 여기에 두 도시마다 짧은 쪽과 긴 쪽 둘 중 하나를 선택해야 하므로 광케이블을 놓는 방법이 최대 228개나 됩니다. 이렇게 많으면 모든 경우를 다 따져보고 최적의 연결을 찾는 것은 무리입니다.



문제 바꿔 쉽게 풀고 원래 답도 구한다

수학자들은 이 문제를 풀기 위해 ‘선형계획법’을 떠올렸습니다. 여기에 적용하기 위해 문제를 조금 수
정했습니다. 두 도시를 연결할 때 긴 쪽과 짧은 쪽 양 방향 중 하나를 택해야 한다는 조건 대신 어떤 방향으로든 전체 수요의 1/3만큼 연결하면, 2/3는 다른 방향으로 연결한다고 가정했습니다.

원래 문제에서는 짧은 쪽이든 긴 쪽이든 방향을 정하고 나면 데이터는 한쪽 방향으로만 보낼 수 있습니다. 만약 처음에 시계방향으로 보내기로 정했다면 필요한 데이터 9를 모두 시계방향으로 보내야 하지요. 하지만 조건을 약하게 만든 문제에서는 9 중 3은 시계방향으로 보내고, 6은 반시계방향으로 보낼 수 있습니다. 문제를 쉽게 해결하기 위해 조건을 완화한 것이지요.

이러면 여러 개의 부등식 조건을 만족하면서 어떤 일차식 값이 최솟값이 되는 경우를 찾는 문제가 됩니다. 이게 바로 선형계획법입니다. 실제 산업현장에서는 선형계획법을 활용해 최적화 작업을 하고 있고, 선형계획법을 잘 푸는 ‘CPLEX’와 같은 소프트웨어는 비싼 값에 팔리고 있습니다.

그런데 이 답은 조건을 약하게 만든 문제의 답입니다. 원래 문제의 답은 아니지요. 바꾼 문제의 답을 원래 문제의 답과 비슷하게 만드는 것이 가능할까요?

1990년대 전화회사의 연구소였던 벨코어에서 근무하던 수학자들은 이 문제를 놓고 고민했습니다. 2월호에도 소개했던 폴 세이머 교수와 지금은 미국 다트머스대 교수인 피터 윙클러 교수, 그리고 이곳을 잠시 방문한 네덜란드의 수학자 알렉산더르 스레이버르 교수가 그 주인공입니다.

그들은 1998년 논문에서 한 가지 사실을 증명했습니다. 먼저 광케이블의 최대 용량을 L, 조건을 약하게 만든 문제를 풀어서 나온 광케이블의 최대 용량을 L*이라고 합시다. 그리고 두 도시를 연결할 때 둘로 나눴던 수요 중에서 가장 큰 값을 D라고 합니다. 그러면 최대 용량 L이 L*+1.5D 이하가되면 원래 문제의 답을 찾을 수 있습니다. 그리고 이것을 찾는 매우 빠른 알고리듬도 제시했습니다.

사실 L*은 L보다 항상 같거나 작습니다. 그 이유는 바꾼 문제가 더 여러 경우를 포함하기 때문입니다. 따라서 이 답을 L*+1.5D 이내로 찾을 수 있다면 비용을 최소로 하면서 수요를 만족하는 방법을 찾은 게 되지요.
 
산업계 문제, 수학자가 푼다!

올해 초 독일 베를린공대 마르틴 슈쿠텔라 교수는 미국응용수학회(SIAM) 저널에 출판된 논문에서 이 1.5라는 값을 줄인 개선된 근사 알고리듬을 제시했습니다. 새로운 알고리듬은 바꾼 문제 답과 L*와 D값이 있을 때, 최대 용량이 L*+19/14 D 이하가 되면 원래 문제의 답을 효율적으로 찾아줍니다. 19/14 는 대략 1.357이므로 1.5보다 작은 값입니다. 따라서 이를 사용한다면 조금 더 효율적인 방법을 찾을 수 있는 것이지요.

슈쿠텔라 교수는 최대 용량이 L*+D 이하인 경우가 항상 있다는 기존의 추측은 틀렸다고도 밝혔습니다. 1998년 논문에서 세 명의 수학자는 바꾼 문제의 답에 원래 문제의 답이 항상 있다고 주장했는데, 이것이 틀렸다는 것이지요. 그가 수억 개의 특수한 상황을 계산한 결과 반례가 딱 하나 있었습니다. 도시가 16개이고 서로 통신하려는 도시의 쌍은 18쌍이어서 218가지 경우를 고려해야 최적인 최대 용량을 구할 수 있는데, 계산해 보니 최적인 L은 50이었고, L*=39, D=10이어서 L≤L*+D라는 식은 틀렸던 것입니다.

이처럼 광케이블을 이용한 통신망 문제는 산업 현장의 문제를 수학자의 도움으로 해결한 대표적인 경우입니다. 앞으로 우리나라도 수학을 통해 산업 경쟁력을 높일 수 있기를 바랍니다.