절단평면법

1. 개요

절단평면법(cutting plane method)은 풀기 어려운 최적화 문제를 완화 문제로 바꿔 푼 다음, 완화해만 콕 집어 제거하고 원래 문제의 실행가능해는 단 하나도 잃지 않는 부등식을 제약으로 덧붙여 다시 푸는 과정을 반복하는 알고리즘 계열이다. 덧붙이는 부등식이 실행가능 영역을 칼로 한 겹 깎아내는 모양이라 절단(cut) 또는 절단평면이라 부른다.

가장 유명한 무대는 정수계획법이다. 정수 제약을 떼어낸 LP 완화를 풀면 $x_1 = 3.5$ 같은 분수해가 나오는데, 이 점만 잘라내고 정수점은 전부 살려두는 부등식을 계속 붙이다 보면 LP의 최적 꼭짓점 자체가 정수가 된다. 여기서 핵심은 “자르는 방법”이 아니라 **“어떤 부등식을 자동으로 찾아내느냐”**이며, 이 문서는 그 절단 생성(cut generation) 쪽에 집중한다. 트리를 파고 내려가는 분지한정법 쪽 이야기는 정수계획법 문서에 있다.¹

2. 정수 껍질과 유효 부등식, 그리고 면

정수계획 $\max\{c^\top x : Ax \le b,\, x \in \mathbb{Z}^n_+\}$의 실행가능 집합을 $S$라 하자. 이론적으로는 게임이 이미 끝나 있다. $S$의 정수 껍질 $\operatorname{conv}(S)$는 (유리수 데이터라면) 다면체이고, 그 위에서 선형계획을 풀면 정수 최적해가 꼭짓점으로 튀어나온다. 즉 정수계획은 “$\operatorname{conv}(S)$의 부등식 표현을 안다면” 그냥 선형계획법이다.

문제는 그 표현이 지수적으로 많고, 대부분의 경우 아무도 모른다는 것. 그래서 현실적으로는 필요한 부등식만 그때그때 조달한다. 어떤 부등식 $\pi^\top x \le \pi_0$가 $S$의 모든 점에서 성립하면 유효 부등식(valid inequality)이라 하고, 유효 부등식이 만드는 면

$$F = \{ x \in \operatorname{conv}(S) : \pi^\top x = \pi_0 \}$$

의 차원이 $\dim \operatorname{conv}(S) - 1$이면 이 부등식을 면(facet, 패싯)이라 부른다. 패싯은 $\operatorname{conv}(S)$를 기술하는 데 없으면 안 되는 부등식이고, 나머지 유효 부등식은 전부 패싯들의 결합으로 유도된다. 그래서 절단 연구의 절반은 “이 문제 구조에서 패싯을 주는 부등식 족은 무엇인가”를 알아내는 다면체 조합론이다.

3. 고모리 분수 절단 — 태블로 한 행에서 절단이 나온다

1958년 랠프 고모리(Ralph Gomory)는 어떤 정수계획에서든 기계적으로 절단을 뽑는 방법을 내놓았다. 재료는 심플렉스법이 끝난 최종 태블로의 한 행뿐이다. 기저변수 $x_{B(i)}$에 대한 행은

$$x_{B(i)} + \sum_{j \in N} \bar{a}_{ij} x_j = \bar{b}_i$$

이고, 현재 해에서는 비기저변수 $x_j\ (j \in N)$가 전부 0이라 $x_{B(i)} = \bar{b}_i$다. 이 $\bar{b}_i$가 분수라고 하자. 각 계수를 정수부와 소수부로 쪼갠다. $\bar{a}_{ij} = \lfloor \bar{a}_{ij} \rfloor + f_{ij}$, $\bar{b}_i = \lfloor \bar{b}_i \rfloor + f_i$ ($0 \le f_{ij} < 1$, $0 < f_i < 1$). 정수부만 왼쪽에 모으면

