Questions tagged [stochastic-programming]

For questions about optimization problems in which one or more parameters are stochastic, with known probability distributions or discrete scenarios. The goal is often, but not always, to minimize or maximize the expected value of the objective function.

Filter by
Sorted by
Tagged with
0 votes
0 answers
30 views

When can we unnest the minimizations/recursions in value functions(bellman optimality)?

When reading the following paper(page 4): An Approximate Dynamic Programming Approach for Dual Stochastic Model Predictive Control I could see that they were able to unnest the minimization's in the ...
richard baws's user avatar
1 vote
0 answers
35 views

How would the Contextual Stochastic Optimization framework be applied to a bilevel problem whose uncertain parameters lie in the inner problem?

Although I only heard about Contextual Stochastic Optimization (CSO) a few months ago, I know now the excitement has been going on for a while. I'm not sure if the idea of CSO has been around for long,...
Jxson99's user avatar
  • 141
4 votes
1 answer
104 views
+50

What's the best way to speed up Benders Decomposition for a stochastic vehicle routing problem?

Currently I am working on an implementation of Benders Decomposition that solves a stochastic vehicle routing problem with synchronisation constraints. Sadly, at the moment it is not performing fast ...
Arctic_Skill's user avatar
1 vote
1 answer
88 views

Benchmark problems for Benders Decomposition

we are implementing a scheduling model using Benders Decomposition. Does someone know of any existing implementation of Benders or any repositories that contain continuous or integer problems solved ...
Vivek's user avatar
  • 11
-3 votes
0 answers
30 views

Scenario-based optimization management of product during production disruption

...
Chitranjan Singh Thakur's user avatar
1 vote
0 answers
43 views

Distributionally Robust Stochastic Programming - Help with derivation

I've been working through this book on robust optimization of electric energy systems, and in particular chapter 4 on distributionally robust optimization. In following the derivation of section 4.2.1....
asfiwefewrno's user avatar
1 vote
2 answers
106 views

Understanding the L-shaped-method and the different variants of it

I am currently trying to understand the integer L-shaped-method/stochastic version of Benders Decomposition because I have practical problem MIP that is stochastic and thus has very good decomposition ...
Arctic_Skill's user avatar
1 vote
1 answer
67 views

How do I check convergence in stochastic Benders?

So in the deterministic version of Benders, the main process works like this: I initialize my x-vector (Integer variables from the master problem) and solve the dual subproblem (SP). I add an ...
Arctic_Skill's user avatar
1 vote
1 answer
78 views

Recommendations to understand stochastic version of Benders?

I successfully understood and implemented a Benders algorithm for the deterministic version of the problem I am studying. However, I have some issues now diving into the stochastic model. I have the ...
Arctic_Skill's user avatar
0 votes
2 answers
91 views

Tips for implementing Benders Decomposition in C++?

currently I am working on implementing Benders Decomposition for a large-scale stochastic MIP in C++ using the CPLEX Solver. I've been spending the last couple of months learning the programming ...
Arctic_Skill's user avatar
0 votes
0 answers
68 views

Simplex algorithm for stochastic constraints?

The OR-Notes by J E Beasley states: Hence the problem: minimise 5x+6y subject to: Prob(a1x + a2y >= 3) >= 1-alpha x,y >= 0 ...
jbuddy_13's user avatar
  • 501
0 votes
1 answer
46 views

Deriving a lower bound for a two-stage stochastic problem

Assume an inventory stochastic optimization problem in the following form: $$\min\limits_{x\in X} c^\top x + \mathbb{E}_{\mathbb{\xi}}[\mathcal{Q}(x, \xi)]$$ Demand is the uncertain parameter, and is ...
Mostafa's user avatar
  • 2,086
4 votes
1 answer
306 views

Is Benders decomposition and the L-shaped method the same algorithm?

