SAA와 SDDP로 푸는 확률적 최적화 모델링 전략

불확실성을 포함한 의사결정에서는 하나의 예측값만으로 모델을 세우기 어렵다. SAA(Sample Average Approximation)와 SDDP(Stochastic Dual Dynamic Programming)는 대규모 확률적 계획 문제를 현실적인 계산 시간 안에서 다루기 위한 대표적 방법이며, 에너지·공급망·금융 분야에서 활용된다.

표본 평균과 컷 근사로 불확실성을 다루는 방식

SAA는 표본 시나리오를 결정론적 문제로 바꾼다

SAA는 기대값 목적함수를 유한한 시나리오 표본의 평균으로 근사하고, 이를 결정론적 등가 문제(Extensive Form)로 변환하는 방식이다. 표본 수가 늘면 최적값과 해는 참 문제에 확률수렴하는 일관성을 가진다.

표본을 여러 번 복제하고 홀드아웃 시뮬레이션을 수행하면 최적화 갭도 추정할 수 있다. 모델 구조가 비교적 단순하고 정수 의사결정이 중심인 문제에 자연스럽게 적용된다.

SDDP는 다단계 정책을 반복해서 다듬는다

SDDP는 다단계 확률 동적계획의 벨만함수를 선형(볼록) 컷으로 점진적으로 근사하는 분해 최적화 알고리즘이다. 전방 패스에서 정책을 시뮬레이션하고, 후방 패스에서 이중문제를 풀어 새 컷을 생성한다.

이 과정에서 하한과 상한을 관리하며, 대형 시나리오트리에서도 선형 스케일로 확장할 수 있다. 다만 볼록·선형 또는 근사 볼록 재과업(recours)이 전제이며, 비볼록 또는 정수 재과업에는 근사·휴리스틱이나 혼성 프레임이 필요하다.

모델 품질을 좌우하는 설계 항목

입력 분포와 상관 구조, 단계별 독립·의존성 가정은 명시해야 한다. 시나리오 트리나 샘플 경로를 설계할 때는 단순 Monte Carlo, 라틴하이퍼큐브(LHS), 중요도 샘플링을 사용할 수 있다. 희귀사건을 반영해야 한다면 표본 가중과 리샘플링도 고려 대상이다.

목적함수는 기대값 최소화에만 한정되지 않는다. CVaR, 분산 제약, 첼레비셰프 바운드 같은 위험규범을 함께 둘 수 있다. SAA에서는 위험항을 표본 평균으로 치환하고, SDDP에서는 단계별 리스크인 마티우센 리스크나 CVaR를 적용해 리스크-어버스 SDDP를 구성한다.

수렴 판단 방식도 서로 다르다. SAA는 복제별 최적값의 분산을 추정하고 홀드아웃 시뮬레이션으로 신뢰구간을 산출해 정지 기준을 정한다. SDDP는 컷 기반 하한과 정책 시뮬레이션 기반 상한의 갭을 사용하며, 컷 프루닝·풀링과 레벨·번들 기법으로 안정화한다.

계산 자원을 쓰는 방식 역시 다르다. SAA는 시나리오 병렬화와 Extensive Form MIP/LP용 분산 MILP 솔버를 활용할 수 있다. SDDP는 단계·시나리오별 서브문제를 병렬화하고, 멀티컷과 싱글컷 사이의 트레이드오프를 조정한다. 온디맨드 컷 생성은 메모리 관리에 도움이 된다.

항목	SAA	SDDP
성능	중소 규모에서 우수, 표본 충분 시 높은 해 품질	대규모 다단계에서 안정적 수렴, 정책 품질 균형
확장성	시나리오 수에 비례한 메모리·시간 증가	단계 수·시나리오 경로에 선형 확장, 컷 관리 필요
일관성	표본 수 증가 시 일관성 보장	하한·상한 단조 수렴, 갭 기반 정지
안정성	표본 분산·희귀사건에 민감	컷 과적합 방지가 필요하며 프루닝·정규화를 사용
운영 편의	모델링이 단순하고 솔버 친화적	컷·샘플링·리스크 설정 요소가 많아 전용 라이브러리 권장

