조합 최적화

최적설계 수치해석 마지막 수정: 2026-07-29 04:35:58

1. 개요[편집]

조합 최적화(combinatorial optimization)는 실행가능해의 집합이 유한하거나 셀 수 있는 이산 집합인 최적화 문제, 그리고 그것을 다루는 이론과 알고리즘 전체를 가리킨다. 형식적으로는 유한 집합족 $\mathcal{F} \subseteq 2^{E}$ 와 비용함수 $c$ 가 주어졌을 때

\min_{S \in \mathcal{F}} \; c(S)

를 푸는 문제다. 순서(순열), 부분집합, 배정, 분할, 그래프 구조처럼 연속적으로 조금씩 움직일 수 없는 대상 위에서 최적을 찾는다는 점이 볼록 최적화나 순차 이차계획법 같은 연속 최적화와 결정적으로 다르다. 기울기가 없으니 경사하강법이 통하지 않고, 대신 조합 구조 자체를 파고들어야 한다.

“유한하면 다 세어보면 되잖아?”라는 반문이 바로 나오는데, 그게 안 되니까 학문이 됐다. 도시 30개짜리 외판원 문제의 경로 수는 $29!/2 \approx 4.4\times10^{30}$ 개로, 1나노초에 하나씩 세도 우주 나이보다 오래 걸린다. 유한 = 쉬움이 아니다는 것이 이 분야의 첫 번째 교훈이다.¹

2. 대표 문제들[편집]

외판원 문제(TSP): 모든 도시를 정확히 한 번씩 방문하고 돌아오는 최단 순회. 조합 최적화의 마스코트.
배낭 문제(knapsack): 무게 한도 안에서 가치 합을 최대화하는 물건 부분집합 고르기.
정점덮개(vertex cover): 모든 간선의 한쪽 끝을 덮는 최소 정점 집합. 감시 카메라 배치의 추상형.
그래프 채색: 인접한 정점이 같은 색을 갖지 않도록 최소 색으로 칠하기. 주파수 할당, 레지스터 할당, 시험 시간표가 전부 이것.
스케줄링: 기계·작업·선후관계·납기 조합. 변형이 수백 종이라 분류 표기법( $\alpha|\beta|\gamma$ )이 따로 있을 정도.
집합덮개(set cover), 최대절단(max-cut), 시설 입지, 차량 경로(VRP), 빈 패킹(bin packing) 등.

반대로 다항시간에 풀리는 조합 문제도 많다는 게 중요하다. 최소 신장트리, 최단경로, 네트워크 흐름의 최대유량·최소비용흐름, 이분 매칭, 일반 그래프 매칭(에드먼즈의 blossom 알고리즘)이 그렇다. 이들은 대개 강한 구조적 성질을 갖는다 — 예컨대 실행가능 집합족이 매트로이드를 이루면 단순 탐욕 알고리즘이 항상 최적을 준다는 정리(로도-에드먼즈)가 있고, 최소 신장트리의 크러스컬 알고리즘이 정확히 그 사례다. 어떤 문제가 쉽고 어떤 문제가 어려운지를 가르는 경계선을 그리는 것 자체가 이 분야의 큰 주제다.

3. 복잡도 — 왜 어려운가[편집]

P는 다항시간에 풀리는 판정 문제, NP는 답이 주어지면 다항시간에 검증되는 판정 문제 집합이다. NP에 속하면서 NP의 모든 문제가 다항시간에 환원되는 문제를 NP-완전, 판정 문제로 한정하지 않고 그 난이도 이상인 문제를 NP-난해라 한다.

1971년 쿡(Cook)이 SAT의 NP-완전성을 보였고, 1972년 카프(Karp)가 21개 조합 문제가 NP-완전임을 보이면서 판이 정리됐다. 위에 든 대표 문제 중 TSP·배낭·정점덮개·채색·집합덮개·max-cut이 전부 여기 들어간다. $\mathrm{P} \ne \mathrm{NP}$ 라는 통설이 맞다면, 이들에 대해 최악의 경우 다항시간에 최적해를 주는 알고리즘은 존재하지 않는다.

여기서 실무자가 새겨야 할 뉘앙스가 있다. NP-난해는 최악 사례에 대한 진술이지, “내 문제 인스턴스가 안 풀린다”는 뜻이 아니다. 실제로 Concorde 솔버는 도시 85,900개짜리 TSP 인스턴스의 증명된 최적해를 구했다. 최악 복잡도가 지수적이라는 사실과, 구조가 있는 실제 인스턴스가 잘 풀린다는 사실은 얼마든지 공존한다.

