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
4 votes
0 answers
83 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 ...
user avatar
  • 109
8 votes
3 answers
240 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 ...
user avatar
  • 544
6 votes
0 answers
208 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 ...
user avatar
4 votes
1 answer
214 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
  • 406
5 votes
1 answer
150 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 ...
user avatar
  • 429
5 votes
0 answers
106 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{...
user avatar
  • 1,011
2 votes
0 answers
52 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 ...
user avatar
  • 429
3 votes
1 answer
173 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 ...
user avatar
  • 2,105
3 votes
1 answer
142 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 ...
user avatar
  • 429
6 votes
0 answers
75 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). $$...
user avatar
  • 133
3 votes
0 answers
65 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 ...
user avatar
  • 133
2 votes
1 answer
107 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 ...
user avatar
3 votes
0 answers
47 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+...
user avatar
  • 2,105
2 votes
0 answers
80 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 ...
user avatar
  • 2,105
1 vote
0 answers
41 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 ...
user avatar
  • 2,105
1 vote
1 answer
154 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,...
user avatar
  • 2,034
2 votes
0 answers
227 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} =...
user avatar
  • 2,105
-1 votes
1 answer
186 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 \...
user avatar
  • 2,105
-3 votes
1 answer
103 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 $...
user avatar
1 vote
1 answer
106 views

Do I need to use a stochastic optimisation approach

I have used deterministic optimisation approaches before but never ventured into stochastic optimisation. In my problem there are a number of decision variables that the optimiser must choose from in ...
user avatar
9 votes
1 answer
416 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 ...
user avatar
  • 3,467
3 votes
2 answers
300 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\\ &...
user avatar
  • 151
2 votes
2 answers
101 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 ...
user avatar
  • 284
4 votes
1 answer
99 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?
user avatar
3 votes
1 answer
236 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 ...
user avatar
2 votes
1 answer
125 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{...
user avatar
  • 151
3 votes
1 answer
113 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 ...
user avatar
  • 544
21 votes
3 answers
2k 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 ...
user avatar
  • 1,546
2 votes
0 answers
49 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 ...
user avatar
1 vote
0 answers
98 views

How do I find the extreme rays and points for a stochastic programming problem

I have the following 2 stage Stochastic Programming program: \begin{align}\min_x& \quad x+\sum_{s=1}^{3}p_sQ_s(x)\\\text{s.t.}&\quad x\in\Bbb R\\&\quad Q_s(x)=\min\left[\begin{pmatrix}1&...
user avatar
  • 149
14 votes
1 answer
259 views

Sources to learn about Sample Average Approximation for practitioners

I want to start learning Stochastic Programming, beginning with SAA (Sample Average Approximation) and keeping a practitioner's perspective in mind, i.e. I would like my sources to collectively cover ...
user avatar
  • 1,577
10 votes
1 answer
244 views

Scenario Generation and Reduction in Stochastic Optimization

I have to generate scenarios for a stochastic optimization program. I want to reduce this number of scenarios but the assignment of a probability to each scenario is my problem. How can I assign a ...
user avatar
11 votes
1 answer
348 views

Why is the sample variance of a Sample Average Approximation calculated in this way?

I am going through the great tutorial on Stochastic Programming by Shapiro and Philpott. When talking about Monte Carlo techniques, I get confused by the way they calculate the sample variance (page ...
user avatar
  • 1,428
9 votes
0 answers
176 views

Solving large-scale stochastic mixed integer program

What are some methods or algorithms for solving a large-scale stochastic mixed-integer optimization problem that runs on an hourly dataset for a year? Do we employ some kind of decomposition? (the ...
user avatar
  • 793
10 votes
2 answers
182 views

Optimal set order to maximize stochastic reward

You have a ticket allowing you to visit up to $n$ of $M$ carnival booths offering games of chance. At each booth you have probability $p_{i}$ of winning a reward with average value $r_{i}$. Each booth ...
user avatar
  • 103
7 votes
1 answer
756 views

Alternative definition for the value of stochastic solution

I have a two-stage stochastic programming problem in which the expected-value solution results in a quite different first-stage solution than the recourse problem. Although the value of VSS (defined ...
user avatar
  • 2,110
11 votes
1 answer
205 views

Difficulties with Finding a Proper Penalty Value for the Progressive Hedging Algorithm

Recently, I've been working on some two-stage stochastic programming problems. Due to the presence of integer second-stage variables in the model, I've preferred to use the Progressive Hedging ...
user avatar
  • 2,410
16 votes
4 answers
992 views

Modeling the uncertainty of the input parameters

There are many approaches to deal with the uncertainty such as stochastic programming, robust optimization and fuzzy programming. Finding a suitable approach that is applicable in the real situations ...
user avatar
  • 603
10 votes
2 answers
2k views

Infinite horizon versus finite horizon MDP

When can we approximate a finite horizon MDP with infinite horizon? Can we use infinite horizon stochastic shortest path problem on a directed acyclic graph?
user avatar
10 votes
2 answers
159 views

Advantages/disadvantages of different representations of non-anticipativity constraints

When reading various papers about two-stage (or multi-stage) stochastic programs with recourse, a common representation of the non-anticipativity constraints is: $$ \sum_{i}H_ix_i=h, $$ where $i$ ...
user avatar
  • 1,957
16 votes
3 answers
397 views

Benchmark problems for scenario-based stochastic optimization

$\newcommand{\E}{\mathbb{E}}$I am working on numerical algorithms for solving convex large-scale multistage scenario-based problems and I am looking for some standard benchmarks problems. I have so ...
user avatar
25 votes
4 answers
869 views

Stochastic programming MIP solvers

I am aware that Benders Decomposition is readily available in CPLEX and in SCIP; but are there any (free) solvers that provide off the shelf stochastic programming MIP algorithms or a nice to work ...
user avatar
12 votes
1 answer
277 views

2 stage stochastic programming to approximate many stage problems

There are many naturally multi-stage (i.e., more than two) stochastic programming problems that are approximated by a two-stage stochastic programming model due to the complete intractability of the '...
user avatar