길리랩blog

MIP와 Branch-and-Bound로 정수 의사결정 최적화하기

Mixed-Integer Programming과 Branch-and-Bound의 탐색 구조, LP 이완, 절단면, 최적성 갭 및 실무 모델링 원칙을 정리한다.

2026-08-14 · 최초 발행 2024-04-29

정수 제약이 붙으면 탐색이 시작된다

Mixed-Integer Programming(MIP)은 선형 목적함수와 제약식에 정수 또는 이진 조건을 결합한 모델이다. 연속 자원 배분만으로는 표현하기 어려운 시설 개설, 선택, 배치, 순서 같은 이산 의사결정을 함께 다룰 수 있다.

일반적인 구조는 연속·정수 의사결정변수 x, 목적함수 c^T x, 제약 Ax ≤ b, 그리고 x ∈ Z^p × R^(n-p)로 표현한다. 선형계획법(LP)을 확장한 형태이지만, 정수성 조건 때문에 해법은 단순한 LP 풀이에서 끝나지 않는다.

Branch-and-Bound(B&B)는 MIP를 LP 이완으로 평가한 뒤 정수 조건을 만족하지 않는 변수를 기준으로 문제를 나누는 완전 탐색 가지치기 프레임이다. 분기(Branching), 경계(Bounding), 절단(Cutting), 현재까지 찾은 최선해(Incumbent), 프루닝이 함께 동작하며 전역 최적성을 보장한다.

LP 이완의 품질이 탐색량을 좌우한다

각 노드에서 푸는 LP 이완이 원래 정수 문제에 가까울수록 경계가 강해지고, 탐색해야 할 노드 수는 줄어든다. 흐름 보존이나 연속성 제약처럼 문제 구조를 드러내는 제약을 잘 설계하는 일이 중요한 이유다.

Big-M은 특히 신중하게 다뤄야 한다. M이 필요 이상으로 크면 수치적 불안정과 탐색 폭발을 유발할 수 있으므로 가능한 한 작은 값을 사용하고, 필요하면 유도 절단을 더한다.

노드의 LP를 푼 뒤 정수 조건을 어긴 해가 나오면 분기 변수를 골라 자식 노드를 만든다. 깊이우선, 최선경계(Best-bound), 하이브리드 전략을 상황에 따라 적용할 수 있다. 정수해를 찾으면 Incumbent를 갱신하고, 현재 경계와 비교해 더 나은 해를 만들 수 없는 노드는 제거한다. 트리가 소진되거나 시간 제한 또는 Gap 기준을 만족하면 탐색을 멈춘다.

절단과 전처리로 불필요한 가지를 걷어낸다

Gomory, MIR, Cover, Clique 절단면은 LP 이완을 강화하는 데 사용된다. 대칭을 깨거나 불일치를 더 강하게 제거하는 제약도 탐색 공간을 줄이는 역할을 한다.

Presolve는 본격적인 탐색 이전에 고정·제거 가능한 항목을 정리하고, 계수를 줄이며, 이득 없는 제약을 제거한다. 전처리만으로 노드 수가 1~2자릿수 배 축소된 사례도 빈번하다.

초기해를 빠르게 얻는 방법도 중요하다. RINS, Local Branching 같은 휴리스틱은 양질의 초기 해를 찾는 데 쓰이며, MIP Start가 있으면 초기 Gap을 줄일 수 있다. 변수 우선순위, Strong Branching, Pseudo-cost 역시 분기 품질을 높이는 수단이다.

Gap은 시간과 해 품질의 접점이다

상대 갭은 (UB−LB)/|UB| ≤ ε로 둘 수 있다. 서비스 운영에서는 0.1~3% 범위를 적용하는 경우가 많으며, 시간 예산이 고정된 환경에서는 Gap을 관찰하면서 해를 점진적으로 개선하는 방식이 유용하다.

