제약 최적화에서 LP·MIP·라그랑주 승수법을 고르는 기준

제약을 식으로 옮긴 뒤에야 선택할 수 있는 것들

제약 최적화는 의사결정변수와 목적함수, 제약식으로 표현한 수리 모델에서 최적값을 찾는 방식이다. 비용을 낮추거나 서비스 수준을 맞추고, 한정된 자원을 더 많이 활용해야 하는 상황에서 쓰인다.

선형계획(Linear Programming, LP)은 목적함수와 제약식이 모두 선형이고 변수가 연속값인 문제를 다룬다. 혼합정수계획(Mixed-Integer Programming, MIP)은 일부 또는 전체 변수가 정수 혹은 이진값인 선형 최적화다. 라그랑주 승수법(Lagrange Multipliers)은 등호 제약이 있는 연속 변수 비선형 최적화에서 정류점을 찾으며, KKT 조건의 특수 형태에 해당한다.

모델을 만들 때는 변수·목적·제약의 의미를 분명히 하고 단위와 스케일을 정리해야 한다. 데이터와 모델을 연결하는 기준도 필요하다. 누락값과 이상치를 어떻게 처리할지, 사업 규칙 가운데 어떤 것은 반드시 지켜야 하는 hard constraint이고 어떤 것은 패널티로 다룰 soft constraint인지 구분한다.

문제의 구조가 해법을 정한다

LP는 심플렉스와 내부점법을 중심으로 풀며, 대규모 연속 문제에 적합하다. 정수성이 필요하지 않다면 LP로 단순화하는 편이 규모와 속도 측면에서 유리하다.

MIP는 분기한계, 분기절단, 휴리스틱을 함께 사용한다. 개설·선택·순서처럼 불연속적인 의사결정이 본질일 때 표현력이 높지만, 계산량과 튜닝 난이도도 커진다.

라그랑주 승수법은 미분 가능성과 정칙성을 전제로 한다. 연속적이고 미분 가능한 제약을 이론적으로 분석하거나 근사해를 도출할 때 적합하며, KKT 조건으로 해를 확인한다.

관점	LP	MIP	Lagrange Multipliers
성능	대규모 선형 연속 문제에서 매우 빠른 수렴	정수성으로 NP-hard, 케이스에 따라 느림	비선형 구조에 따라 빠르거나 불안정
확장성	수백만 변수까지 가능	모델 구조·컷 설계에 좌우	변수 수 증가 시 해석 복잡
전역최적	볼록성 하 전역최적 보장	전역최적 보장, 해 찾기 어려울 수 있음	일반 비선형은 지역해 가능, KKT 필요충분 아님
민감도	듀얼·감도분석 풍부	갭·바운드로 진단, 민감도 해석 제한	정칙성·라그랑주안정성 조건 의존
운영 편의	모델링·튜닝 용이	현업 제약 표현력 우수, 튜닝 난이도 높음	분석가 숙련도 필요, 자동화 난이도 상

입력부터 배포까지 이어지는 최적화 운영 흐름

⤢✕

운영 절차는 시나리오 입력, 모델 생성, 전처리와 사전단순화, 해 탐색, 해 검증, 배포로 이어진다. Warm start, 프리솔브, 파라미터 튜닝을 자동화하고, 실패했을 때의 경로와 대체 전략도 함께 정해 둔다.

검증에서는 실현가능성과 최적성 갭을 확인하고, 민감도와 가격(Shadow price)을 분석한다. 이중문제 해석, 바운드와 슬랙 진단은 해가 현업 규칙에 맞는지 설명하는 데도 쓰인다. 규모가 커지면 Benders와 Dantzig-Wolfe 분해, 시나리오 병렬화, 컬럼 생성을 적용할 수 있다. 변수와 제약을 줄이고 대칭성을 제거하며 커팅플레인을 설계하는 작업도 수렴을 앞당긴다.

공급망부터 포트폴리오까지의 모델링 차이

