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
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 ...
Jai s's user avatar
  • 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 ...
John's user avatar
  • 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 ...
Rene Pickhardt's user avatar
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 ...
arvind rathore's user avatar
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=\...
falamiw's user avatar
  • 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 ...
Engr. Moiz Ahmad's user avatar
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, ...
falamiw's user avatar
  • 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 ...
Alfonso_MA's user avatar
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}...
falamiw's user avatar
  • 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 ...
falamiw's user avatar
  • 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 ...
stewardbranson's user avatar
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)]\}$$ ...
PeterD's user avatar
  • 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 &...
chrisrichardsson's user avatar
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 ...
will's user avatar
  • 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 ...
chrisrichardsson's user avatar
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}...
Ahmed's user avatar
  • 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 ...
mahgol's user avatar
  • 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}, ...
falamiw's user avatar
  • 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 ...
falamiw's user avatar
  • 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 ...
falamiw's user avatar
  • 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 ...
Brannon's user avatar
  • 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 ...
anerjee's user avatar
  • 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 ...
Betty's user avatar
  • 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 ...
SimonCello94's user avatar
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{...
user avatar
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 ...
mars's user avatar
  • 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{...
Djames's user avatar
  • 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 ...
mars's user avatar
  • 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 ...
Amin's user avatar
  • 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 ...
mars's user avatar
  • 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). $$...
Keith's user avatar
  • 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 ...
Keith's user avatar
  • 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 ...
Lee Adolin's user avatar
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+...
Amin's user avatar
  • 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 ...
Amin's user avatar
  • 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 ...
Amin's user avatar
  • 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,...
Mostafa's user avatar
  • 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} =...
Amin's user avatar
  • 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 \...
Amin's user avatar
  • 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 $...
DSPinfinity's user avatar
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 ...
granddejeuner's user avatar
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 ...
user3680510's user avatar
  • 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\\ &...
Sam's user avatar
  • 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 ...
SAH's user avatar
  • 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?
minsoo kim's user avatar
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 ...
Moving in rhythm with OR's user avatar
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{...
Sam's user avatar
  • 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 ...
Betty's user avatar
  • 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 ...
PeterBe's user avatar
  • 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 ...
Bartek Andrzejczak's user avatar