전체 단모듈성

최적설계 수치해석 마지막 수정: 2026-08-13 04:38:52

1. 개요[편집]

전체 단모듈성 Total Unimodularity
정의	모든 정방 부분행렬의 행렬식이 $0, +1, -1$
핵심 결과	호프만-크루스칼 정리(1956) — 완화 다면체가 정수 다면체
대표 TU 족	방향그래프 접속행렬 · 이분 그래프 접속행렬 · 구간행렬 · 네트워크 행렬
판정	구일라-우리 조건(1962) · 시모어 분해(1980)로 다항시간 인식
실용적 의미	정수 제약을 붙일 필요 없이 LP 한 번으로 끝

전체 단모듈성(total unimodularity)은 정수 행렬 $A$ 의 모든 정방 부분행렬의 행렬식이 $0$ , $+1$ , $-1$ 중 하나라는 성질이다. 이 조건을 만족하는 행렬을 전체 단모듈 행렬(totally unimodular matrix, TU 행렬)이라 부른다. $1\times1$ 부분행렬도 정방 부분행렬이므로, TU 행렬의 모든 성분은 자동으로 $\{0,+1,-1\}$ 에 들어간다.

정의만 보면 선형대수의 사소한 잡기술 같지만, 이 성질의 값어치는 딱 한 문장으로 요약된다. 계수행렬이 TU면 정수계획을 그냥 선형계획으로 풀어도 정수해가 나온다. 정수계획법은 NP-난해이고 선형계획법은 다항시간이니, TU는 이 둘 사이를 가르는 경계선 중 가장 깨끗하게 정리된 것이다. 최대유량의 정수성 정리, 이분 매칭이 0/1로 나오는 이유, 수송 문제의 배정이 항상 정수인 이유가 전부 이 하나에서 나온다.¹

2. 왜 꼭짓점이 정수가 되는가[편집]

$P = \{x : Ax \le b,\ x \ge 0\}$ 의 꼭짓점(기저 실행가능해)은 $A$ 의 어떤 정칙 정방 부분행렬 $B$ 에 대해 $x_B = B^{-1}b_B$ , 나머지 성분은 0인 형태다. 여기에 크라메르 법칙을 그대로 대입하면

x_j = \frac{\det B_j}{\det B}

이고, $B_j$ 는 $B$ 의 한 열을 $b_B$ 로 갈아끼운 행렬이다. $A$ 가 TU면 $\det B = \pm 1$ 이므로 분모가 사라진다. $b$ 가 정수 벡터이면 $\det B_j$ 도 정수이니 $x_j$ 가 정수다. 논증이 이게 전부다 — 정수성이 어려운 정리에서 나오는 게 아니라 행렬식이 1이라 나눗셈이 없어지기 때문이다.

더 정확히는 역행렬 공식 $B^{-1} = \mathrm{adj}(B)/\det B$ 에서 수반행렬 성분이 소행렬식(정수)이고 분모가 $\pm1$ 이므로 $B^{-1}$ 자체가 정수행렬이 된다. 이 관점이 다음 정리로 이어진다.

호프만-크루스칼 정리(Hoffman–Kruskal, 1956): 정수 행렬 $A$ 에 대해, 모든 정수 벡터 $b$ 에 대해 $\{x : Ax \le b,\ x \ge 0\}$ 이 정수 다면체가 되는 것과 $A$ 가 TU인 것은 동치다.

방향이 양쪽이라는 게 중요하다. “TU면 정수해”는 위에서 봤고, 역방향은 “어떤 $b$ 에서도 안 깨지려면 TU일 수밖에 없다”는 뜻이라 TU가 이 목적에 대해 정확히 필요충분한 조건임을 못박는다. 실용적으로 읽으면 이렇다 — 우변 데이터가 정수인 한 무슨 값을 넣든 안전하다. 용량을 바꾸든 수요를 바꾸든 모델을 다시 검증할 필요가 없다.

그리고 쌍대 쪽도 공짜로 따라온다. $A$ 가 TU면 $A^\top$ 도 TU이므로 쌍대문제의 최적해도 정수다. 최대유량-최소절단, 쾨니그 정리(최대 매칭 = 최소 정점 덮개) 같은 “최대-최소 등식”들이 왜 정수끼리 딱 맞아떨어지는지가 여기서 설명된다.

3. 대표적인 TU 족[편집]

