제약 최적화로 LP·MILP·라그랑주 이완 선택하기

제약은 목적함수보다 먼저 모델링된다

제약 최적화는 제한된 자원과 비즈니스 규칙 아래에서 목적함수의 최적값을 찾는 문제다. 비용을 줄이거나 이익과 서비스 수준을 높이는 목표만으로는 충분하지 않다. 수요, 용량, 정책, 논리 조건을 수리모형에 함께 반영해야 실제 운영에 쓸 수 있는 해가 나온다.

연속적인 의사결정에는 Linear Programming(LP)을, 정수나 이진 선택이 필요한 경우에는 Integer Programming(IP, MILP)을 적용한다. 결합 제약 때문에 정수문제가 지나치게 커질 때는 Lagrangian Relaxation/Dual로 제약 일부를 벌점 형태로 목적함수에 이관해 하한을 계산하고 문제를 분해할 수 있다.

LP는 목적함수와 제약식이 모두 선형식인 연속 최적화 문제다. Simplex 또는 Interior-Point로 다항 규모 실무 문제에 안정적으로 적용할 수 있다. IP와 MILP는 일부 또는 모든 의사결정변수에 정수 또는 이진 제약을 둔다. NP-hard 특성 때문에 Branch-and-Bound/Cut과 Heuristic을 함께 사용한다.

모형의 크기와 해법은 변수 유형에서 갈린다

목적함수에는 비용 최소화, 이익 또는 서비스 수준 최대화 같은 목표를 선형식으로 둔다. 다목적 문제는 가중합이나 계층화로 하나의 기준으로 바꿔 다룬다. 제약식에는 수요, 용량, 정책, 논리 조건을 선형화해 넣으며, 불능(Infeasibility)을 피하기 위한 슬랙 변수와 벌점 설계도 필요하다.

변수는 연속형이면 LP, 이진형 또는 일반정수형이면 IP의 대상이 된다. 변수의 유형과 수는 모델 크기, 해공간의 복잡도, 그리고 적합한 해법을 함께 결정한다.

Simplex는 꼭짓점을 옮기며 해를 반복 개선하고, 듀얼성 및 기저 갱신 절차로 수렴한다. 퇴화나 사이클링을 막기 위해 Bland 규칙 등을 적용할 수 있다. MILP에서는 LP 릴랙세이션의 하한을 바탕으로 Branch-and-Bound 탐색을 수행하고, 컷(분리평면)으로 폴리토프를 강화한다. best-bound와 depth-first 같은 탐색전략을 고르고 프리솔브와 대칭성 제거로 탐색공간을 줄인다.

라그랑주 접근은 결합 제약을 이완한 뒤 승수를 서브그래디언트 또는 Bundle 방식으로 갱신한다. 듀얼 하한과 실현가능한 프라이멀 상한 사이의 갭을 줄이는 것이 운영의 중심이 된다.

해를 얻은 뒤에는 최적성의 근거를 확인한다

LP에서는 강한 듀얼성이 성립하므로 듀얼 갭이 0이면 최적성을 보장할 수 있다. 섀도우 프라이스를 이용한 감도분석은 경영지표 해석에도 활용된다.

IP에서는 MIP GAP를 기준으로 최적성을 인증한다. 허용 GAP 안에서 조기 종료한 준최적 솔루션도 실무에서 사용할 수 있다. 라그랑주 이완의 듀얼 최적값은 하한을 제공하며, 프라이멀 복구(heuristic)로 상한을 만들어 갭 기반 종료 규칙을 설계한다.

기법	성능(해속/갭)	확장성(변수·제약)	일관성(최적성 보장)	안정성(수렴·민감)	운영 편의(튜닝·해석)
LP(Simplex/Interior)	매우 우수, 실시간 가능	매우 우수, 수십만 규모 처리	강함, 듀얼 갭 0	높음, 감도분석 용이	우수, 파라미터 단순
IP(MILP)	문제 의존, 탐색 폭 큼	중간~우수, 컷/휴리스틱 필수	강함, GAP 기준 인증	중간, 데이터 스케일 민감	중간, 모델링·튜닝 요구
Lagrangian	하한 계산 빠름, 프라이멀 복구 필요	우수, 분해·병렬 적합	듀얼 하한만 보장	중간, 승수 업데이트 민감	중간, 구현 복잡성 존재

⤢✕

공급망부터 네트워크 설계까지의 적용 방식

공급망과 생산 계획에서는 수요 충족, 공장 및 창고 용량, 운송비 최소화를 함께 모델링한다. 흐름 최적화에는 LP를 쓰고, 이산 배치나 설비 온·오프 조건은 MILP에 포함한다. 공장과 창고를 묶는 제약은 라그랑주 이완으로 완화해 사이트별 하위문제를 병렬화하고 듀얼 갭을 관리할 수 있다.

인력과 교대 스케줄링에서는 근무 규정, 최소 인원, 연속 근무 제한 같은 논리 조건을 이진 변수로 표현한다. 최적 스케줄은 IP로 구하며, 인원이나 기간이 커지면 Lagrangian 또는 컬럼생성(Dantzig-Wolfe)을 적용한다.

투자 포트폴리오에서는 리스크 예산, 섹터 한도, 최소 거래단위의 정수 제약을 고려한다. 연속 LP로 초기 배분을 구한 뒤 IP로 라운딩과 카디널리티를 통제할 수 있다. 트랜잭션 코스트와 세금이 들어가면 컷 및 프리솔브 전략을 병행한다.

시설 위치 결정과 경로 선택이 함께 있는 네트워크 설계는 고정비와 흐름이 결합된 문제다. MILP와 Benders 분해를 적용할 수 있으며, 수요와 용량의 결합은 라그랑주 이완으로 풀어 서브문제의 최단경로와 최소컷을 반복 계산한다.

