칸토로비치 문제: 나눠 보내면 선형계획이 된다

몽주 문제는 흙더미 하나를 쪼갤 수 없다는 규칙 때문에 두 번 막혔다. 흙의 양이 더미마다 다르면 답이 아예 없고, 양이 같아도 배정의 가짓수가 n!로 늘어난다. 실제 공사장의 흙은 트럭 여러 대로 나눠 실을 수 있다. 흙더미 A가 트럭 5대분이라면, 2대는 구덩이 3으로, 1대씩은 다른 구덩이로 보내는 것이 자연스럽다. 흙을 나눠 보내도 된다면 문제는 어떤 꼴이 되고, 나눌 수 있게 되었다고 오히려 더 풀기 어려워지지는 않을까?

역사: 합판 공장의 숙제에서 나온 선형계획

나눠 보내는 수송 문제에 닿은 사람은 흙과는 거리가 먼 곳에서 일하던 소련의 수학자 레오니트 칸토로비치(Leonid Kantorovich, 1912–1986)였다. 칸토로비치는 자신의 회고에서 레닌그라드 합판 트러스트(공장 연합)의 실험실에 자문을 하다가 아주 특별한 극값(가장 크거나 작은 값을 찾는) 문제를 만났다고 적었다. 뒷날의 전기들은 1938년 이 트러스트가 레닌그라드 대학의 젊은 교수였던 그에게 들고 온 문제를 이렇게 전한다. 선반 여덟 대에 일을 어떻게 나눠 맡겨야 합판 다섯 종류를 정해진 비율로 가장 많이 만들 수 있느냐는 것이었다. 기계마다 종류마다 걸리는 시간이 달라, 기계 한 대를 한 종류에만 쓰지 않고 시간을 나눠 맡기는 것이 핵심이었다.

칸토로비치는 이런 문제들이 모두 「1차식으로 된 조건들 아래에서 1차식 하나를 가장 크게(또는 작게) 만들기」라는 같은 꼴임을 알아보고, 그 해법을 1939년 레닌그라드 대학 출판부에서 소책자 『생산의 조직과 계획의 수학적 방법』으로 냈다. 오늘날 선형계획이라 부르는 것의 핵심이 그 안에 있었고, 물건을 나르는 길을 정하는 문제도 예로 들어 있었다. 1942년에는 짧은 논문 「질량의 옮김에 대하여」에서 수송 문제를 따로 다뤘지만, 이때 그는 몽주의 글을 몰랐다. 1948년에야 「몽주의 한 문제에 대하여」라는 글에서 160여 년 전의 흙 나르기와 자신의 문제를 이었다.

결정적인 차이는 한 출발점의 양을 여러 도착점으로 나눠 보낼 수 있게 한 데 있다. 「누가 누구와 짝인가」 대신 「어디에서 어디로 얼마만큼」을 적은 표를 정하는 문제가 된 것이다. 칸토로비치의 소책자는 오랫동안 서방에 알려지지 않았다. 미국에서는 1947년 조지 단치그(George Dantzig)가 낸 단체법(다면체의 꼭짓점을 따라 옮겨 가며 선형계획을 푸는 방법)과 함께 선형계획이 따로 자랐고, 수송 문제를 연구하던 경제학자 찰링 쿠프만스(Tjalling Koopmans)도 그 흐름에 있었다. 칸토로비치의 소책자는 1960년에야 영어로 옮겨져 『매니지먼트 사이언스』에 실렸다. 1975년 두 사람은 「자원의 최적 배분 이론에 기여한 공로」로 노벨 경제학상을 함께 받았다.

트럭 5대분짜리 흙더미

먼저 몽주 문제와 같은 공사장, 같은 비용 표에서 「나눠 보내도 된다」는 규칙만 바꿔 보자. 흙더미와 구덩이가 모두 트럭 1대분이면, 흙더미 A가 0.5대분은 구덩이 2로, 0.5대분은 구덩이 3으로 보내는 것도 이제 허락된다. 이렇게 넓어진 선택지에서 총 시간이 가장 작은 계획을 선형계획으로 풀면, 답은 A→3, B→4, C→1, D→2에 1대분씩, 총 14분이다. 쪼갤 수 있게 해 주었는데도 가장 좋은 계획은 쪼개지 않고, 몽주 문제의 답을 그대로 돌려준다.