정의를 그대로 확인하려면 부분행렬이 지수적으로 많아 곤란하다. 실무에서는 알려진 TU 족에 해당하는지를 본다.

방향그래프의 접속행렬. 정점 × 간선 행렬에서 간선 $(u,v)$ 열은 $u$ 행에 $-1$ , $v$ 행에 $+1$ , 나머지는 0이다. 항상 TU다. 증명은 부분행렬 크기에 대한 귀납으로 간다 — 모든 열이 정확히 $+1$ 하나와 $-1$ 하나를 가지면 행 전체 합이 0이라 행렬식이 0이고, 어떤 열에 0이 아닌 성분이 하나뿐이면 그 열로 여인수 전개해 한 단계 줄인다. 이것이 네트워크 흐름의 정수성 정리 전체를 지탱하는 사실이며, 최단경로·최대유량·최소비용 흐름·수송 문제가 모두 정수 최적해를 갖는 이유다.

이분 그래프의 접속행렬. 무향 그래프의 접속행렬(간선 열에 양 끝점 행이 $+1$ )은 그래프가 이분일 때에 한해 TU다. 필요조건 쪽이 재미있다. 홀수 길이 사이클 $C_{2k+1}$ 의 접속행렬은 정방행렬이고 행렬식이 $\pm 2$ 라서 곧장 TU가 깨진다. 충분조건은 이분 그래프에서 정점을 두 색으로 나눈 뒤 한쪽 행에 $-1$ 을 곱하면 방향그래프 접속행렬과 같은 꼴이 된다는 것으로 보인다. 삼각형 하나가 정수성을 파괴한다는 이 사실이 이분 매칭은 LP로 풀리는데 일반 매칭은 홀수집합(blossom) 부등식을 따로 붙여야 하는 이유다.

구간행렬(연속 1 성질). 각 행의 1들이 연속해서 나타나는 0/1 행렬은 TU다. “시간 구간 $[s_i, t_i]$ 동안 자원을 쓴다”는 형태의 제약이 정확히 이 모양이라, 구간 스케줄링·설비 배치·유전자 물리지도 문제가 여기 걸린다. 열 방향으로 연속 1이어도 마찬가지(전치가 TU이므로).

네트워크 행렬. 신장트리를 하나 잡고 비트리 간선을 트리 경로로 표현했을 때 나오는 $\pm1$ 행렬로, 위의 접속행렬 부류를 포함하는 더 넓은 족이다. 터트가 정의했고 시모어 분해 정리에서 기본 벽돌 역할을 한다.

연산에 대한 닫힘성. TU 행렬은 다음 연산에 대해 닫혀 있어서, 하나를 알면 여럿을 얻는다.

연산	TU 유지
전치	유지
행 또는 열의 부호 반전	유지
행/열의 순서 교환, 복제	유지
단위행렬 열 붙이기 (슬랙 변수 추가)	유지
0인 행/열 추가, 행/열 삭제	유지
두 TU 행렬을 나란히 붙이기	깨질 수 있음

슬랙 변수를 붙여도 유지된다는 항목이 실무에서 특히 중요하다. $Ax \le b$ 를 $Ax + s = b$ 로 표준형화해도 정수성이 살아남는다는 뜻이니까. 반대로 마지막 줄이 TU 판정을 어렵게 만든다 — 부분 모델이 각각 TU여도 합쳐 놓으면 아니다. 흐름 제약과 배낭 제약을 한 모델에 넣는 순간 대개 여기서 깨진다.

4. 판정하는 법[편집]

구일라-우리 조건(Ghouila-Houri, 1962)이 고전적인 특성화다.

$A$ 가 TU $\iff$ 행의 임의의 부분집합 $R$ 을 $R_1, R_2$ 로 나눠서 $\sum_{i\in R_1} a_{i} - \sum_{i\in R_2} a_{i}$ 의 모든 성분이 $\{0,+1,-1\}$ 에 들어가게 할 수 있다.

행마다 $\pm$ 부호를 잘 배정해 합이 셋 중 하나로 눌리게 할 수 있느냐는 조건이며, 열에 대해 진술해도 동치다. 특정 구조가 왜 TU인지를 손으로 증명할 때 가장 쓸모 있는 도구다(방향그래프 접속행렬에 적용해 보면 $R_1 = R$ , $R_2 = \varnothing$ 이 그냥 통한다).