공급망과 생산 계획에서는 운송·재고·생산을 포함한 총비용 최소화와 서비스 레벨 제약 충족이 목적이 된다. 생산량은 LP의 연속 변수로, 공장 개설과 차량 배차는 MIP의 이진 변수로 표현할 수 있다. 안전재고와 리드타임은 soft constraint로 패널티화하고, 불확실성은 시나리오 또는 로버스트 제약으로 흡수한다.

인력 배치와 스케줄링에서는 인건비 최소화 또는 커버리지 최대화를 목표로 둔다. 시프트 근무 여부, 근로기준법, 연속 휴식시간 제약은 MIP 모델링 대상이다. 컬럼 생성 기반 셋커버링과 warm start는 재스케줄링을 가속하는 데 활용한다.

포트폴리오와 리스크 관리에서는 기대수익을 높이면서 분산이나 VAR 제약을 맞춘다. 투자비중은 LP 또는 이차계획(QP)으로 다루고, 종목 수 제한과 라운드 lot은 MIP의 이진 변수로 처리한다. 트랜잭션 비용과 슬리피지를 패널티로 넣고, 민감도를 바탕으로 리밸런싱 룰을 구성한다.

간단한 모델을 코드로 확인하기

전제조건은 Python 3.10+, pulp 2.7+, sympy 1.12이며, 외부 데이터 없이 단일 파일로 실행한다.

생산계획의 LP 모델

# pip install pulp
from pulp import LpProblem, LpVariable, LpMaximize, lpSum, value

prob = LpProblem("ProductionPlan", LpMaximize)
x = LpVariable("Prod_A", lowBound=0)
y = LpVariable("Prod_B", lowBound=0)

# 최대 이익: 3x + 2y
prob += 3*x + 2*y
# 기계시간: 2x + y <= 100
prob += 2*x + y <= 100
# 원자재: x + y <= 80
prob += x + y <= 80

prob.solve()
print("Status:", prob.status, "Profit:", value(prob.objective))
print("x:", value(x), "y:", value(y))

이진 선택이 필요한 MIP 모델

# pip install pulp
from pulp import LpProblem, LpVariable, LpMaximize, lpSum, LpBinary, value

items = ["i1","i2","i3","i4"]
values = {"i1":10,"i2":8,"i3":7,"i4":6}
weights = {"i1":5,"i2":4,"i3":3,"i4":2}
capacity = 9

prob = LpProblem("Knapsack", LpMaximize)
x = {i: LpVariable(f"x_{i}", cat=LpBinary) for i in items}
prob += lpSum(values[i]*x[i] for i in items)
prob += lpSum(weights[i]*x[i] for i in items) <= capacity

prob.solve()
print("Objective:", value(prob.objective))
print({i:int(x[i].value()) for i in items})

등호 제약을 둔 라그랑주 승수법

# pip install sympy
import sympy as sp
x, y, lam = sp.symbols('x y lam', real=True)
f = x*y
g = x + y - 10
L = f + lam*(10 - x - y)
sol = sp.solve([sp.diff(L, v) for v in (x, y, lam)], (x, y, lam), dict=True)
print(sol)  # [{x: 5, y: 5, lam: 0}]

LP와 MIP에서는 제약 슬랙, 변수 바운드, 상용 솔버 사용 시 최적성 갭을 확인한다. 라그랑주 승수법에서는 KKT 조건 만족 여부와 Hessian 부호를 통해 볼록·오목 및 극값의 성격을 판정한다.

비용·서비스 수준·의사결정 속도에 미치는 영향

운송·재고·인력 비용은 베이스라인 대비 520% 절감 가능하며, 도메인에 의존한다. SLA 위반율은 1030% 감소하고 충족률은 2~8%p 개선될 수 있다. 자동화 파이프라인을 구축하면 일 단위 배치 의사결정을 분·초 단위 실시간 의사결정으로 전환할 수 있다.

실무에서는 강한 바운드 설정, 스케일링, 중복 또는 지배 제약 제거부터 시작한다. 이후 컷 관리, 브랜칭 우선순위, 대칭성 제거, warm start를 조합해 성능을 조정한다. 불능과 무계획을 진단하는 루틴, soft constraint 패널티 캘리브레이션, 시나리오 회귀 테스트를 운영에 포함하면 모델의 신뢰성을 유지하는 데 도움이 된다.