이번에는 양을 바꾼다. 흙더미 A가 트럭 5대분이고 B, C, D는 1대분씩이며, 구덩이는 넷 다 2대분씩이다(합은 양쪽 모두 8대분). 몽주 문제라면 답이 없는 경우다. 흙더미 i에서 구덩이 j로 보내는 트럭 수를 πᵢⱼ로 두면, 정할 것은 칸 열여섯 개짜리 표 하나다. 지켜야 할 것은 세 가지뿐이다. 흙더미마다 내보낸 양의 합이 그 더미의 양 pᵢ와 같고, 구덩이마다 받은 양의 합이 그 구덩이의 양 qⱼ와 같고, 보내는 양은 음수가 아니다. 총 시간 ΣπᵢⱼCᵢⱼ도, 지켜야 할 조건도 모두 π의 1차식이어서, 칸토로비치가 합판 공장에서 본 바로 그 꼴이 된다.

선형계획으로 풀면 다음 계획이 나온다. 흙더미 A의 5대분이 구덩이 1, 2, 3, 4로 1, 1, 2, 1대씩 나뉘고, B는 구덩이 4로, C는 구덩이 1로, D는 구덩이 2로 1대씩 간다. 총 시간은 9 + 6 + 14 + 9 + 3 + 2 + 2 = 45분이다.

πᵢⱼ (트럭 대수)	구덩이 1	구덩이 2	구덩이 3	구덩이 4	내보낸 양 pᵢ
흙더미 A	1	1	2	1	5
흙더미 B	0	0	0	1	1
흙더미 C	1	0	0	0	1
흙더미 D	0	1	0	0	1
받은 양 qⱼ	2	2	2	2	8

칸 열여섯 개 가운데 0이 아닌 칸은 일곱 개인데, 흙더미 4 + 구덩이 4 − 1 = 7이라는 수는 우연이 아니다. 선형계획의 답은 조건들이 만드는 다면체의 꼭짓점에 놓이는데, 이 문제의 꼭짓점에서는 0이 아닌 칸이 많아야 (행 수 + 열 수 − 1)개다. 대부분의 칸이 0이므로, 나눠 보내기를 허락해도 실제로 갈라지는 흙더미는 많지 않다.

이렇게 출발점마다의 양 p와 도착점마다의 양 q가 주어졌을 때, 어디에서 어디로 얼마를 보낼지 적은 표(수송 계획) π 가운데 총비용이 가장 작은 것을 찾는 문제를 칸토로비치 문제 (나눠 보내기를 허락한 수송 문제 / Kantorovich problem)라 한다.

