9. 정수 프로그래밍 (IP, Integer Programming) — 분기 한정, MILP

핵심 인사이트 (3줄 요약)

본질: IP (Integer Programming, 정수 계획법) 는 결정 변수가 정수여야 하는 최적화 — LP보다 훨씬 어렵고 (NP-hard in general) 실세계의 이진(0/1) 결정 문제를 직접 모델링한다.

가치: 분기 한정법 (Branch and Bound) 이 LP 완화와 결합해 최적 정수해를 체계적으로 탐색하며, CPLEX·Gurobi 같은 현대 솔버가 수백만 변수 문제를 다항식 평균 시간에 풀어낸다.

판단 포인트: MILP (Mixed Integer Linear Programming, 혼합 정수 선형 계획법) — 일부 변수가 정수, 일부는 연속 — 가 스케줄링, 네트워크 설계, 포트폴리오 등 실무 문제의 가장 일반적인 형태다.

Ⅰ. 개요 및 필요성

정수 계획법 (Integer Programming, IP) 표준형:

minimize   cᵀx
subject to Ax ≤ b
           x ∈ ℤⁿ    (정수 제약)

특히 이진 정수 계획법 (Binary IP, 0-1 IP):

x ∈ {0, 1}ⁿ    (예/아니오 결정)

LP보다 어려운 이유: 가능 영역이 연속이 아닌 이산 점집합 → 볼록 완화와 실제 최적해의 격차 (Integrality Gap) 존재.

IP 활용 분야

분야	IP 모델	예시
스케줄링	xᵢⱼ ∈ {0,1}: i번 작업을 j시간대 배정	항공 승무원 스케줄
네트워크 설계	yᵢⱼ ∈ {0,1}: 링크 설치 여부	광섬유 네트워크
포트폴리오	자산 선택 0/1	인덱스 추적
배낭 문제 (Knapsack)	물건 선택 0/1	화물 적재
순회 판매원 (TSP)	경로 선택 0/1	물류 경로

📢 섹션 요약 비유: IP는 "분수로 살 수 없는 쇼핑"이다 — 냉장고를 0.7개 살 수 없듯, 정수 단위로만 결정해야 하는 현실 문제를 다룬다.

Ⅱ. 아키텍처 및 핵심 원리

분기 한정법 (Branch and Bound) 트리

IP 문제: min cᵀx, x ∈ ℤⁿ

        [LP 완화]  UB=∞
        해: x₁*=2.5
           ↙           ↘
    [x₁ ≤ 2]         [x₁ ≥ 3]
    LP 해: 2.7         LP 해: 3.2
    LB=2.7             LB=3.2
       ↙   ↘
[x₂≤2] [x₂≥3]
정수해!  비가능
 LB=3.1  Prune
 UB=3.1 ← 갱신

최종: x₁=2, x₂=2, 목적값=3.1

LP 완화 (Relaxation): 정수 제약 해제 → 현재 노드의 하한 (Lower Bound) 계산
분기 (Branch): 비정수 변수 선택 → 두 자식 노드 (xᵢ ≤ ⌊xᵢ*⌋, xᵢ ≥ ⌈xᵢ*⌉)
한정 (Bound): 노드 하한 ≥ 현재 상한 (Upper Bound) → 가지치기 (Prune)
갱신: 정수해 발견 시 UB 갱신

분기 한정 연산	설명
LP 완화	현재 노드 하한 계산 (LP 풀이)
분기 변수 선택	최대 분수 규칙, 강한 분기 등
한정 (가지치기)	LB ≥ UB 또는 비가능 시 제거
상한 갱신	정수해 발견 시 UB 업데이트

절삭면 (Cutting Planes)

고모리 절삭 (Gomory Cuts): LP 완화 해에서 정수해만 남기는 추가 제약 생성

LP 완화 가능 영역     절삭면 추가 후
   ────────────────   ────────────────
  /                \ /  (잘린 모서리)  \
 /    LP 최적●      |    LP 최적●      |
|     (비정수)      |    (정수에 근접)  |
 \                 / \                /
  \               /   \             /

절삭면 = 정수 가능 영역만 남기는 선형 부등식

현대 솔버: Branch and Cut = 분기 한정 + 절삭면 결합.

📢 섹션 요약 비유: 분기 한정법은 "체계적 가능성 탐색 + 조기 포기"다 — 모든 경우를 다 확인하지 않고, 더 좋은 답이 나올 수 없는 가지를 미리 잘라낸다.

Ⅲ. 비교 및 연결

MILP 모델링 예시 — 시설 입지 결정

yⱼ ∈ {0,1}: j번 시설 설치 여부 (정수)
xᵢⱼ ≥ 0:   수요지 i에 대한 j 시설의 공급 비율 (연속)

min Σⱼ fⱼ·yⱼ + ΣᵢΣⱼ cᵢⱼ·xᵢⱼ
s.t. Σⱼ xᵢⱼ = 1  ∀i       (수요 충족)
     xᵢⱼ ≤ yⱼ    ∀i,j     (개설 시설만 사용)
     yⱼ ∈ {0,1}, xᵢⱼ ≥ 0

이것이 MILP: yⱼ(정수) + xᵢⱼ(연속) 혼재.

IP 복잡도와 특수 구조

문제	복잡도	비고
일반 0-1 IP	NP-hard
배낭 문제	NP-hard (위약: O(nW) DP)	의사 다항식
순회 판매원 (TSP)	NP-hard
최소 스패닝 트리	P	LP 완화가 정수 → 프리마/크루스칼
최단 경로	P	다익스트라
최대 매칭 (이분)	P	헝가리안 알고리즘
네트워크 플로우	P	LP 행렬이 완전 단모듈

현대 MIP 솔버의 강점

Gurobi 예시 (2023):

1,000만 변수, 200만 제약 MILP 풀기 가능
이진 IP 내부 휴리스틱: 초기 정수해 빠르게 찾기
병렬 분기 한정: 수십 코어 활용

📢 섹션 요약 비유: 절삭면은 "정수만 남기는 필터"다 — LP의 넓은 가능 영역을 잘라내어 정수해를 담은 더 작은 다면체로 만드는 수학적 가위질.

Ⅳ. 실무 적용 및 기술사 판단

항공사 승무원 스케줄링

xᵢⱼ ∈ {0,1}: 승무원 i를 비행 편 j에 배정 여부

min Σᵢ 비용ᵢ · (배정된 비행 편 수)
s.t. Σᵢ xᵢⱼ ≥ 1    ∀j  (각 편 최소 1명 승무원)
     xᵢⱼ ≤ 적합도ᵢⱼ  ∀i,j  (자격 요건)
     연속 비행 편 간 시간 제약 (휴식)
     법적 근무 시간 제약

수천 명 승무원, 수만 편 → MILP로 수십억 원 절약 (American Airlines 등 실 적용).

배낭 문제 (0-1 Knapsack) — 동적 계획 vs IP

n = 5, W = 10:
물건: (가치 6, 무게 4), (가치 3, 무게 2), (가치 5, 무게 5),
     (가치 4, 무게 3), (가치 2, 무게 1)

DP 방법: O(nW) = O(50) 시간
IP 방법: 분기 한정, 절삭면
→ 작은 문제는 DP, 큰 구조화 문제는 IP 솔버

기술사 판단 포인트

"LP와 IP 복잡도 차이는?" → LP: 다항식 (내점법), IP: 일반 NP-hard
"분기 한정법의 핵심 두 가지는?" → LP 완화 (하한) + 가지치기 (상한 초과 시 제거)
"TSP가 IP로 표현 가능한가?" → ✅ 가능, Miller-Tucker-Zemlin 제약으로 부분 순환 제거

📢 섹션 요약 비유: 배낭 문제의 LP 완화는 "물건을 잘게 자를 수 있다"고 가정하는 것이다 — 잘라도 된다면 쉽지만, 0 또는 1만 허용되면(정수 제약) 훨씬 어려워진다.

Ⅴ. 기대효과 및 결론

IP/MILP는 현실 세계 이산 결정 문제의 수학적 언어다. 아무리 복잡한 스케줄링, 네트워크 설계, 물류 경로도 IP 모델로 표현하면 전역 최적을 추구할 수 있다.

현대 MIP 솔버의 발전:

1990년대 대비 솔버 성능 10억배 이상 향상
이 중 알고리즘 개선이 수천배, 하드웨어 개선이 수십만배
LP 완화 + 절삭면 + 분기 한정 + 병렬화의 결합이 핵심

📢 섹션 요약 비유: IP 솔버의 발전은 "체계적인 보물 지도"가 된 것이다 — 이전엔 모든 경우를 일일이 확인해야 했지만, 이제는 지도(LP 완화 하한)와 가위(가지치기)로 최적 보물을 효율적으로 찾는다.

📌 관련 개념 맵

개념	핵심	연결
IP	x ∈ ℤⁿ, NP-hard	스케줄링, TSP
MILP	정수+연속 혼합	시설 입지, 포트폴리오
LP 완화	정수 제약 해제	분기 한정 하한
분기 한정	LP완화+분기+가지치기	MIP 표준 알고리즘
절삭면	Gomory cuts	정수 가능 영역 축소

📈 관련 키워드 및 발전 흐름도

[선형 계획법(LP)]
    │
    ▼
[정수 계획법(IP) 문제 정의]
    │
    ▼
[분기 한정법(Branch & Bound)]
    │
    ▼
[절단 평면법(Cutting Plane)]
    │
    ▼
[산업 최적화 응용]

정수 계획법은 선형 계획법을 정수 제약으로 확장하고 Branch & Bound와 Cutting Plane으로 푼다.

👶 어린이를 위한 3줄 비유 설명

IP는 "반만 살 수 없는 쇼핑": 물건은 1개씩만 살 수 있고, 0.5개나 1.7개는 불가능하다.
분기 한정은 "나무 가지치기 게임": 모든 경우를 탐색하되, 이미 더 좋은 답이 있으면 그 가지는 더 볼 필요 없이 잘라버린다.
LP 완화는 "일단 분수 허용": 어려운 정수 문제를 쉬운 연속 문제로 먼저 풀어 "이 이하는 불가능"한 기준점을 얻는다.