다만 부분집합을 훑는 정의라 그대로는 지수적이다. 다항시간 인식 알고리즘은 시모어의 분해 정리(Seymour, 1980)에서 나온다. 요지는 “모든 TU 행렬은 네트워크 행렬과 그 전치, 그리고 두 개의 특정한 $5\times5$ 예외 행렬로부터 1-합·2-합·3-합이라는 세 가지 결합 연산만으로 만들어진다”는 것이고, 이 분해를 거꾸로 찾아 내려가면 TU 여부를 다항시간에 판정할 수 있다(트루엠퍼의 구현). 이론적으로는 완결됐지만 구현이 무거워서, 현업 모델러가 실제로 하는 일은 알려진 족에 대입해 보기와 작은 반례 찾기다.²

5. TU가 아니면 그다음은[편집]

대부분의 실전 모델은 TU가 아니다. 배낭 제약 하나, 고정비용 하나, “이 둘 중 하나만” 하는 논리 제약 하나면 충분히 깨진다. 그러면 LP 완화의 최적해가 분수로 나오고, 그 분수해와 진짜 정수 최적 사이의 간극이 정수성 간극(integrality gap)이다. 여기서부터가 정수계획의 본론이다.

절단평면법 — 완화해만 잘라내고 정수해는 전부 살리는 부등식을 계속 붙여 완화 다면체를 정수 껍질 쪽으로 조인다. TU가 “처음부터 정수 껍질이었다”는 상황이라면, 절단은 “정수 껍질을 필요한 부분만 사후에 복원한다”는 접근이다.
분지한정법 — 분수 변수를 골라 $x_j \le \lfloor x_j^* \rfloor$ 와 $x_j \ge \lceil x_j^* \rceil$ 로 갈라 트리를 판다. 둘을 합친 분지절단(branch-and-cut)이 오늘날 모든 상용 MIP 솔버의 골격이다.
더 넓은 정수성 조건 — TU는 “모든 $b$ 에 대해”라는 강한 요구라서, 특정 $b$ 에서만 정수 다면체가 되는 경우를 놓친다. 완전균형 행렬·균형 행렬, 완전 쌍대 정수성(TDI), 그리고 완전 그래프(perfect graph)의 클리크 제약 등이 그런 예다. 일반 매칭 다면체가 홀수집합 부등식을 붙이면 정수 다면체가 되는 것도 TU가 아니면서 정수인 대표 사례다.
모델링으로 되찾기 — 같은 문제라도 정식화를 바꾸면 구조가 살아날 때가 있다. 시간 지표를 흐름 변수로 다시 쓰거나, 제약 순서를 재배열해 연속 1 성질을 만들거나, 라그랑주 완화로 “TU인 부분”만 남기고 나머지를 승수로 밀어내는 식이다. 완화 문제가 흐름 문제로 떨어지면 서브그래디언트 한 번당 비용이 극적으로 싸진다.

반대 방향의 교훈도 있다. 정수 제약이 없다고 안심하면 안 되고, 정수 제약이 있다고 겁먹을 필요도 없다. 계수행렬이 TU인데 굳이 변수를 정수로 선언하면 솔버가 쓸데없이 분지 트리를 파느라 느려지는 경우가 실제로 있다. 반대로 정수 다품종 흐름처럼 “흐름이니까 정수겠지”라고 방심했다가 NP-난해에 정면으로 부딪히기도 한다 — 상품별 접속행렬을 쌓아 올리는 순간 위 표의 마지막 줄이 발동하기 때문이다.³

6. 관련 문서[편집]

최적화 세계에서 “공짜 점심”이라는 말이 허용되는 몇 안 되는 자리다. 제약을 하나도 추가하지 않았는데 정수해가 나오는 것이니, 정확히는 공짜가 아니라 모델 구조에 미리 지불된 값이다. ↩
시모어 정리는 조합론의 기념비적 결과지만, “그래서 우리 모델이 TU인가요?”라는 질문에 실무자가 이걸 돌리는 일은 거의 없다. 대부분은 반례를 하나 찾아 “아니네요”로 끝나고, 못 찾으면 “그런 것 같은데 확신은 없으니 정수 선언 유지”로 끝난다. ↩
그래서 한 상품일 때는 다항시간, 두 상품부터는 NP-난해라는 극적인 절벽이 생긴다. 접속행렬 두 개를 대각으로 쌓고 공유 용량 제약 한 줄을 얹었을 뿐인데 복잡도 등급이 바뀌는 것을 보면, TU가 얼마나 부서지기 쉬운 성질인지 실감이 난다. ↩