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.
64
questions
0
votes
0
answers
48
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 ...
- 1
0
votes
1
answer
65
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 ...
- 9
3
votes
2
answers
148
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 ...
- 131
2
votes
3
answers
274
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 ...
2
votes
1
answer
120
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=\...
- 157
1
vote
1
answer
54
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 ...
1
vote
1
answer
62
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, ...
- 157
5
votes
1
answer
121
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 ...
- 151
5
votes
1
answer
352
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}...
- 157
2
votes
3
answers
300
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 ...
- 157
3
votes
0
answers
46
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 ...
3
votes
1
answer
87
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)]\}$$
...
- 1,282
0
votes
0
answers
42
views
How do i model this problem as an stochastic optimization problem
Consider the following optimization problem:
$$\begin{align}
\max_{inv1t, inv2t} \sum_{t=t}^{t=t+H} r(inv1t, inv2t, & independent \; variables) \\
\mbox{s.t.} \sum_{t=t}^{t=t+H} inv1t + inv2t &...
3
votes
2
answers
349
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 ...
- 31
1
vote
0
answers
36
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 ...
1
vote
0
answers
66
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}...
- 103
2
votes
1
answer
92
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 ...
- 21
2
votes
0
answers
54
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}, ...
- 157
2
votes
1
answer
149
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 ...
- 157
0
votes
1
answer
221
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 ...
- 157
5
votes
1
answer
109
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 ...
- 762
4
votes
0
answers
139
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 ...
- 119
8
votes
3
answers
520
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 ...
- 534
6
votes
0
answers
218
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 ...
- 165
4
votes
1
answer
228
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{...
user9659
5
votes
1
answer
325
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 ...
- 619
5
votes
0
answers
131
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{...
- 1,113
2
votes
0
answers
78
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 ...
- 619
3
votes
1
answer
206
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 ...
- 2,140
3
votes
1
answer
252
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 ...
- 619
6
votes
0
answers
86
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).
$$...
- 155
3
votes
0
answers
75
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 ...
- 155
2
votes
1
answer
145
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 ...
- 55
4
votes
0
answers
53
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+...
- 2,140
2
votes
0
answers
123
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 ...
- 2,140
1
vote
0
answers
56
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 ...
- 2,140
1
vote
1
answer
160
views
Generating numbers that should add up to a fixed value while they follow a known distribution
Suppose a perishable item that is associated with a shelf life $m\in \mathcal{M} = \{1,\dots,M\}$. We have a periodic review system with stock level $S$, i.e., based on the inventory level of the item,...
- 2,074
2
votes
0
answers
536
views
How to write nonanticipativity constraints?
In Multi-stage stochastic programming, we write the constraints that for scenarios $s$ and $s^{\prime}$ which have the same trajectory up to time $t$, should take the same value. That is,
$$
x_{t,s} =...
- 2,140
-1
votes
1
answer
272
views
How to prove that the second-stage value function of a Stochastic Program is convex?
I am wondering to know how it is possible to prove that the second-stage value function in a two-stage stochastic program is convex on $x$ and $\xi$? A two-stage stochastic program can be defined as
\...
- 2,140
-3
votes
1
answer
106
views
is this a mistake or not in this tutorial?
Please consider
https://stoprog.org/what-stochastic-programming
and look at "A SIMPLE INTEGER RECOURSE MODEL" at
"Stochastic Integer Programming" section.
Should not $b_i$ be $...
- 409
1
vote
1
answer
145
views
Do I need to use a stochastic optimization approach
I have used deterministic optimization approaches before but never ventured into stochastic optimization.
In my problem there are a number of decision variables that the optimizer must choose from in ...
11
votes
1
answer
490
views
How is optimization under uncertainty done in real world applications?
In this post What is robust optimization? there is a nice introduction to robust optimization.
There are many concept for uncertainty in optimization problems like
robust optimization
stochastic ...
- 3,557
3
votes
2
answers
511
views
Decomposition methods for two-stage stochastic program with integer variables
In a stochastic programming problem, I have binary variables in the second stage. As an example, consider that the optimization problem is given by:
\begin{align}
&\text{minimize} &\gamma\\
&...
- 151
2
votes
2
answers
105
views
How to generate correlated samples?
The variation of the average price of a product over a longer period is generally lower than a shorter period. I am interested to capture both uncertainties as to the input of the stochastic ...
- 294
4
votes
1
answer
102
views
How to evaluate the performance of scenario generation algorithms?
I would like to compare the performance of various scenario generation algorithms.
What are the metrics for comparing the performance of these algorithms?
- 43
3
votes
1
answer
461
views
Accessible introduction to L-shaped methods/Benders decomposition
I am looking for papers or other resources that provide an accessible introduction to L-shaped methods/Benders decomposition for solving stochastic linear programming-ideally something focused more on ...
2
votes
1
answer
151
views
Scenario based approach to value-at-risk optimization using mixed-integer programming
For a discrete set of scenarios, minimising value at risk can be formulated as a mixed integer linear programming problem. If each scenario has equal probability then this can be written as
\begin{...
- 151
3
votes
1
answer
144
views
Robust/Stochastic optimization deployed in real-world systems/applications
In an applied project we are working on currently, we want to use robust or stochastic programming in order to enhance the performance of the systems (by reference to certain metrics). As you may ...
- 534
23
votes
3
answers
4k
views
Difference between stochastic optimization and robust optimization
I would like to know whether stochastic optimization and robust optimization are the same and if not, what is the main difference between them. I did an Internet search and I found the following ...
- 1,668
2
votes
0
answers
57
views
Decision-making algorithm for dynamic load balancing
I'm researching a subject of balancing the load between two black-box systems (with some twists). I thought that I could record latest response time log from each of those systems and process such a ...