I've been studying the Benders decomposition method to solve stochastic integer problems. I've also stumbled across papers using a so called L-shaped-algorithm which also divides into master problem ...
Arctic_Skill's user avatar
0 votes
0 answers
73 views

Resource allocation problem - RL or stochastic optimization?

I am currently working on a resource allocation problem and I am uncertain about which field of stochastic optimization and reinforcement learning encompasses this particular problem. The objective is ...
liam urate's user avatar
0 votes
0 answers
57 views

Best strategy for the secretary problem with known distribution

The optimal strategy for the well known secretary problem with $n$ candidates is to reject the first $\lceil \frac{n}{e} \rceil-1$ candidates, and then select the first subsequent applicant that is ...
Kuifje's user avatar
  • 12.9k
0 votes
0 answers
60 views

Loan Allocation Problem

I need help with the following use case: Context : Let's say there is a fintech "F", that helps with aggregating personal loans. Now, "F" can pool in customers who need a personal ...
Jai s's user avatar
  • 1
0 votes
1 answer
79 views

Theorem proving Stochastic Optimization for Unit Commitment always better than deterministic solution

I'm trying to recall a theorem that I was taught in grad school, but can't remember the name of the theorem. We were learning about different methods to solve unit committment and economic dispatch ...
John's user avatar
  • 9
3 votes
2 answers
164 views

How to find the maximizing number of expected delivered units of a probabilistic minimum cost flow problem?

I am a Bitcoin / Lightning Network open source developer and researcher and new here but very active on the sister site. In the context of my research I discovered the field of operations research ...
Rene Pickhardt's user avatar
2 votes
3 answers
430 views

Robust Optimization in Gurobi

I have a research problem where my Mixed Integer Linear Program has data that follow probability distributions. I am approaching this by creating some m instances through realizations of these random ...
arvind rathore's user avatar
2 votes
1 answer
165 views

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

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=\...
falamiw's user avatar
  • 157
1 vote
1 answer
74 views

Can stochastic dual dynamic programming algorithm (or any variant of it) handle multi-stage optimization problems with here-and-now uncertainty nodes?

Stochastic dual dynamic programming (SDDP) algorithm solves stage-wise optimization problem through sampling scenarios. In this regard, it is obvious to see that wait-and-see uncertainty can be easily ...
Engr. Moiz Ahmad's user avatar
1 vote
1 answer
64 views

Problem to construct constaints in SAA method

Pop-Donuts located in Los Angeles of California makes two products, donuts and cakes. Pop-Donuts has bottlenecks in its capital used to purchase flour that is required in making both donuts and cakes, ...
falamiw's user avatar
  • 157
5 votes
1 answer
165 views

Two-Stage Stochastic Optimization: How to deal with Infeasible scenario while calculating EEV (Expected result of using the EV solution)

I am trying to solve some of the stochastic optimization proposed problems for an Optimization course I joined. One of the exercices asks to solve the Expected Value problem. I already made it. Next ...
Alfonso_MA's user avatar
5 votes
1 answer
774 views

Understanding L-shaped algorithm in a two-stage stochastic problem

I am facing a problem understanding the L-shaped algorithm in a two-stage stochastic problem. $$\operatorname{Min} z=100 x_1+150 x_2+E_{\xi}\left(q_1 y_1+q_2 y_2\right)$$ subject to $$ \begin{aligned}...
falamiw's user avatar
  • 157
2 votes
3 answers
317 views

Create constraint only for a recourse problem in stochastic linear programming

Question1: Northam Airlines is trying to decide how to partition a new plane for its Chicago– Detroit route. The plane can seat $200$ economy class, passengers. A section can be partitioned off for ...
falamiw's user avatar
  • 157
3 votes
0 answers
47 views

Control variables and cofounding effects in stochastic programming/,model predictive control/reinforcement learning

How can we be sure that confounding variables/control variables don’t pickup the effect our decisions w.r.t decision variables had on the actual control variable? Since the term control variable ...
stewardbranson's user avatar
3 votes
1 answer
117 views

