정수계획법

1. 개요[편집]

정수계획법(Integer Programming, IP)은 결정변수의 전부 또는 일부가 정수값만 가질 수 있다는 제약이 붙은 수학적 최적화 문제, 그리고 그것을 푸는 방법론이다. 목적함수와 제약이 전부 일차식이면 정수선형계획(ILP), 여기에 연속변수가 섞이면 혼합정수선형계획(MILP), 변수가 0/1만 가지면 이진계획(BIP)이라 부른다. 실무에서 그냥 “MIP”라고 하면 보통 MILP를 가리킨다.

$$\min_{x} \; c^{\top} x \quad \text{s.t.} \quad Ax \le b, \; x \ge 0, \; x_j \in \mathbb{Z} \; (j \in I)$$

마지막 조건 하나 붙였을 뿐인데 선형계획법의 아름다운 다항시간 세계는 그대로 증발하고 NP-난해의 세계가 열린다.¹ 대신 “짓는다/안 짓는다”, “이 라인에 배정한다/안 한다”, “이 부재를 남긴다/제거한다” 같은 이산 의사결정을 그대로 모델에 넣을 수 있게 되어, 표현력은 비교가 안 되게 넓어진다. 공장 배치, 승무원 스케줄링, 배송 경로, 발전기 기동정지(unit commitment), 이산 단면 치수를 갖는 형상 최적화가 전부 여기로 들어온다.

2. LP 완화와 완화 간극[편집]

정수 제약 $x_j \in \mathbb{Z}$를 그냥 지워버린 문제를 LP 완화(linear programming relaxation)라 한다. 완화 문제는 원문제보다 실행가능 영역이 넓으므로, 최소화 문제 기준으로 그 최적값은 항상 원문제 최적값의 하계가 된다. 이 한 줄이 정수계획 알고리즘 전체를 지탱하는 기둥이다.

• LP 완화 해가 우연히 전부 정수면 → 그게 곧 원문제 최적해다. 끝.
• 아니면 → 그 값은 “아무리 잘해봐야 이보다 좋을 수 없다”는 증명서 역할을 한다.

원문제 최적값과 완화 최적값의 차이를 완화 간극(integrality gap)이라 하고, 이 간극이 작을수록 탐색이 빨리 끝난다. 그래서 MIP 모델링의 8할은 “같은 정수해 집합을 표현하되 완화가 더 타이트한” 정식화를 찾는 싸움이다. 같은 문제라도 정식화를 바꾸면 풀이 시간이 수천 배 차이 난다는 게 이 바닥의 상식.

주의할 오해 하나. LP 완화 해를 반올림하면 되지 않느냐는 발상은 거의 항상 틀린다. 반올림한 점은 실행가능하지 않을 수 있고, 실행가능하더라도 최적과는 한참 멀 수 있으며, 어떤 문제에서는 실행가능해를 찾는 것 자체가 이미 NP-난해다.

3. 분지한정법[편집]

정수계획의 표준 해법은 1960년 랜드-도이그(Land-Doig)가 제시한 분지한정법(branch and bound)이다. 골자는 “전체 탐색 트리를 만들되, 가망 없는 가지는 열어보지도 않고 잘라낸다”이다.

1. 완화 풀기. 현재 노드에서 LP 완화를 푼다. 실행불가능하면 그 가지는 즉시 사망.
2. 분지(branching). 완화 해에서 정수여야 할 변수 $x_j$가 분수값 $\bar{x}_j$를 가지면, 두 자식 노드를 만든다: $x_j \le \lfloor \bar{x}_j \rfloor$ 인 쪽과 $x_j \ge \lceil \bar{x}_j \rceil$ 인 쪽. 두 영역의 합집합은 원래의 정수해를 하나도 잃지 않으면서 분수해 $\bar{x}$만 쏙 배제한다.
3. 한정(bounding). 자식의 LP 값이 현재까지 찾은 최선의 정수해, 즉 incumbent의 값보다 나쁘면 그 아래에는 더 좋은 해가 있을 수 없다. 가지치기(pruning) 대상.
4. 열린 노드가 없어지면 incumbent가 전역 최적해다.

실전 성능은 세부 규칙이 좌우한다. 분지할 변수를 고르는 규칙은 강분지(strong branching, 후보마다 시험 LP를 풀어보고 고름 — 정확하지만 비쌈)와 의사비용(pseudocost, 과거 분지에서의 목적값 상승 이력을 평균 내 예측) 혼합이 국룰이고, 노드 선택은 하계를 빨리 조이는 최량우선(best-first)과 incumbent를 빨리 얻는 깊이우선(depth-first)을 섞어 쓴다. 좋은 incumbent를 일찍 확보할수록 가지치기가 강해지므로, 솔버는 실행가능해 발견용 휴리스틱(feasibility pump, RINS, local branching)을 트리 안에서 계속 돌린다.