4. 정확 알고리즘[편집]

최적해를 증명과 함께 내놓는 접근들.

동적 계획법: 부분 문제의 최적 부분구조를 이용한다. 배낭 문제는 $O(nW)$ 에 풀리는데( $W$ 는 용량), 이건 입력의 비트 수가 아니라 값에 비례하므로 의사다항(pseudo-polynomial)이라 부른다. TSP의 헬드-카프 DP는 $O(n^2 2^n)$ 으로, 전수조사 $O(n!)$ 보다는 비교할 수 없이 낫지만 여전히 지수적이다. 자세히는 동적 계획법 참고.
분지한정법: 실행가능 영역을 재귀적으로 쪼개고, 하계가 현재 최선(incumbent)보다 나쁜 가지를 통째로 잘라낸다. 하계를 어떻게 뽑느냐가 성능의 전부다.
절단평면 / 분지절단: 문제를 정수계획법으로 정식화한 뒤, 유효 부등식을 계속 추가해 LP 완화를 정수 껍질 쪽으로 조인다. TSP의 부분순회 제거 부등식·빗(comb) 부등식이 유명한 예이고, Concorde의 위력이 정확히 여기서 나온다.
제약 계획(CP)과 SAT/SMT: 전파(propagation) + 백트래킹. 스케줄링·배치처럼 “실행가능해 찾기”가 주된 난관인 문제에서 강하다. 현대 SAT 솔버의 CDCL은 수백만 변수 인스턴스를 일상적으로 처리한다.

5. 근사 알고리즘[편집]

최적을 포기하되 얼마나 나쁠 수 있는지 수학적으로 보증하는 노선이다. 알고리즘이 $\rho$ -근사라는 것은 최소화 문제에서 항상 $\text{ALG} \le \rho \cdot \text{OPT}$ 임을 뜻한다.

정점덮개 2-근사: 극대 매칭의 양 끝점을 전부 넣으면 끝. 세 줄짜리 알고리즘이 2배 보증을 준다.
근사 알고리즘의 대표작, 크리스토피데스 알고리즘: 삼각부등식을 만족하는 거리(metric TSP)에서 $3/2$ -근사를 준다. 최소 신장트리를 만들고, 홀수 차수 정점들끼리 최소 가중 완전 매칭을 붙여 모든 차수를 짝수로 만든 뒤, 오일러 회로를 지름길로 단축한다. 1976년 결과가 40여 년간 최고 기록으로 남아 있다가, 2021년에야 $3/2 - \varepsilon$ 이 증명됐는데 그 $\varepsilon$ 이 $10^{-36}$ 규모라 실용적 의미는 사실상 없다.²
배낭 문제의 FPTAS: 가치를 적당히 반올림해 DP를 돌리면 임의의 $\varepsilon>0$ 에 대해 $(1-\varepsilon)$ -근사를 다항시간에 얻는다. 근사 난이도의 스펙트럼에서 가장 착한 등급.
근사 불가능성: 반대로 한계도 증명된다. 집합덮개는 $(1-o(1))\ln n$ 보다 잘 근사하는 것이 NP-난해이고, 일반 TSP(삼각부등식 없음)는 어떤 상수 비율로도 근사 불가능하다. “적당히 잘하는 것”조차 어려운 문제가 있다는 얘기.

6. 완화와 쌍대성[편집]

정확 알고리즘의 하계는 대부분 완화에서 나온다. 어려운 제약을 풀거나 목적에 흡수시켜 쉬운 문제로 바꾼 뒤, 그 최적값을 원문제의 하계로 쓰는 것이다.

LP 완화: 정수 제약을 지우고 선형계획법으로 푼다. 완화 간극이 작을수록 좋은 하계.
라그랑주 완화: 성가신 제약을 승수로 목적함수에 얹고, 남은 구조 좋은 문제만 푼다. TSP의 헬드-카프 하계가 대표작으로, 1-트리 완화에 승수 갱신(subgradient)을 돌리면 최적값의 99% 이상에 육박하는 하계가 나온다.
SDP 완화와 무작위 반올림: 0/1 변수를 단위구 위 벡터로 올려 반정부호 문제로 완화한 뒤, 무작위 초평면으로 다시 0/1로 내린다. 괴만스-윌리엄슨의 max-cut $0.878$ -근사가 이 기법의 원형이며, 유일 게임 추측이 참이라면 이 상수가 최선이라는 것까지 알려져 있다. 자세히는 반정부호 계획법 참고.

완화는 하계뿐 아니라 좋은 실행가능해도 준다. LP 완화 해를 확률로 해석해 무작위 반올림하면 기댓값 보증이 붙은 근사해가 나온다.