\min_{\textcolor{#ff5a78}{\pi} \ge 0}\; \sum_{i,j} \textcolor{#ff5a78}{\pi}_{ij}\, \textcolor{#8c564b}{C}_{ij} \quad \text{조건:}\quad \sum_j \textcolor{#ff5a78}{\pi}_{ij} = \textcolor{#c2408a}{p}_i,\qquad \sum_i \textcolor{#ff5a78}{\pi}_{ij} = \textcolor{#c2408a}{q}_j

\begin{array}{ll} \textcolor{#ff5a78}{\pi}_{ij} & \text{수송 계획: 출발점 } i \text{ 에서 도착점 } j \text{ 로 보내는 양} \\ \textcolor{#8c564b}{C}_{ij} & \text{한 단위를 } i \text{ 에서 } j \text{ 로 옮기는 비용} \\ \textcolor{#c2408a}{p}_i & \text{출발점 } i \text{ 에 있는 양 (행의 합)} \\ \textcolor{#c2408a}{q}_j & \text{도착점 } j \text{ 가 받을 양 (열의 합)} \end{array}

몽주 문제의 짝짓기 T는 각 행에 1이 하나뿐인 특별한 π이므로, 칸토로비치 문제는 몽주 문제를 품는다. 그러면서 몽주 문제가 막혔던 두 곳이 풀린다. 양이 달라도 조건을 맞추는 π는 늘 있고(모든 칸에 pᵢqⱼ/8을 넣으면 된다), n!가지를 세는 대신 1차식 조건 아래의 최소화가 되어 선형계획의 일반적인 풀이법으로 풀린다. 양을 p와 q의 합으로 나누면 π는 (출발점, 도착점) 쌍의 결합분포(두 가지를 함께 본 확률표, 예를 들어 「흙더미 A에서 구덩이 3으로」 같은 쌍마다의 확률)가 되고, 행의 합과 열의 합은 그 결합분포의 두 주변분포(한쪽만 본 확률, 예를 들어 「흙더미 A에서 출발할」 확률)가 된다. 그래서 칸토로비치 문제는 「두 분포를 주변분포로 갖는 결합분포 가운데 가장 싼 것 고르기」로도 읽힌다.

선 굵기가 그 길로 보내는 트럭 수다. 흙더미 A(5대분)가 구덩이 넷으로 나뉘어 1, 1, 2, 1대씩 간다. 몽주 문제로는 답이 없던 양이다(sources/optimal-transport/s2_kantorovich.py)

ML에서: 미니배치 안에서 노이즈와 그림을 짝짓기

플로우 매칭은 노이즈 샘플과 데이터 샘플을 짝지은 뒤 각 (노이즈, 데이터) 쌍을 잇는 직선 위의 속도를 신경망에게 가르친다. 보통은 미니배치 안에서 들어온 순서대로 쌍을 짓는다. 2023년 알렉산더 통(Alexander Tong)과 동료들, 그리고 아람-알렉상드르 풀라디안(Aram-Alexandre Pooladian)과 동료들은 따로, 미니배치 안의 노이즈 B개와 데이터 B개 사이에서 칸토로비치 문제를 풀어 쌍을 짓자고 했다. 데이터 전체를 한꺼번에 짝지을 수는 없으니 미니배치 안에서만이라도 옮기는 거리가 가장 짧은 짝짓기를 쓰자는 것이다. 양이 모두 같으므로 답은 짝짓기 하나가 되고, 짝지은 직선들이 덜 엇갈려 신경망이 배우는 흐름이 곧아진다.

문제 4. 빵 공장 둘, 카페 셋

빵 공장 1은 하루 5상자, 공장 2는 3상자를 굽고, 카페 가, 나, 다는 하루 2, 3, 3상자가 필요하다. 한 상자를 나르는 비용(천 원)은 공장 1에서 (가 4, 나 6, 다 9), 공장 2에서 (가 5, 나 3, 다 4)이다. (가) 공장 2가 자기에게서 가장 싼 카페부터 채우고, 남는 수요를 공장 1이 채우면 운반비는? (나) 운반비가 가장 작은 계획과 그 비용은? (다) 가장 좋은 계획에서 0이 아닌 칸은 몇 개이고, 0이 아닌 칸의 수는 무엇과 맞는가?

(가)는 공장 2에서 제일 싼 카페 나(3천 원)에 3상자를 다 보내요. 공장 1은 가에 2상자, 다에 3상자고요. 4 × 2 + 9 × 3 + 3 × 3 = 44천 원이에요. 각자 제일 싼 곳으로 보냈으니 괜찮지 않나요?

공장 1에서 카페 다로 가는 9천 원짜리 길이 세 번이나 쓰였네요. 그 길을 피할 수는 없었을까요?

공장 2가 다로 보내면 4천 원이에요. 그 대신 공장 2가 나에 못 보내면 공장 1이 나를 6천 원에 채워야 하고요.

그럼 한 상자를 그렇게 돌릴 때마다 얼마가 남죠?

다에서 상자마다 5천 원 아끼고 나에서 3천 원 더 쓰니까, 상자마다 2천 원 이득이에요. 공장 2의 3상자를 다 돌리면 공장 1이 가 2, 나 3, 공장 2가 다 3이고 8 + 18 + 12 = 38천 원이에요.

정수로 된 계획을 다 늘어놓아 봤는데 38이 가장 작아. 그다음이 40이고. 공장 2 입장에서 나가 제일 싸긴 해도, 공장 1과 비교하면 공장 2가 상대적으로 크게 유리한 곳은 다야. 공장 1과의 차이가 나에서는 3천 원, 다에서는 5천 원이니까.

(다)는요?

0이 아닌 칸이 셋이에요. 공장 2 + 카페 3 − 1 = 4보다 하나 적어요. 「많아야 행 + 열 − 1」이니까 맞고요. 공장 1이 가와 나 두 곳으로 갈라져 있고, 공장 2는 한 곳으로만 가요. 절대적으로 싼 곳이 아니라 상대적으로 유리한 곳에 맡겨야 한다는 게, 경제 수업에서 들은 비교 우위 얘기 같아요.

팀 과제에서 제일 빨리 끝낼 수 있는 일을 각자 고르면 어려운 일이 마지막에 남는데, 다른 사람에 비해 자기가 특히 잘하는 일을 고르게 하면 전체가 빨리 끝나잖아요. 「다른 사람에 비해 특히 잘하는 일」이 공장 1에 비해 공장 2가 특히 싼 카페예요.

문제 5. 트럭을 반씩 나누면 더 좋아질까

공사장의 비용 표에서 흙더미와 구덩이가 모두 트럭 1대분이다. 가장 짧은 배정(A→3, B→4, C→1, D→2, 14분)과 둘째 배정(A→2, B→4, C→1, D→3, 16분)이 있다. (가) 두 배정을 반씩 섞어, 흙더미 A와 D는 0.5대분씩 구덩이 2와 3으로 나눠 보내는 계획을 만들면 총 시간은? (나) 이 비용 표에서는 선형계획이 쪼개지 않은 14분짜리 배정을 돌려주었다. 다른 비용 표라면, 흙더미와 구덩이가 모두 1대분일 때 나눠 보내는 계획이 가장 좋은 배정보다 짧아질 수 있는가? (다) 왜 그런지 계획의 모양으로 설명하라.

이 표에서 14분이 그대로 나온 건 비용이 우연히 그렇게 생겨서일 거야. 나눠 보내면 선택지가 훨씬 넓어지니까, 다른 표라면 가장 좋은 배정보다 짧은 계획이 어딘가 있을 것 같아. 선택지가 늘면 최솟값은 줄거나 같잖아.

(가)부터 계산해요. A가 구덩이 2에 0.5대(6분 × 0.5), 구덩이 3에 0.5대(7분 × 0.5), D가 구덩이 2에 0.5대(2 × 0.5), 구덩이 3에 0.5대(5 × 0.5), 그리고 B→4(3), C→1(2)이요. 3 + 3.5 + 1 + 2.5 + 3 + 2 = 15분이에요. 14와 16의 딱 가운데네요.

가운데가 나온 게 우연일까요? 반씩 섞은 계획의 총 시간을 두 배정의 총 시간으로 적어 볼래요?

총 시간이 계획의 1차식이니까 (½ × 첫 배정 + ½ × 둘째 배정)의 총 시간은 ½ × 14 + ½ × 16이에요. 섞은 계획의 값은 섞은 배정들의 값의 가중평균이라서, 가장 작은 배정보다 작아질 수가 없어요. 그런데 아무 계획이나 배정들을 섞은 꼴로 쓸 수 있을까요?

행의 합과 열의 합이 모두 1인 표는 언제나 배정 몇 개를 가중평균한 꼴로 쓸 수 있다는 정리가 있어요. 버코프–폰 노이만 정리예요. 그걸 받아들이면 (나)의 답은요?

아니요예요. 어떤 계획이든 배정들의 가중평균이면, 그 총 시간도 배정들 총 시간의 가중평균이니까… 가장 좋은 배정 밑으로 못 내려가요.

이 표라면 14분 밑으로는 안 된다는 거네. 비용 표가 달라도?

응, 표가 달라도 그 표의 가장 좋은 배정 밑으로는 못 가. 아까 내가 선택지가 늘면 줄 거라고 했는데, 늘어난 것들이 모두 원래 것들의 「사이」에 있으면 최솟값은 그대로네. 선형계획의 답이 꼭짓점에 놓인다는 게 이거였어. 이 문제의 꼭짓점이 배정들이고.

실제로 배정 24가지를 무작위 비율로 섞은 계획을 2만 개 만들어 봤는데, 가장 짧은 것도 20.6분이었어요. 14분 근처에도 못 가요. 시험 점수 두 개를 어떤 비율로 섞어 평균을 내도 높은 점수보다 높아질 수 없잖아요. 섞은 계획이 그 평균이고, 배정 하나하나가 시험 점수예요.

문제 6. 미니배치 안에서 짝짓기

1차원 플로우 매칭의 미니배치 하나에 노이즈 z = (2.0, −2.6, 0.4, −0.6)과 데이터 x = (−2.1, 1.9, −2.1, 1.4)가 이 순서로 들어왔다. 노이즈 하나를 데이터 하나와 이을 때의 비용은 옮기는 거리의 제곱 (x − z)²이다. (가) 들어온 순서대로 짝지으면 제곱거리의 합은? (나) 제곱거리의 합이 가장 작은 짝짓기와 그 합은? (다) 두 짝짓기에서, 짝지은 직선 둘이 서로 엇갈리는 쌍은 각각 몇 개인가? (노이즈의 크기 순서와 데이터의 크기 순서가 뒤바뀐 두 직선을 엇갈린 쌍으로 센다.)

(가)는 2.0→−2.1, −2.6→1.9, 0.4→−2.1, −0.6→1.4라서 16.81 + 20.25 + 6.25 + 4 = 47.31이에요. 순서대로 짓는 게 보통의 조건부 플로우 매칭이니까, 평균적으로는 이 정도겠죠.

24가지 짝짓기의 평균은 얼마던가요?

계산해 보니 25.31이에요. 순서대로 한 짝짓기가 평균의 두 배 가까이 되네요. 이번 미니배치는 운이 나빴어요. 가장 작은 건 2.0→1.9, −2.6→−2.1, 0.4→1.4, −0.6→−2.1로 0.01 + 0.25 + 1 + 2.25 = 3.51이고요.

최적 짝짓기를 보면 노이즈를 작은 것부터 −2.6, −0.6, 0.4, 2.0으로 세우고 데이터도 작은 것부터 −2.1, −2.1, 1.4, 1.9로 세워서 순서대로 이은 거야. 1차원에서 제곱거리로 재면 작은 것끼리, 큰 것끼리 잇는 게 답이네.

(다)를 세어 보면 왜 그런지 보일 거예요.

순서대로 한 짝짓기는 여섯 쌍 가운데 다섯 쌍이 엇갈리고, 최적 짝짓기는 하나도 안 엇갈려요. 몽주가 적은 성질이 여기서도 나와요. 두 직선이 엇갈리면 도착점을 맞바꾸는 것이 제곱거리 합을 줄이니까, 최적 짝짓기에는 엇갈림이 남을 수 없어요.

미니배치 최적 수송이 노리는 게 이거구나. 엇갈림이 다섯 번이면 그 교차점마다 신경망이 서로 반대로 가는 속도의 평균을 배워야 하는데, 엇갈림이 없으면 짝지은 직선을 그대로 배우면 되니까요. 다만 미니배치 네 개 안에서 정한 짝짓기가 데이터 전체로 보면 최적이 아닐 수는 있겠네요. 조별 과제 조를 반마다 따로 짜면 반 안에서는 최선이어도 학년 전체로 보면 더 좋은 조가 있을 수 있는 것처럼요.