솔버가 출력하는 MIP gap은 (incumbent 값 − 최량 하계) / incumbent 값이다. 이게 0이 될 때까지 기다리는 게 원칙이지만, 현생이 바쁜 현업에서는 보통 0.1~1%에서 끊는다. 그 순간에도 “최적에서 최대 x% 이내”라는 보증서는 손에 남는다는 점이 메타휴리스틱과 결정적으로 다른 부분.²

4. 절단평면법과 분지절단[편집]

또 다른 축은 절단평면법(cutting plane method)이다. 1958년 고모리(Ralph Gomory)가 제안한 아이디어는 이렇다. LP 완화 해가 분수라면, 모든 정수해는 만족하지만 지금의 분수해는 위반하는 부등식을 하나 찾아 제약으로 추가한다. 실행가능 영역이 정수 껍질(integer hull) 쪽으로 한 겹 깎이고, 다시 LP를 푼다.

고전적인 고모리 분수 절단은 심플렉스 최종 태블로의 한 행

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

에서 $\bar{b}_i$가 분수일 때, 소수부만 남긴

$$\sum_{j \in N} \left( \bar{a}_{ij} - \lfloor \bar{a}_{ij} \rfloor \right) x_j \;\ge\; \bar{b}_i - \lfloor \bar{b}_i \rfloor$$

를 추가한다. 정수해라면 좌변은 반드시 우변 이상인데, 현재 분수해는 $x_N = 0$이라 좌변이 0이므로 잘려 나간다. 이론적으로는 유한 번에 수렴하지만, 순수 고모리 절단만 반복하면 수치적으로 뭉개지고 절단이 점점 무뎌져 실전에서는 오래도록 찬밥이었다.

부활은 분지절단(branch-and-cut)이라는 결합형에서 일어났다. 분지한정 트리의 각 노드에서 절단을 몇 겹 추가해 하계를 조인 다음 분지하는 방식으로, 파드베르그-리날디가 대규모 외판원 문제에 적용해 위력을 입증한 뒤 표준이 됐다. 현대 솔버는 고모리 혼합정수 절단, 배낭 커버 절단, 흐름 커버, MIR(mixed integer rounding), 클리크 절단 등을 한꺼번에 생성하고 효과 없는 절단은 다시 버린다. 절단을 붙일 때마다 재최적화가 필요한데, 이때는 웜스타트가 잘 먹히는 쌍대 심플렉스법이 주력이다.

5. 언제 정수 제약이 공짜가 되는가[편집]

모든 정수계획이 어려운 건 아니다. 계수행렬 $A$가 전체 단모듈(totally unimodular, TU)이면 — 즉 모든 정사각 부분행렬의 행렬식이 0, +1, −1 중 하나이면 — $b$가 정수 벡터일 때 다면체 $\{x : Ax \le b,\, x \ge 0\}$의 모든 꼭짓점이 정수점이 된다. 심플렉스법이 뱉는 LP 해가 저절로 정수라는 뜻이고, 정수 제약을 붙이든 말든 같은 답이 나온다.

대표적인 TU 행렬이 네트워크 흐름 문제의 노드-아크 접속행렬과 이분그래프의 접속행렬이다. 최대유량, 최소비용흐름, 수송문제, 이분 매칭이 전부 다항시간에 정수해로 풀리는 이유가 바로 이것이다. 반대로 말하면, 여러분의 모델이 도저히 안 풀린다면 “네트워크 구조로 다시 쓸 수 있나”를 먼저 의심해볼 가치가 있다. 관련 심화 개념으로 전체 단모듈성과 완전정수 다면체 이론이 있다.

6. 모델링 기법[편집]

정수계획은 알고리즘보다 모델링이 실력인 분야다. 자주 쓰는 관용구 몇 가지.