Decision dependent scenarios in Stochastic Programming

I am new to the field of stochastic programming and saw that the general formulation of a two-stage stochastic programming problem is given by: $$\min_{x\in X}\{ g(x)= f(x) + E_{\xi}[Q(x,\xi)]\}$$ ...
PeterD's user avatar
  • 1,461
3 votes
2 answers
432 views

How do I solve a probability based knapsack problem?

I am looking to maximize my probability of reaching a given target value, by creating multiple groups of 6 items with different means and variances that stay within a weight limit. This is an example ...
will's user avatar
  • 31
1 vote
0 answers
38 views

Multicollinearity w.r.t decisions in optimal control/reinforcement learning learning/resource allocation problem

Consider the following optimization/control problem: We aim to maximize the cumulative reward $R$ during the horizon $H$ by every day allocating a portion of total budget $B$ to our two different ...
chrisrichardsson's user avatar
1 vote
0 answers
71 views

Multi-Stage Stochastic Decomposition

I have a multi-stage model with both binary and continuous first-stage investment variables and continuous operational next-stage variables: $$ \sum_{s} \rho_{s} \left[ x_{s} + y_{s} + \sum_{t}(y^{op}...
Ahmed's user avatar
  • 103
2 votes
1 answer
112 views

multi stage stochastic programming algorithm

I have a multi-stage stochastic programming model. I have 3 groups of variables: the first group takes values at the beginning of the planning horizon before the first realization and does not change ...
mahgol's user avatar
  • 21
2 votes
0 answers
66 views

Reformulate the deterministic equivalent model as an Expected Value problem

Given an optimization problem as follows: $$ \begin{array}{cc} \operatorname{Max} Z=3 x_{1}+9 x_{2}-2 y_{1}-4 y_{2} \\ \text { subject to, } y_{1}+y_{2}=15 \\ 5 x_{1}+2 x_{2} \leq 10 \\ x_{1}, x_{2}, ...
falamiw's user avatar
  • 157
2 votes
1 answer
214 views

Resource which explain different stochastic method with some intuition

Hope my question fit this community. I have taken Stochastic Optimization course (2 credits). The course content are: Deterministic VS Stochastic Linear Program Two-Stage Recourse Problem Multi-Stage ...
falamiw's user avatar
  • 157
0 votes
1 answer
334 views

Can Expected value of perfect information be zero?

I tried to find the Expected Value of Perfect Information (EVPI) and the Value of the Stochastic Solution (VSS) of the following problem. Consider a farmer who specializes in raising wheat, corn, and ...
falamiw's user avatar
  • 157
5 votes
1 answer
112 views

Use of variance in job ordering

For a job-shop-like problem I have some constraints of this form: $$ c_i \geq s_i + d_{iom} z_{iom} $$ $z_{iom}$ is a binary enabler, $d_{iom}$ is the delay on job $i$ for operation $o$ done by ...
Brannon's user avatar
  • 892
4 votes
0 answers
155 views

Stochastic optimization for inventory management

The deterministic problem is to minimize operational cost subject to constraints in demand, supply and capacity. The ordering policy is periodic review, order-up-to. The stochastic version of the ...
anerjee's user avatar
  • 119
8 votes
3 answers
637 views

Difference between "Online Optimization" and "Stochastic Optimization"/"Robust Optimization"?

I just came across the notion of Online optimization (I got a look on Wikipedia page and some other webpages), but it was not enough for me and I am looking for a more elaborated comparison, namely in ...
Betty's user avatar
  • 534
6 votes
0 answers
222 views

Airline revenue management re-solving problem

I am considering a bid prices (shadow price of the capacity constraint) problem (from Chen, L. and Homem-de Mello, T. (2009)., page 14) where the acceptable classes for booking requests for ...
SimonCello94's user avatar
4 votes
1 answer
239 views

Can we simplify (perhaps linearize) this constraint?

We are dealing with a stochastic model and one of the constraints is \begin{align} y_j=\frac{\sum_{i \in I}\sum_{k \in K}\mathbb{E}\left[X_{ik}^2\right]x^k_{ij}}{\sum_{i \in I} \sum_{k \in K} \mathbb{...
user avatar
5 votes
1 answer
385 views

Optimality in L Shaped or Bender Decomposition

I was working on solving a two-stage stochastic problem using L Shaped method (Benders Decomposition). I have discussed the model here: Stochastic Facility Location Model. Do the single-cut/ multi-cut ...
mars's user avatar
  • 619
5 votes
0 answers
145 views

Chance constrained optimization - interpretation

Suppose that we have a stochastic vector $\psi$ and $S$ realisations of $\psi$ given by $\psi_1,\dots,\psi_S$ with equal probability of occurrence. In addition, we have constraints of the form \begin{...
Djames's user avatar
  • 1,133
2 votes
0 answers
87 views

Two-stage stochastic with non-linear recourse

I am working on a two-stage facility location problem as I described in this question. I am solving it with the L-shaped method (Benders decomposition). The cost value between each $(i,j)$ is a ...
mars's user avatar
  • 619
3 votes
1 answer
242 views

How to solve Stochastic Dynamic Program with huge state space?

I am modelling a stochastic dynamic program but because I need to store all information related to former sales, the state of the dynamic program increases and potentially it can growth so much which ...
Amin's user avatar
  • 2,150
3 votes
1 answer
285 views

Stochastic Facility Location Model

I am solving a stochastic facility location model using Benders decomposition (L-shaped algorithm). In each scenario, I want to allocate demands from origin to a fixed number of closest open ...
mars's user avatar
  • 619
6 votes
0 answers
92 views

Sample Average Approximation vs. Numerical Integration

In the sense of the calculation of the expected value of objective functions, we have two choices to evaluate the value; 1. Sample Average Approximation (SAA): $$ \frac{1}{N}\sum_{i=1}^N f(x,\xi^i). $$...
Keith's user avatar
  • 155
3 votes
0 answers
77 views

Derivative of sup(max) functions in distributionally robust optimization

In the distributionally robust optimization problem \begin{aligned} \min_{x\in X}\sup_{P\in\mathfrak{P}}\mathbb{E}_P[f(x,\xi)], \end{aligned} where $f:\mathbb{R}^n\to\mathbb{R}$ and $P$ is a ...
Keith's user avatar
  • 155
2 votes
1 answer
156 views

Numerical problem regarding to classical benders cut of large scale problem

I am trying to implement benders decomposition for a simple two stage unit commitment problem. I implemented the classic Benders decomposition to add feasible cut and optimal cut to relax master ...
Lee Adolin's user avatar
4 votes
0 answers
54 views

How to find range of values for the first-stage decisions resulting in the same cuts in two-stage stochastic programming?

Suppose we have a two-stage stochastic program as follows: \begin{equation} \begin{split} \min \ & c^Tx + \mathbb{E}_\xi[Q(x,\xi)] \\ & \text{where}\\ &Q(x,\xi)=\min q(\xi)^Ty\\ &Tx+...
Amin's user avatar
  • 2,150
2 votes
0 answers
205 views

What is the intuition behind Progressive hedging algorithm?

I am reading some papers about PHA to solve multi-stage stochastic programming, but I think it is not still clear to me. This is my understanding and I would be thankful to know if it is correct or ...
Amin's user avatar
  • 2,150
1 vote
0 answers
63 views

Scenario Tree Construction in Multi-Stage Stochastic Programming

I gonna use the approach used in this document. Suppose there are $T$ stages and uncertain parameter is $\xi_{t}, \quad t \in \{1,2,\dots,T\}$. In this algorithm, it is required to calculate the ...
Amin's user avatar
  • 2,150