표본평균근사법 (Sample Average Approximation)
쉽게 풀면
전 국민의 의견을 일일이 물어볼 수 없으니 표본을 뽑아 여론조사를 하듯, 미래에 벌어질 수 있는 무수한 상황의 평균을 정확히 계산할 수 없을 때 몇백 개의 시나리오를 뽑아 그 평균으로 대신하는 방법입니다. 이렇게 바꾸고 나면 문제 안에 확률이 사라지고, 시나리오마다 변수가 붙은 커다란 결정론적 계획 문제만 남습니다. 그러면 기존의 선형계획이나 정수계획 도구를 그대로 쓸 수 있습니다. 표본을 많이 뽑을수록 원래 문제에 가까워지지만 문제 크기도 함께 커지므로, 어느 정도에서 멈출지를 통계적으로 판단하는 절차가 함께 따라옵니다.
왜 중요한가
재고, 입지, 용량 계획처럼 불확실성을 명시적으로 다루는 문제에서 기댓값을 닫힌 형태로 계산할 수 있는 경우는 드뭅니다. 이 기법은 그런 문제를 이미 성숙한 수리계획 솔버가 다룰 수 있는 형태로 바꿔 주고, 나아가 얻은 해가 참 최적해에서 얼마나 떨어져 있는지를 신뢰구간 형태로 제시할 수 있게 해 줍니다.
논문에서는 이렇게 쓰입니다
표본을 키우면 근사 문제의 해가 참 최적해에 수렴한다는 성질을 이용해, 추정된 격차가 충분히 작아지는 지점에서 표본 크기를 확정했다는 뜻입니다.
여러 독립 표본문제의 최적값 평균이 최소화 문제에서 참 최적값의 하한을 준다는 성질을 이용한 표준적인 격차 추정 절차입니다.
해를 구할 때 쓴 시나리오로 그 해를 평가하면 성능이 낙관적으로 부풀려지므로, 독립적인 시나리오 집합으로 다시 검증했다는 의미입니다.
조금 더 깊게 보면
표본평균근사법의 이론적 뒷받침은 표본 수가 커질 때 근사 문제의 최적값과 최적해가 원래 문제의 것으로 수렴한다는 결과입니다. 특히 결정변수가 이산인 경우 수렴이 상당히 빠르다는 점이 알려져 있습니다. 실무 절차는 보통 두 갈래로 나뉘어, 여러 개의 중간 크기 표본문제를 풀어 최적값의 하한을 추정하고, 그중 하나의 해를 매우 큰 표본으로 평가해 상한을 얻은 뒤 둘의 차이로 최적성 격차를 보고합니다. 여기에 공통난수법 같은 분산감소기법을 결합해 추정치의 흔들림을 줄이기도 합니다.
주의할 점
표본 수에 비례해 문제 크기가 커지므로 정수변수가 섞이면 계산 부담이 급격히 늘어납니다. 또 얻어진 해는 어디까지나 그 표본에 대한 최적해여서, 같은 표본으로 성능까지 평가하면 결과가 낙관적으로 편향됩니다. 시나리오 수를 줄이는 시나리오 감축 기법과는 목적이 다릅니다.