$$\underbrace{x_{B(i)} + \sum_{j \in N} \lfloor \bar{a}_{ij} \rfloor x_j - \lfloor \bar{b}_i \rfloor}_{\text{정수해에서는 반드시 정수}} \;=\; f_i - \sum_{j \in N} f_{ij} x_j$$

가 된다. 좌변은 정수들의 정수 결합이므로 실행가능한 정수해에서 항상 정수다. 따라서 우변도 정수여야 한다. 그런데 $x_j \ge 0$, $f_{ij} \ge 0$이므로 우변은 $f_i < 1$을 넘지 못하고, 정수이면서 1 미만이면 0 이하다. 정리하면

$$\sum_{j \in N} f_{ij}\, x_j \;\ge\; f_i$$

이것이 고모리 분수 절단이다. 모든 정수해가 만족한다는 것은 방금 증명했고, 현재 LP 해는 $x_N = 0$이라 좌변이 0, 우변이 $f_i > 0$이므로 정확히 위반된다. 완화해 하나를 잘라내면서 정수해는 하나도 안 잃는, 절단의 정의를 그대로 만족하는 부등식이 태블로 한 줄에서 공짜로 떨어진 셈이다.

같은 아이디어를 승수 $u \ge 0$로 일반화한 것이 쇼바탈-고모리 절단이다. $Ax \le b$에서 $u^\top A x \le u^\top b$가 유효하고, $x$가 정수라면 좌변 계수를 내림해도 되므로 $\lfloor u^\top A \rfloor x \le \lfloor u^\top b \rfloor$가 유효하다. 이 연산을 반복해서 얻는 최소 횟수를 쇼바탈 랭크라 하고, 유계 유리 다면체에서는 랭크가 유한하다는 것이 알려져 있다. 즉 이론적으로 절단만으로도 끝난다. 실전이 문제일 뿐.

4. 절단의 계열들

범용 고모리 절단은 아무 구조나 먹지만, 그만큼 무디다. 실전 솔버는 제약의 구조를 알아보고 전용 절단을 쏟아붓는다.

• 배낭 커버 부등식: $\sum_{j \in N} a_j x_j \le b$, $x \in \{0,1\}^n$에서 $\sum_{j \in C} a_j > b$인 커버 $C$가 있으면 $\sum_{j \in C} x_j \le |C| - 1$이 유효하다. “다 넣으면 가방이 터진다”는 자명한 사실이 부등식이 되는 것. 여기에 리프팅을 걸어 $C$ 밖 변수의 계수를 키우면 패싯으로 올라간다. 배낭 문제 구조가 들어간 모든 모델에서 쓰인다.
• 클리크 부등식: 이진변수들의 충돌 그래프(둘 다 1이 될 수 없는 쌍을 간선으로)에서 클리크 $K$를 찾으면 $\sum_{j \in K} x_j \le 1$. 스케줄링·배정 모델에서 대량으로 나온다.
• MIR(mixed integer rounding): 혼합정수의 기본 벽돌. $x \in \mathbb{Z}$, $s \ge 0$, $x + s \ge b$이면 $f = b - \lfloor b \rfloor > 0$일 때 $x + \frac{s}{1 - f} \ge \lceil b \rceil$이 유효하다. 흐름 커버·고모리 혼합정수(GMI) 절단이 전부 이 한 부등식의 변형으로 유도된다.
• 문제 특화 패싯: 외판원 문제의 부분순회 제거 부등식과 빗(comb) 부등식, 네트워크 흐름 기반 모델의 흐름 커버 등. 계수행렬이 전체 단모듈이면 애초에 절단이 필요 없다.

5. 분리 문제 — 절단을 “찾는” 것이 곧 최적화다

부등식 족을 안다고 끝이 아니다. 지수적으로 많은 후보 중에서 지금 이 점 $x^*$가 위반하는 것 하나를 실제로 찾아내야 한다. 이것이 분리 문제(separation problem)다. 입력은 점 $x^*$, 출력은 “위반된 부등식 하나” 또는 “없음” 판정.