⤢✕불능정수해분수해LB = UBLB < UB트리 소진 또는 Gap 만족시간 제한입력: MIP 모델변수·목적·제약Presolve/ScalingLP 이완 풀이노드 프루닝Incumbent 갱신경계 비교: LB vs UB분기 변수 선택(Strong/Pseudo-cost)가지 1: x_i <= ⌊v⌋가지 2: x_i = ⌈v⌉절단면 추가/LP 재풀이종료 조건최적/근최적 해 출력

계획·배치 문제에서의 모델링 방식

생산계획과 캡패시티 플래닝에서는 이진 가동 결정과 연속 자원 배분을 결합해 설정비용, 변화비용, 재고잔여를 최소화한다. 차량경로와 창고입지에서는 시설 개설 이진변수와 할당 연속변수를 연결하고, 수요 충족 및 거리·탄소비용을 함께 고려한다. 승무·교대 배정에는 연속 12시간 제한 같은 근무규칙과 커버 요구치를 반영해 공정성과 페널티를 다룰 수 있다.

금융에서는 최소·최대 비중, 카드inality, 추적오차 제약을 둔 포트폴리오 선택에 적용할 수 있다. 네트워크 설계는 링크 개통 여부와 흐름 변수를 결합해 신뢰성·지연 제약을 통합한다. VM 배치와 용량 계획에서는 라이선스 수 제한, 지역 가용성 제약을 반영하면서 비용 최소화와 SLO 충족을 함께 목표로 둔다.

상대 갭을 0.52%로 설정했을 때 계획비를 15% 절감할 가능성이 있으며, 이는 문제에 의존한다. Presolve·절단·워밍스타트를 함께 적용하면 노드 수가 10^1~10^3배 감소한 관측 사례도 다수다. 최적해의 근거와 이원변수(Shadow price)는 경영 의사결정의 설명가능성에도 활용된다.

접근법을 고를 때 보는 지표

접근법 성능(대규모) 확장성 일관성/최적성 보장 안정성(수치) 운영 편의
MIP + Branch-and-Bound 우수(강한 모델·컷 필요) 높음(병렬·노드 프루닝) 전역 최적/Gap 보장 높음(스케일링 전제) 높음(표준 툴체인)
CP-SAT/CP 하이브리드 매우 우수(이산 제약 강함) 높음 최적/Gap 보장(모델 의존) 높음 중간(튜닝 다양)
메타휴리스틱(탐욕/GA 등) 빠름(초기 해) 높음 비보장(경험적) 중간 높음(구현 용이)

CP-SAT는 SAT+CP+컷의 하이브리드 탐색으로 B&B와 유사한 경계 논리를 적용한다. 세부 동작은 최신 정보 확인이 필요하다.

운영 가능한 모델을 만드는 기준

강한 형식화가 출발점이다. Big-M을 최소화하고, 유도 불등식과 대칭깨기를 추가하며, 흐름·커버 불등식을 활용한다. 계수 스케일은 10^-3~10^3 범위를 권장하며 정규화를 적용한다. 긴 제약이나 대형 문제에서는 Benders, Column Generation, 라그랑주 이완을 검토할 수 있다.

솔버 설정에서는 Best-bound와 Depth-first의 하이브리드, Strong Branching의 활성화 여부, 글로벌·로컬 컷 제한, MIR·FlowCover 활성화 비율을 다룬다. 시간 제한, 상대·절대 Gap, 노드·컷 카운트 한도와 초기해(MIP Start)도 함께 정한다.

운영 단계에서는 난수 시드와 버전을 고정하고 로그·노드 통계를 보관한다. 불능 문제는 IIS 또는 충돌 집합 추출을 지원하는 솔버로 진단하고, 모델 검증 테스트 스위트를 둔다. 배포 시에는 컨테이너화, 병렬 스레드 제한, 리소스 격리와 라이선스·상용 솔버 정책 준수가 필요하다.

PuLP와 CBC로 시설 입지 모델 구성하기

전제조건은 다음과 같다.

  • Python 3.9+
  • pulp >= 2.7.0
  • CBC 설치 필요(예: conda install -c conda-forge coincbc 또는 OS 패키지 관리자). CBC 버전 차이로 옵션명 상이 가능, 최신 정보 확인 필요.