7. 메타휴리스틱[편집]

보증을 포기하고 “그럴듯한 해를 빨리”에 올인하는 노선. 산업 현장에서 실제로 가장 많이 돌아가는 부류이기도 하다.

담금질 모사: 나빠지는 이동도 확률 $\exp(-\Delta E/T)$ 로 받아들이며 온도를 낮춘다. 온도 스케줄이 충분히 느리면 전역 최적 수렴이 이론적으로 보장되지만, 그 “충분히 느리게”가 전수조사보다 느리다는 게 함정.
유전 알고리즘: 해 집단에 선택·교차·돌연변이를 반복. 순열 표현에서 교차 연산자 설계가 성능의 대부분을 좌우한다.
타부 서치: 최근 방문한 이동을 금지 목록에 넣어 같은 국소 최적을 맴도는 것을 막는다. 스케줄링·차량 경로에서 특히 강하다.
개미 군집 최적화(ACO): 좋은 경로에 페로몬을 쌓아 확률적 구성 편향을 학습한다. TSP·라우팅에서 출발한 계열.
입자 군집 최적화 및 국소탐색 계열(2-opt, Lin-Kernighan): 특히 LKH 구현은 대형 TSP에서 최적에 1% 이내로 붙는 해를 초 단위로 낸다.

메타휴리스틱을 쓸 때 반드시 기억할 것. 이들은 하계를 주지 않는다. 나온 해가 최적 대비 2% 떨어졌는지 200% 떨어졌는지 알 방법이 없으므로, 가능하면 LP·라그랑주 완화로 하계를 따로 뽑아 간극을 보고하는 것이 성실한 태도다. 또 공짜 점심은 없다(No Free Lunch) 정리에 따라, 모든 문제에 걸쳐 평균적으로 우월한 범용 탐색 알고리즘은 존재하지 않는다. 성능은 문제 구조를 얼마나 이용했느냐에서 나온다.³

8. 시뮬레이션·공학과의 접점[편집]

조합 최적화는 순수 OR의 물건처럼 보이지만 시뮬레이션 현장 곳곳에 박혀 있다.

메시 분할과 재정렬: 대규모 유한요소법 해석을 병렬화하려면 메시를 통신량 최소로 쪼개야 하는데, 이게 균형 그래프 분할(NP-난해)이다. 희소행렬의 대역폭을 줄이는 정점 재배열도 조합 문제. 병렬 컴퓨팅·희소행렬 참고.
이산 설계변수: 표준 규격 판재 두께, 볼트 개수, 부재 유무처럼 카탈로그에서 골라야 하는 최적설계 변수는 본질적으로 이산이다. 연속 최적화로 풀고 반올림하면 실행가능성이 깨지기 십상.
경로 계획: 게임의 내비게이션 메시 위 최단경로, 로봇 작업 순서 결정이 각각 그래프 최단경로와 TSP 변형이다.
QUBO와 이징 머신: 많은 조합 문제를 $x^\top Q x$ 형태의 이진 이차 최적화로 바꿀 수 있고, 이를 스핀 변수로 옮기면 이징 모형의 바닥상태 찾기와 등가가 된다. 양자 어닐러·광학 이징 머신이 노리는 지점이 정확히 여기다. 다만 현재까지 범용적인 실용 우위가 확립된 것은 아니다.

9. 관련 문서[편집]

이 착각은 생각보다 끈질기다. “경우의 수가 유한하니 컴퓨터가 다 해보면 되죠”라는 말은 회의실에서 최소 분기당 한 번은 나온다. 그때 $29!/2$ 를 계산기에 찍어 보여주는 게 가장 빠른 설득이다. ↩
논문 제목이 대놓고 “A (slightly) improved approximation algorithm for metric TSP”다. 학계의 정직함이 빛나는 순간. 40년 묵은 상수를 $10^{-36}$ 만큼 깎은 것으로도 최고 수준의 성과로 인정받는다는 점에서, 이 상수가 얼마나 단단히 박혀 있었는지 알 수 있다. ↩
그래서 “우리 신형 메타휴리스틱이 벤치마크에서 이겼다”류의 주장은 항상 의심하고 볼 일이다. 튜닝 예산을 공평하게 줬는지, 비교 대상이 제대로 구현된 최신 기법인지, 인스턴스가 편향되지 않았는지를 보면 대부분의 우위가 증발한다. 새 동물 이름을 붙인 알고리즘이 매년 수십 개씩 나오는 것도 이 바닥의 웃픈 풍경. ↩