그로치·로바스·슈라이버(1981)의 타원체법 논증이 여기서 결정적이다. 어떤 다면체 족에 대해 분리 문제가 다항시간에 풀리는 것과 그 위에서의 최적화가 다항시간에 풀리는 것은 등가다. 절단을 빨리 찾을 수 있으면 최적화가 빨라지고, 최적화가 어려우면 분리도 어렵다는 뜻이라, “패싯을 다 알아냈으니 이제 다 됐다”는 낙관을 깔끔하게 차단한다. TSP의 부분순회 제거 부등식은 최소절단 계산으로 다항시간 분리가 되지만, 빗 부등식의 분리는 일반적으로 어렵고 실전에서는 휴리스틱 분리를 쓴다.

6. 분지절단 — 그리고 볼록 계획으로의 확장

순수 고모리 절단만 계속 돌리면 어떻게 되는가. 답은 “잘 안 된다”였다. 절단들이 점점 서로 평행해지면서 잘리는 양이 급감하고(tailing off), 분수 계수의 분모가 커지면서 태블로가 수치적으로 뭉개진다. 1960~80년대 내내 고모리 절단은 “교과서용”이라는 평을 들었다.

부활은 분지절단(branch-and-cut)에서 일어났다. 파드베르그와 리날디가 대규모 TSP에 절단과 분지를 결합해 성공한 뒤, 발라스·세리아·코르누에졸스(1996)가 고모리 혼합정수 절단을 분지한정 트리 안에서 절단 풀 관리와 함께 쓰면 여전히 강력하다는 것을 보이면서 완전히 명예회복했다. 오늘날 상용 MIP 솔버는 예외 없이 분지절단이다 — 루트 노드에서 여러 계열의 절단을 라운드로 나눠 생성해 완화 간극을 크게 줄이고, 효과 없는 절단은 다시 버리며, 절단 추가 후 재최적화는 웜스타트가 잘 먹히는 쌍대 심플렉스법으로 처리한다.²

절단평면 아이디어는 정수 문제 밖에서도 산다. 켈리(1960)의 볼록 계획용 절단평면법은 볼록 목적함수를 여러 개의 접평면(열분할 가능한 아래근사)으로 대체하고, 최소점에서 새 열분할 접평면을 하나 더 얹는 것을 반복한다. 볼록 최적화의 정석적 알고리즘이지만 수렴이 느리고 반복점이 심하게 요동친다는 약점이 있어, 근접항 $\frac{\mu}{2}\|x - \hat{x}\|^2$으로 안정화한 **번들법**으로 발전했다. 벤더스 분해와 라그랑주 완화의 쌍대도 결국 “쌍대 공간에서 절단을 모으는” 절단평면법이다.³

7. 관련 문서

• 정수계획법 · 선형계획법 · 조합 최적화
• 외판원 문제 · 네트워크 흐름
• 볼록 최적화 · 내점법 · 활성집합법 · 이차계획법
• 최적설계 · 타부 서치

8. Footnotes

1. 분지한정법이 “해 공간을 쪼개서 정복”이라면 절단평면법은 “완화 공간을 깎아서 정복”이다. 둘은 경쟁 관계처럼 보이지만 실제로는 30년 넘게 한 몸으로 붙어 다니고 있다. 사이가 나쁜 것보다 훨씬 무섭다. ↩

2. 절단을 무한정 넣으면 LP 자체가 무거워져 손해다. 그래서 솔버 내부에는 “절단 효율(cut efficacy)”, 즉 절단이 현재 해로부터 얼마나 떨어져 있는지를 잰 뒤 성적이 나쁜 절단을 쫓아내는 관리자가 붙어 있다. 절단도 성과평가를 받는 세상이다. ↩

3. 켈리의 방법이 요동치는 이유는 직관적이다. 아래근사의 최소점은 항상 아직 접평면이 하나도 없는 미개척지에 찍히므로, 매 반복마다 지도의 반대편 끝으로 순간이동한다. 근접항은 “어제 있던 곳에서 너무 멀리 가지 마라”는 벌점이고, 이게 번들법의 전부라고 해도 크게 틀리지 않다. ↩