SAA와 SDDP의 반복 구조

⤢✕

에너지부터 포트폴리오까지의 적용 맥락

전력·에너지 분야에서는 수력-열병합 스케줄링, 저수지 운영, 저장장치(배터리) 운용에 SDDP를 적용하고 시나리오 기반으로 발전비를 최소화한다. 확률적 수요와 재생발전 예측 오차를 반영하며, 리스크-어버스 SDDP로 가격 변동성과 부족 비용을 제어할 수 있다.

공급망과 재고 문제에서는 다품목 재고, 생산·배송 계획을 SAA로 대규모 시나리오에 맞춰 최적화하고 서비스 레벨을 CVaR로 관리한다. 시나리오 축소와 중요도 샘플링은 희귀 수요 피크 대응에 쓰인다.

금융 포트폴리오에서는 거래비용과 규제 제약 아래의 다기간 리밸런싱에 SDDP를 적용해 동적 헤지 정책을 도출하고 CVaR를 제어한다. 2단계 배당·유동성 제약 문제는 SAA로 빠르게 탐색한 뒤, 다단계 확장을 SDDP로 고도화할 수 있다.

자원 계획과 정비에서는 유지보수 시점과 용량 확장 결정에 수요·고장 불확실성을 반영한다. SAA는 전처리 설계에, SDDP는 롤링 운영 정책 생성에 활용된다.

성능 지표와 운영상 점검 지점

상·하한 갭 ε에 도달하는 시간은 동등 Extensive Form 대비 2~~10배 단축될 수 있으며, 이는 문제와 플랫폼에 의존한다. 리스크-어버스 설정에서는 Tail 손실(CVaR)이 10~~30% 감소한 사례가 보고됐다. 도메인 의존성이 있으므로 모델의 전제와 적용 범위를 함께 봐야 한다.

정책 해석 용이성, 불확실성 시나리오 전 범위의 커버리지 강화, 운영 신뢰성 제고도 함께 기대할 수 있다. 운영 단계에서는 최적화 갭, 정책 시뮬레이션 비용의 평균·분산, VaR/CVaR, 계산 시간, 메모리 사용량을 모니터링하는 체계를 둔다.

문제 구조에 맞춰 선택하고 검증하기

2단계·정수 의사결정이 중심이고 모델이 간결하면 SAA를 우선 검토한다. 다단계 구조와 대규모 상태공간, 볼록 재과업이 본체라면 SDDP가 적합하다. 비볼록성이나 강한 이산성이 존재하면 SAA 또는 PH(Progressive Hedging)·라그랑주 분해의 혼합을 검토한다.

분포는 캘리브레이션하고 드리프트·시즌성을 반영하며 공분산을 안정화한다. LHS는 분산 축소에, 희귀 이벤트에는 중요도 가중에 쓸 수 있다. 시나리오 수 N은 분산과 해의 민감도 분석으로 정한다.

SAA에서는 복제 R≥10을 권장하고, 홀드아웃 10k+ 경로 시뮬레이션으로 성능을 검증한다. 정지 기준은 신뢰구간 폭이나 상대갭으로 둘 수 있다. SDDP에서는 멀티컷, 연령·도미넌스 기반 컷 프루닝, Trust-region과 level 정규화를 적용하고 샘플 경로 배치 수를 병렬로 확장한다.

Out-of-sample 시뮬레이션은 필수다. 스트레스 시나리오의 상·하위 α-분위에서 제약 위반율을 확인하고, 데이터 드리프트를 모니터링하면서 정책 재학습 주기를 관리한다. 모델 변경 이력과 성능 리포트도 표준화한다.

교육용 최소 구현 예시

다음 코드는 교육용 최소 예시다. 버전은 예시이며 최신 정보 확인이 필요하다.

