|
Hello all, I have a multi-stage stochastic problem and I am employing multi-cut Benders decomposition to solve it. The objective function is that of a typical planning problem, essentially the summation of expected investment and operation cost across all scenario tree nodes. A node-variable formulation of the non-decomposed problem is as follows: \(z = \min \sum_{m=1}^{M} \pi_{m}\left ( cx_{m} + qy_{m} \right )\), where \(x_{m}\) is the investment decision at scenario tree node \(m\), \(y_{m}\) is the operation decision at scenario tree node \(m\), \(\pi_{m}\) is the probability of occurrence for scenario tree node \(m\) When moving all operation variables to the sub-problem, the master problem objective function is: \(z = \min \sum_{m=1}^{M} \pi_{m}\left ( cx_{m} + \alpha_{m} \right )\), where \(\alpha_{m}\) is the sub-problem approximation subject to the appended Bender cuts. The cuts to be appended at iteration \(v\) are: \(\alpha_{m} \geq h_{m}^{v-1} + \lambda_{m}^{v-1} ( x_{m}-x_{m}^{v-1} ), \forall m\), where \(h_{m}^{v-1}\) is the optimal sub-problem solution from the previous iteration \(\lambda_{m}^{v-1}\) is the dual multiplier from the previous iteration Currently, I am looking to move from an expected cost decision criterion to minimization of the maximum regret experienced. My non-decomposed solution strategy is to:
\(z = \min r \) \(r \geq \sum_{m \epsilon \Omega_{s}}\left ( cx_{m} + qy_{m} \right ) - d_{s}, \forall s\) The above approach works fine. However, I am having difficulty understanding how a Benders decomposition scheme (again, separating \(x\) and \(y\)) could be applied to speed up convergence. According to [1], a straightforward implementation of Benders should be possible, but I am not certain:
thank you in advance for your input! ikonikon [1] Gorenstin, B.G.; Campodonico, N.M.; Costa, J.P.; Pereira, M.V.F.; , "Power system expansion planning under uncertainty," Power Systems, IEEE Transactions on , vol.8, no.1, pp.129-136, Feb 1993. |
|
I don't do stochastic models, but it seems to me your decomposition would be essentially the same. Rewrite the master as \(\min r \ni r \ge \sum_{m\in\Omega_{s}}\left(cx_{m}+\alpha_{m}\right)-d_{s}\,\,\forall s\), then minimize \(qy_{m}\) given \(x_{m}\) in a subproblem and, if \(\alpha_{m}\) underestimates it, add the optimality (point) cut you got before. Convergence would be an optimal master solution that did not generate any new Benders cuts. |
