Minimax regret formulation with Benders decomposition

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:

1. 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 )\)

2. 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:

1. what the Benders cut should look like
2. 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.