에너지시스템 최적화/게임이론 강의: 8) Optimization problems with decomposable structure
이 포스팅은, Technical University of Denmark의 박사과정 과목 “Advanced Optimization and Game Theory for Energy Systems” (Prof. Jalal Kazempour) 의 8강을 필자가 요약한 내용이다.
큰 문제를 작은 문제’들’로 쪼개기
에너지 시스템에 대한 최적화 문제는 종종 그 크기가 크다. 매우 많은 시간들을 포함하기 때문일 수도 있고, stochastic programming에서 매우 많은 시나리오들을 고려하기 때문일 수도 있다.
문제의 크기가 극단적으로 크면 현재의 컴퓨터로 풀지 못하는 (intractable) 문제가 될 수 있으며, 풀리긴 하더라도 필요한 시간 내에 풀어야만 할 수도 있다. 이를테면 하루전 시장에서의 급전계획을 결정하는 문제의 경우, 몇 시간 안에는 풀려야 다음 날의 실시간 시장에 결과 반영이 가능하다.
그런데 에너지 분야에서는, 큰 최적화 문제가 종종 작은 최적화 문제들로 쪼개질 수 있다. 매우 많은 시간들을 포함하는 문제를 시간별 소문제들로 쪼갠다든지, 매우 많은 시나리오들을 고려하는 문제를 시나리오별 소문제들로 쪼갤 수 있다. 당연히 각 소문제는 원래 문제 대비 쉽게 풀린다.
작은 문제들로 쪼갤 수 있는 구조를 갖고 있지만 그 자체로는 큰 단일 문제인 최적화 문제의 경우, 바로 작은 문제들로 쪼개지 못하도록 만드는 변수 (complicating variables) 혹은 제약조건 (complicating constraints) 이 있다. 아래 두 슬라이드가 각각의 예시를 보여준다.
에너지 분야에 대한 간단한 예시들은 아래와 같다.
Generation expansion problem에서는, 일반적으로 investment variable (설비 용량 등) 을 complicating variable로 보고 fix하는 것이 좋다.
01) Market clearing as an optimization problem
02) Market clearing as an equilibrium problem
03) Desirable properties of market-clearing mechanisms
04) Market clearing using a cooperative game approach
05) Stochastic market clearing
06) Robust approaches for market clearing
07) Bilevel programming in energy systems
08) Optimization problems with decomposable structure
09) Benders’ decomposition: Theory
10) Benders’ decomposition: Applications
11) Augmented Lagrangian relaxation
12) Variants of ADMM and applications