# Minimax regret formulation with Benders decomposition

 3 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: 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 )$$ 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: $$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: what the Benders cut should look like what the convergence criterion should be 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. asked 22 Jan '13, 06:53 ikonikon 31●1●4 accept rate: 0% Paul Rubin ♦♦ 14.6k●5●13

 2 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. answered 22 Jan '13, 16:53 Paul Rubin ♦♦ 14.6k●5●13 accept rate: 19%
 toggle preview community wiki

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "Title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported

Tags: