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.

asked 22 Jan '13, 06:53

ikonikon's gravatar image

ikonikon
3114
accept rate: 0%

edited 22 Jan '13, 16:44

Paul%20Rubin's gravatar image

Paul Rubin ♦♦
14.6k412


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.

link

answered 22 Jan '13, 16:53

Paul%20Rubin's gravatar image

Paul Rubin ♦♦
14.6k412
accept rate: 19%

edited 22 Jan '13, 16:55

Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • 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:

×58
×35
×1

Asked: 22 Jan '13, 06:53

Seen: 6,140 times

Last updated: 22 Jan '13, 16:55

OR-Exchange! Your site for questions, answers, and announcements about operations research.