비용 절감 520%, 납기 준수율 1030%p 향상, 재고 회전 10~25% 개선이 예상된다. 의사결정 시간은 50% 이상 단축할 수 있고, 대안 탐색 범위를 넓혀 의사결정 품질을 높일 수 있다. 섀도우 프라이스와 바인딩 제약 리포트는 설명가능성을 높이며, 운영 표준화와 의사결정 편차 축소, 시뮬레이션 및 시나리오 플래닝 체계화에도 연결된다.

규모가 커질수록 모델 품질과 운영 규칙이 중요해진다

데이터 스케일링과 전처리로 중복·암묵 제약을 제거하면 수렴 안정성이 높아진다. 대규모 문제는 Benders 또는 Dantzig-Wolfe 분해로 나눌 수 있다. 온프레미스와 클라우드를 함께 쓰는 실행 환경에서는 Warm-start와 영업일 반복해 설정을 통해 운영비를 줄이고, 듀얼 및 베이시스 로그를 보관해 해석 가능성을 확보한다.

단위와 스케일은 일관되게 유지하고, 큰 계수와 작은 계수가 섞이지 않게 해야 한다. 불능에 대비해 슬랙과 큰벌점(Big-M)을 사용할 때는 과도한 M 값을 피하고 논리 컷으로 대체한다.

MILP는 프리솔브를 강화하고 Flow cover, MIR 같은 컷 전략을 선택하며, best-bound와 depth-first 중 문제에 맞는 탐색전략을 적용한다. 라그랑주 이완은 Polyak 방식의 승수 보폭 적응과 번들 방법으로 진동을 억제한다. 재실행 파이프라인에는 Warm-start, 솔루션 풀이 로그, IIS 자동 수집을 포함한다.

SLA에 맞춰 종료 규칙도 정해야 한다. 예를 들어 MIP GAP ≤ 1% 또는 5분 타임아웃을 기준으로 둘 수 있다. 최적성과 계산시간, 정수화의 엄격성과 실무 수용성, 단일 일괄 최적화와 계층 또는 분해 접근 사이의 균형을 함께 판단해야 한다.

모델을 운영에 연결하는 순서

먼저 KPI와 의사결정수준(전략/전술/운영)을 명확히 하고 데이터 품질, 결측, 이상을 점검한다. 이어 목적과 제약을 선형화하며 정수 변수는 필요한 범위로 줄이고, 불능 방지용 슬랙과 벌점을 설계한다.

초기 실험에서는 LP, IP, Lagrangian의 적합성을 비교한다. 베이스라인 LP 릴랙세이션 성능을 확인한 뒤 정수화를 진행한다. 이후 프리솔브, 컷, 휴리스틱을 활성화하고 분해기법을 병행하며, Warm-start와 시나리오 배치 실행으로 규모를 다룬다.

운영 단계에서는 듀얼·프라이멀 갭과 IIS를 회귀 테스트에 포함하고, 모니터링·알림·버전관리 체계를 갖춘다.

LP와 MILP를 전환하는 최소 예제

전제조건: Python 3.10+, ortools 패키지 설치(pip install ortools). 단위 테스트 수준 예제, 소규모 데이터셋 기준이다.

2개 공장에서 2개 고객 수요를 최소 비용으로 공급하는 문제이며, 변수 유형을 연속(LP) 또는 정수(MILP)로 전환한다.

from ortools.linear_solver import pywraplp

def transport_example(as_integer=False):
    # 데이터
    plants = ['P1', 'P2']
    customers = ['C1', 'C2']
    supply = {'P1': 35, 'P2': 50}
    demand = {'C1': 30, 'C2': 40}
    cost = {('P1','C1'): 2, ('P1','C2'): 4, ('P2','C1'): 3, ('P2','C2'): 1}

    solver = pywraplp.Solver.CreateSolver('CBC')  # LP/MILP 모두 지원
    if not solver:
        raise RuntimeError('Solver 초기화 실패')

    # 변수: x[p,c] ≥ 0
    x = {}
    for p in plants:
        for c in customers:
            if as_integer:
                x[p,c] = solver.IntVar(0, solver.infinity(), f'x_{p}_{c}')
            else:
                x[p,c] = solver.NumVar(0.0, solver.infinity(), f'x_{p}_{c}')

    # 목적: 총 비용 최소화
    solver.Minimize(solver.Sum(cost[p,c] * x[p,c] for p in plants for c in customers))

    # 제약: 공급 한도
    for p in plants:
        solver.Add(solver.Sum(x[p,c] for c in customers) <= supply[p])
    # 제약: 수요 충족
    for c in customers:
        solver.Add(solver.Sum(x[p,c] for p in plants) >= demand[c])

    status = solver.Solve()
    if status not in (pywraplp.Solver.OPTIMAL, pywraplp.Solver.FEASIBLE):
        raise RuntimeError('해 미발견: Infeasible 또는 오류')

    total_cost = solver.Objective().Value()
    sol = {(p,c): x[p,c].solution_value() for p in plants for c in customers}
    return total_cost, sol

if __name__ == "__main__":
    for flag in (False, True):
        total, sol = transport_example(as_integer=flag)
        t = 'MILP(정수)' if flag else 'LP(연속)'
        print(f'[{t}] 총비용={total:.2f}, 해={sol}')

정수 변수를 더해 고정비 유무를 나타내는 이진 변수와 Big-M 논리 제약을 구성할 수 있다. Flow cover와 Knapsack cover를 추가하면 폴리토프를 강화할 수 있으며, 과거 해나 휴리스틱 출력은 Warm-start의 초기 해로 쓸 수 있다.