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
2
votes
1answer
69 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 ...
3
votes
0answers
41 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
votes
0answers
70 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 ...
1
vote
0answers
33 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 ...
1
vote
1answer
143 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
votes
0answers
80 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} =...
0
votes
1answer
141 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 \...
-3
votes
1answer
99 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 $...
1
vote
1answer
97 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 ...
9
votes
1answer
383 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
votes
2answers
213 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\\ &...
2
votes
2answers
96 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 ...
4
votes
1answer
93 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?
3
votes
1answer
147 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
1answer
108 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{...
3
votes
1answer
88 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 ...
19
votes
2answers
1k 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 ...
2
votes
0answers
46 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 ...
1
vote
0answers
87 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&...
14
votes
1answer
209 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 ...
10
votes
1answer
162 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 ...
11
votes
1answer
340 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 ...
10
votes
0answers
160 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 ...
10
votes
2answers
173 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 ...
7
votes
1answer
316 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 ...
11
votes
1answer
183 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 ...
16
votes
4answers
900 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 ...
10
votes
2answers
1k 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?
10
votes
2answers
146 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$ ...
15
votes
3answers
336 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 ...
25
votes
4answers
689 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 ...
12
votes
1answer
220 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 '...