I'm reading through "Algorithms for Stochastic Mixed-Integer Programming Models", Elsevier Handbooks in OR&MS Volume 12 (Discrete Optimization), Chapter 9 and I'm stuck. For those without access to the Handbooks, I found a preprint version at: http://server1.tepper.cmu.edu/Seminars/docs/Sen_paper1-2.pdf.

On page 531, Sen describes an algorithm from Laporte and Loveaux's 1993 paper "The integer L-shaped method for stochastic integer programs with complete recourse". In step 2b, he says:

Define \(\eta_k(x) = \max \left\{\eta_{k-1}(x), ~\alpha + \beta x \right\}\)

In the first iteration, \(\eta_{k-1}(x)\) is the constant lower bound on the expected recourse, and \(\alpha + \beta x \), the right-hand side of equation 3.4b on page 530, is a function of the binary first-stage variable \(x\). given that the first term of \(\max\) is a constant, and the second term is a function of \(x\), I'm not clear what the \(\max\) function means. In the example instance on the next page, the \(\beta x\) term in \(\alpha + \beta x \) cancels out, but this isn't always the case.

What does step 2b mean?

asked 13 Oct '11, 17:20

Luis%20de%20la%20Torre's gravatar image

Luis de la T...
accept rate: 11%

edited 10 May '18, 14:58

fbahr's gravatar image

fbahr ♦

PS: You surely meant to write North Holland/Elsevier Handbook[s] in OR&MS, didn't you?

(13 Oct '11, 18:30) fbahr ♦

You're right, I did mean this. I'll correct this. I confused myself by reading both the 2011 Wiley EORMS and the older Elsevier Handbook at the same time. The same optimality cuts are also described in Sen's article in the 2011 Wiley EORMS.

(13 Oct '11, 18:37) Luis de la T...

This means that you keep all the cuts that you have added so far. Here $eta_k(x)$ is the point-wise maximum of all (affine) cuts and is the current (piece-wise linear) convex under-approximation of the expected recourse function.


answered 13 Oct '11, 19:31

Shabbir%20Ahmed's gravatar image

Shabbir Ahmed
accept rate: 33%

Thanks, should've been obvious that it was the point-wise maximum of all cuts.

(14 Oct '11, 13:03) Luis de la T...

@OPer: were you able to implement the integer L-shaped method?? I am currently stumbled upon it while trying to transfer the non-integer, single-cut version of L-shaped method to an integer version one...


answered 26 Apr '18, 23:57

ghjk's gravatar image

accept rate: 0%

Your answer
toggle preview

Follow this question

By Email:

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



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



Asked: 13 Oct '11, 17:20

Seen: 2,210 times

Last updated: 10 May '18, 14:58

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