Answers to: Minimax regret formulation with Benders decompositionhttp://www.or-exchange.com/questions/7307/minimax-regret-formulation-with-benders-decomposition<p>Hello all,</p>
<p>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:</p>
<hr>
<p>\(z = \min \sum_{m=1}^{M} \pi_{m}\left ( cx_{m} + qy_{m} \right )\),</p>
<p>where</p>
<p>\(x_{m}\) is the investment decision at scenario tree node \(m\),</p>
<p>\(y_{m}\) is the operation decision at scenario tree node \(m\),</p>
<p>\(\pi_{m}\) is the probability of occurrence for scenario tree node \(m\)</p>
<hr>
<p>When moving all operation variables to the sub-problem, the master problem objective function is:</p>
<p>\(z = \min \sum_{m=1}^{M} \pi_{m}\left ( cx_{m} + \alpha_{m} \right )\),</p>
<p>where</p>
<p>\(\alpha_{m}\) is the sub-problem approximation subject to the appended Bender cuts.
The cuts to be appended at iteration \(v\) are:</p>
<p>\(\alpha_{m} \geq h_{m}^{v-1} + \lambda_{m}^{v-1} ( x_{m}-x_{m}^{v-1} ), \forall m\),</p>
<p>where</p>
<p>\(h_{m}^{v-1}\) is the optimal sub-problem solution from the previous iteration</p>
<p>\(\lambda_{m}^{v-1}\) is the dual multiplier from the previous iteration </p>
<hr>
<p>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:</p>
<ol>
<li>
<p>First, compute the optimum solution for each scenario (i.e. for all nodes \(m\) constituting scenario-index set \(\Omega_{s})\) in isolation (one problem per scenario) as in:
\(d_{s} = \min \sum_{m \epsilon \Omega_{s}}\left ( cx_{m} + qy_{m} \right )\)</p>
</li>
<li>
<p>Then, introduce an auxiliary "regret" variable \(r\) to be minimized, set to be greater than the regret (with respect to the corresponding deterministic solution) experienced under each scenario: </p>
</li>
</ol>
<p>\(z = \min r \)</p>
<p>\(r \geq \sum_{m \epsilon \Omega_{s}}\left ( cx_{m} + qy_{m} \right ) - d_{s}, \forall s\)</p>
<hr>
<p>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:</p>
<ol>
<li>what the Benders cut should look like</li>
<li>what the convergence criterion should be</li>
</ol>
<p>thank you in advance for your input!</p>
<p>ikonikon</p>
<p>[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.</p>enTue, 22 Jan 2013 16:53:54 -0500Answer by Paul Rubinhttp://www.or-exchange.com/questions/7307/minimax-regret-formulation-with-benders-decomposition/7314<p>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.</p>Paul RubinTue, 22 Jan 2013 16:53:54 -0500http://www.or-exchange.com/questions/7307/minimax-regret-formulation-with-benders-decomposition/7314