• 이진 지시변수. $y \in \{0,1\}$로 “설비 건설 여부”, “경로 사용 여부”를 표현하고, 고정비 $f y$를 목적함수에 얹는다.
• 빅-M 연결. “설비를 짓지 않으면 생산량 0”은 $x \le M y$로 쓴다. 여기서 $M$은 $x$의 유효 상한이어야 하는데, 필요 이상으로 크게 잡으면 LP 완화가 흐물흐물해져 하계가 무의미해지고 부동소수점 오차까지 커진다. $M$은 항상 물리적으로 정당한 최소값으로 잡는 게 원칙이며, 가능하면 솔버의 지시 제약(indicator constraint) 기능으로 $M$ 없이 표현하는 편이 낫다.
• 논리 제약의 선형화. 배타적 선택은 $\sum y_i = 1$, 함의 $y_1 \Rightarrow y_2$는 $y_1 \le y_2$, “둘 중 하나만 활성”은 SOS1 집합으로 선언한다.
• 구간 선형 근사. 비선형 비용곡선을 조각선형으로 쪼개고 인접한 두 조각만 켜지도록 SOS2 제약을 건다. 비선형 문제를 MILP로 끌어오는 흔한 수법.
• 대칭 파괴. 동일한 기계·동일한 시간슬롯처럼 서로 바꿔도 같은 해가 되는 대칭이 있으면 탐색 트리가 같은 해를 수없이 재방문한다. 사전식 순서 제약을 걸어 대칭을 깨면 극적으로 빨라진다.

7. 솔버와 실무[편집]

상용 진영은 Gurobi와 IBM CPLEX가 양대 산맥이고, FICO Xpress가 뒤를 잇는다. 학술·오픈소스 쪽은 SCIP(제약계획과 결합, 비선형 MINLP까지), HiGHS, CBC가 대표적이다. 모델링은 AMPL·GAMS 같은 전용 언어나 Pyomo·JuMP·PuLP 같은 라이브러리로 하고 솔버는 갈아끼우는 구조가 일반적이다.

이들 솔버에서 가장 과소평가되는 부품이 전처리(presolve) 다. 중복 제약 제거, 변수 고정, 계수 강화, 경계 전파만으로 문제 크기가 절반 이하로 줄어드는 일이 흔하다. 지난 30여 년간 MILP 실측 속도 향상은 하드웨어보다 알고리즘(전처리·절단·휴리스틱·분지 규칙) 쪽 기여가 훨씬 컸다는 게 정설이다.³

비선형 목적·제약에 정수변수가 섞인 MINLP는 한 단계 더 난이도가 올라간다. 볼록 MINLP는 외부근사(outer approximation)나 분지한정+NLP 조합으로 접근하고, 각 노드의 연속 부분문제는 순차 이차계획법이나 내점법으로 푼다. 비볼록 MINLP는 공간 분지한정(spatial branch-and-bound)으로 전역 최적을 노리지만, 규모가 커지면 결국 담금질 모사나 유전 알고리즘 같은 메타휴리스틱과 타협하게 된다.⁴

8. 관련 문서[편집]

• 선형계획법 · 이차계획법
• 조합 최적화 · 네트워크 흐름
• 분지한정법 · 절단평면법
• 볼록 최적화 · 내점법 · 활성집합법
• 동적 계획법 · 담금질 모사 · 유전 알고리즘
• 최적설계 · 위상 최적화 · 형상 최적화
• 희소행렬 · 조건수

9. Footnotes[편집]

1. 0-1 정수계획은 1972년 카프(Richard Karp)가 NP-완전임을 보인 21개 문제 목록의 첫머리에 올라 있다. 즉 “정수 제약 하나 추가”의 대가는 이론적으로 확정된 셈이다. 그래도 매일 수십만 변수짜리 MILP가 현업에서 풀린다 — 최악의 경우가 지수적이라는 것과 내 문제가 지수적이라는 것은 다른 얘기다. ↩

2. MIP gap 0.5%로 끊은 결과를 보고할 때 “최적입니다”라고 하면 안 되고 “최적 대비 0.5% 이내 보증”이라고 해야 한다. 이 구분을 지키는 것만으로도 회의실에서 신뢰도가 올라간다. 반대로 gap을 안 보고 시간 제한으로 끊은 뒤 최적이라고 우기는 순간, 그건 그냥 휴리스틱이다. ↩

3. 벤치마크 관행상 “기계 성능 고정 시 알고리즘 개선분”과 “하드웨어 개선분”을 분리해 측정하는데, 상용 솔버 개발사들이 공개한 장기 추적에서 알고리즘 쪽 배수가 훨씬 컸다. 코드를 갈아 넣는 게 실리콘을 갈아 넣는 것보다 남는 장사였다는 뜻. ↩

4. 여기서 유혹이 온다. “그냥 유전 알고리즘 돌리면 되지 않나?” 돌아는 간다. 다만 그 순간 하계가 사라지므로, 나온 해가 최적에서 3% 떨어졌는지 300% 떨어졌는지 영원히 알 수 없게 된다. 수렴은 신에게 맡긴다는 자세가 필요하다면 그때 쓰자. ↩