SAA: Python(Pyomo) 뉴스벤더 간단 예시

환경: Python 3.10+, pyomo 6.6+, glpk 또는 cbc
전제: 수요 불확실성, 과잉 재고·결품 비용 포함

# pip install pyomo
# GLPK/CBC 솔버 필요
import random
import statistics
from pyomo.environ import ConcreteModel, Var, NonNegativeReals, Objective, minimize, Constraint, SolverFactory, Param, RangeSet

def build_newsvendor_model(demands, c, h, p):
    m = ConcreteModel()
    N = len(demands)
    m.S = RangeSet(0, N-1)
    m.q = Var(domain=NonNegativeReals)  # 주문량
    m.obj = Objective(
        expr = (1/N) * sum(c*m.q + h*max(m.q - d, 0) + p*max(d - m.q, 0) for d in demands),
        sense = minimize
    )
    return m

def solve_saa(num_scenarios=500, replications=5, seed=42):
    random.seed(seed)
    c, h, p = 5.0, 1.0, 10.0  # 단가/과잉/결품 비용
    true_demand = lambda: max(0, random.gauss(100, 30))
    sols, objs = [], []
    solver = SolverFactory("glpk")
    for r in range(replications):
        demands = [true_demand() for _ in range(num_scenarios)]
        m = build_newsvendor_model(demands, c, h, p)
        res = solver.solve(m, tee=False)
        sols.append(m.q.value)
        # 홀드아웃 시뮬레이션으로 성능 추정
        test = [true_demand() for _ in range(10000)]
        cost = sum(c*sols[-1] + h*max(s - d, 0) + p*max(d - s, 0) for d in test for s in [sols[-1]])/len(test)
        objs.append(cost)
    mean_cost = sum(objs)/len(objs)
    std_cost = statistics.pstdev(objs)
    return {"q_mean": sum(sols)/len(sols), "cost_mean": mean_cost, "cost_std": std_cost}

if __name__ == "__main__":
    print(solve_saa())

SDDP: Julia(SDDP.jl) 단순 저장장치 예시

환경: Julia 1.10+, SDDP.jl 1.x, HiGHS 또는 Gurobi
전제: 무작위 전력 가격, 저장장치 충방전 의사결정, 선형 손실 무시

# using Pkg; Pkg.add(["SDDP","HiGHS"])
using SDDP, HiGHS, Distributions

T = 3
price_dist = [Normal(50.0, 10.0) for t in 1:T]

model = SDDP.PolicyGraph(
    stages = T,
    sense = :Min,
    lower_bound = 0.0,
    optimizer = HiGHS.Optimizer,
) do sp, t
    @variable(sp, 0 <= e <= 100)     # 저장 에너지
    @variable(sp, -50 <= u <= 50)    # 충방전(+방전 수익)
    @stageobjective(sp, -SDDP.parameter(sp, :price) * u)  # 비용 = -수익
    @constraint(sp, e == SDDP.state(sp, :e, 0.0) + u)
    @constraint(sp, e >= 0)
end

# 무작위 가격 샘플러 연결
SDDP.parameterize(model) do ω
    for t in 1:T
        ω[:price, t] = rand(price_dist[t])
    end
end

SDDP.train(model; iteration_limit = 200, print_level = 1)
sim = SDDP.simulate(model, 1000)
avg_profit = -mean([sum(stage.objective for stage in traj) for traj in sim])
println("Estimated average profit = ", avg_profit)

위 예시에서 위험회피 설정은 SDDP.parameter로 시나리오 가중과 리스크 함수(CVaR 등)를 추가하는 방식으로 구성한다. 컷 프루닝과 정규화 옵션은 수렴 안정화에 활용할 수 있다.

SAA는 초기 구조와 파라미터 튜닝에, SDDP는 다단계 정책 최적화에 각각 강점이 있다. 리스크-어버스 목적과 병렬 계산을 함께 설계하면 실운영 문제의 불확실성을 더 체계적으로 다룰 수 있다.