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.
85 questions
1
vote
1
answer
53
views
Interpreting simulation results
I've coded a tiny example of how to apply simulation to the TSP, and I am having some problems interpreting the obtained results. So, first, I will describe the proposed procedure, and then point out ...
- 1,282
0
votes
2
answers
77
views
Distribution Evaluation for SAA
I understand that Sample Average Approximation (SAA) in optimization is considered as an approximation model using the law of large numbers (such as in this link). Therefore the approximation of the ...
- 35
1
vote
0
answers
46
views
Using the Alternative Cut Generation Problem in Benders, why do I get different results?
I am using Benders' Decomposition to solve a stochastic MIP.
To improve cut selection, I implemented the Alternative Cut Generation Problem as proposed by Fischetti et al. (2010).
I will summarize the ...
- 327
0
votes
0
answers
32
views
Understanding different norms in the p-Wasserstein distance
The generalized p-Wasserstein distance, for $p\geq 1$, is given by
$$d_W(Q_1,Q_2):=inf \left\{\int_{\Xi_2}||\xi_1-\xi_2||^p \Pi(d\xi_1,d\xi_2)\right\}$$
where $\Pi$ is the joint distribution of $\xi_1$...
- 31
0
votes
1
answer
48
views
How can I calculate the UB if I'm using Fischetti's Alternative Cut Generation for Benders'?
Assuming I have a stochastic MIP that I want to minimize using Benders' Decomposition.
With the objective of the MP being:
$$
Minimize \; cx + \frac{1}{\lvert S \rvert} \sum_{s \in S} \theta_s
$$
...
- 327
1
vote
0
answers
22
views
Building a CapEx portfolio using mathematical optimization
Let's say you have a set of potential capital projects $C$, each defined by an up-front investment $c_i$ and random payoff (say, NPV) $P_i(\omega)$, where $\omega \in \Omega$ is a point in a sample ...
- 111
2
votes
1
answer
73
views
How to deal with performance bottlenecks in Stochastic Vehicle Routing Problem with Benders' decomposition?
I've been working on solving a stochastic vehicle routing problem using Benders' decomposition with CPLEX in C++. Initially, my implementation struggled with larger instances, but I've made ...
- 327
0
votes
0
answers
23
views
Supremum of a probabilistic function with ambiguity distribution set using Wasserstein metric
There is a proof of how to derive distributionally robust chance constraints with ellipsoid bound.
$$\inf_{\mathbb{P}\in\mathcal{D}^{WD}} \mathbb{P}\{\|\mathbf{A\zeta-b}\|_2 \leq 1\} \geq 1-\epsilon$$
...
- 105
0
votes
0
answers
57
views
How to initialize a parameter (belonging to the first stage model) in a two stage model, taking its value from second stage model?
I am working on a two stage approach in order to reduce the complexity of a scheduling model which is an NP-hard problem. I have to implement a while loop in order to repeat solving the models in case ...
- 131
2
votes
1
answer
159
views
How to pass the values of a variable of the first model to a parameter of the second model?
I am working on a scheduling problem which is NP-hard problem. Therefore, I decided to implement two-stage strategy to speed up the solution process. I need to pass the values of a variable from the ...
- 131
0
votes
0
answers
50
views
monte carlo for a selection problem
What type of Monte Carlo simulation is suitable for solving this problem? Also, how can we select results after simulation to guarantee feasibility?
1
vote
0
answers
46
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,...
- 163
4
votes
1
answer
214
views
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 ...
- 327
1
vote
1
answer
128
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 ...
- 21
1
vote
0
answers
59
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....
- 76
1
vote
2
answers
833
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 ...
- 327
1
vote
1
answer
134
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 ...
- 327
1
vote
1
answer
92
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 ...
- 327
0
votes
2
answers
192
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 ...
- 327
0
votes
0
answers
74
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
...
- 559
0
votes
2
answers
83
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 ...
- 2,114
4
votes
1
answer
500
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 ...
- 327
0
votes
0
answers
95
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 ...
0
votes
1
answer
131
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
176
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
784
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
276
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
120
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
66
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
252
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
2k
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
387
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
51
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
157
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,736
3
votes
2
answers
561
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
40
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
75
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}...
- 113
2
votes
1
answer
182
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
90
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
454
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
546
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
115
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 ...
- 970
4
votes
0
answers
167
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
875
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 ...
- 544
6
votes
0
answers
227
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
253
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
423
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 ...
- 629
5
votes
0
answers
157
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,143
2
votes
0
answers
111
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 ...
- 629
3
votes
1
answer
328
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,160