Difference between Optimality cuts and Feasibility cuts for L shaped method in stochastic programming?

Question

What is the difference between Optimality cuts and Feasibility cuts for L shaped method in stochastic programming? Like for the following problem they used Optimality cuts, $$ \begin{aligned} & z=\min 100 x_1+150 x_2+\mathrm{E}_{\boldsymbol{\xi}}\left(q_1 y_1+q_2 y_2\right) \\ & \text { s. t. } \quad x_1+x_2 \leq 120 \text {, } \\ & 6 y_1+10 y_2 \leq 60 x_1 \text {, } \\ & 8 y_1+5 y_2 \leq 80 x_2 \text {, } \\ & y_1 \leq d_1, \quad y_2 \leq d_2, \\ & x_1 \geq 40, \quad x_2 \geq 20, \quad y_1, y_2 \geq 0, \\ & \end{aligned} $$ where $\boldsymbol{\xi}^T=\left(d_1, d_2, q_1, q_2\right)$ takes on the values $(500,100,-24,-28)$ with probability $0.4$ and $(300,300,-28,-32)$ with probability $0.6$.

And Feasibility cuts for the the following problem, $$ \begin{gathered} \min 3 x_1+2 x_2-\mathrm{E}_{\boldsymbol{\xi}}\left(15 \mathbf{y}_1+12 \mathbf{y}_2\right) \\ \text { s. t. } 3 \mathbf{y}_1+2 \mathbf{y}_2 \leq x_1, \\ 2 \mathbf{y}_1+5 \mathbf{y}_2 \leq x_2, \\ .8 \boldsymbol{\xi}_1 \leq \mathbf{y}_1 \leq \boldsymbol{\xi}_1, \\ .8 \boldsymbol{\xi}_2 \leq \mathbf{y}_2 \leq \boldsymbol{\xi}_2, \\ x, \mathbf{y} \geq 0, \text { a.s., } \end{gathered} $$ with $\xi_1=4$ or 6 and $\xi_2=4$ or 8 , independently, with probability $1 / 2$ each and $\boldsymbol{\xi}=\left(\boldsymbol{\xi}_1, \boldsymbol{\xi}_2\right)^T$

Q: I have the solution. But what I am missing is the clear meaning of Optimality Cuts and Feasibility Cuts used in L shape method and Why? It will be a great help if anyone give some insight or resource for clear explanation of that.

Answer 1

Given a certain master problem solution, when the subproblem is infeasible, a feasibility cut is added to the master problem. On the other hand, an optimality cut is added to the master problem when the subproblem is feasible, but its objective implies the trial master problem solution is not globally optimal. Both cuts remove the current master problem solution from being searched in future iterations.

As demonstrated by [1]:

(The L-shaped method) is essentially the same as the algorithm developed by Benders [2].

Therefore, besides papers about the L-shaped method, papers about Benders Decomposition also help with understanding these two types of cuts.

Finally, I would like to recommend the literature review paper [3], which I feel is easier for understanding the Benders decomposition than [1] and [2].

• [1] Van Slyke, R. M., & Wets, R. (1969). L-shaped linear programs with applications to optimal control and stochastic programming. SIAM Journal on Applied Mathematics, 17(4), 638–663. https://doi.org/10.1137/0117061
• [2] Benders, J. F. (1962). Partitioning procedures for solving mixed-variables programming problems. Numerische Mathematik, 4(1), 238–252. https://doi.org/10.1007/BF01386316
• [3] Rahmaniani, R., Crainic, T. G., Gendreau, M., & Rei, W. (2017). The Benders decomposition algorithm: A literature review. European Journal of Operational Research, 259(3), 801–817. https://doi.org/10.1016/j.ejor.2016.12.005