이 예제는 시설 f의 개설 여부를 이진 변수 y_f로 두고, 고객 c의 시설별 할당 비율을 연속 변수 x_{f,c}로 표현한다. 개설비와 운송비를 최소화하면서 수요 충족, 시설 용량, 할당-개설 연계 x_{f,c} ≤ y_f를 반영한다.

# pip install pulp
import pulp as pl

# 데이터
facilities = ["F1", "F2", "F3"]
customers = ["C1", "C2", "C3", "C4", "C5"]

open_cost = {"F1": 800, "F2": 700, "F3": 500}
capacity = {"F1": 4, "F2": 5, "F3": 3}
demand = {"C1": 1, "C2": 1, "C3": 1, "C4": 2, "C5": 1}
# 단위 운송비(시설-고객)
ship_cost = {
    ("F1", "C1"): 3, ("F1", "C2"): 5, ("F1", "C3"): 2, ("F1", "C4"): 6, ("F1", "C5"): 4,
    ("F2", "C1"): 4, ("F2", "C2"): 3, ("F2", "C3"): 5, ("F2", "C4"): 2, ("F2", "C5"): 3,
    ("F3", "C1"): 6, ("F3", "C2"): 4, ("F3", "C3"): 3, ("F3", "C4"): 4, ("F3", "C5"): 2,
}

# 모델
m = pl.LpProblem("FacilityLocation", pl.LpMinimize)

# 변수
y = pl.LpVariable.dicts("open", facilities, lowBound=0, upBound=1, cat="Binary")
x = pl.LpVariable.dicts("assign", [(f, c) for f in facilities for c in customers],
                        lowBound=0, cat="Continuous")

# 목적함수
m += pl.lpSum(open_cost[f] * y[f] for f in facilities) + \
     pl.lpSum(ship_cost[(f, c)] * x[(f, c)] for f in facilities for c in customers)

# 수요 충족: 각 고객은 정확히 1 단위 충족
for c in customers:
    m += pl.lpSum(x[(f, c)] for f in facilities) == demand[c]

# 용량 제약
for f in facilities:
    m += pl.lpSum(x[(f, c)] for c in customers) <= capacity[f]

# 할당-개설 연계: x_{f,c} ≤ demand[c] * y_f (Big-M 최소화: 고객별 수요 사용)
for f in facilities:
    for c in customers:
        m += x[(f, c)] <= demand[c] * y[f]

# 솔버 옵션: 시간 제한 10초, 상대 Gap 1%, 로그 출력
solver = pl.PULP_CBC_CMD(msg=True, timeLimit=10, options=["ratio", "0.01"])
m.solve(solver)

print("Status:", pl.LpStatus[m.status])
print("Objective:", pl.value(m.objective))
print("Opened facilities:", [f for f in facilities if pl.value(y[f]) > 0.5])

assign_plan = {(f, c): pl.value(x[(f, c)]) for f in facilities for c in customers if pl.value(x[(f, c)]) > 1e-6}
print("Assignments:", assign_plan)

# CBC 로그로 Gap/노드 정보를 확인 가능. 상용 솔버 사용 시 MIPStart/우선순위/컷 수준 상세 설정 가능.

초기해는 일부 y_f를 1로 고정한 뒤 풀고 해제하는 방식으로 힌트를 제공할 수 있다. 분기 우선순위는 상용 솔버(Gurobi/CPLEX) 또는 SCIP에서 var priority로 설정한다. MIR·FlowCover 컷의 활성화와 강도를 조정해 LP 이완을 강화할 수도 있다.

모델 품질과 탐색 정책을 함께 관리한다

MIP와 Branch-and-Bound의 성능은 솔버만으로 결정되지 않는다. LP 이완을 강하게 만드는 모델링, 분기·절단·휴리스틱의 조합, Gap 기반의 시간-품질 관리가 한 흐름으로 이어진다.

문제가 커질수록 분해·하이브리드 접근과 병렬 탐색을 검토할 수 있다. 데이터 스케일링과 Big-M 최소화는 수치 안정성을 지키는 기본 조건이다.

정수계획제약 최적화Branch-and-BoundLP 이완운영 최적화