# Questions tagged [dynamic-programming]

For questions about dynamic programming, a mathematical optimization technique where the optimal solution to the problem is found by breaking it down to simpler sub-problems and solved recursively.

44 questions
Filter by
Sorted by
Tagged with
1 vote
48 views

### Subsequence Decision Optimization with Optional and Stopping Times

I have a problem that I haven't encountered before and would like to know if there is any literature on the problem - or maybe you can help me simplify my problem if you think I'm doing something ...
• 11
1 vote
95 views

### How is this function piece-wise linear?

I encountered this lemma in a research paper related to End-to-End inventory management model. Please note that $d_{[t_1,t_2]} = \sum_{t=t_1}^{t_2} d_i$, where $d_t$ denotes demand at time instance t. ...
141 views

### Can the following problem be solved recursively?

Consider the following problem \begin{aligned} \min_{x,y,z} \quad & \sum_{i=0}^1 \sum_{j=0}^1 \sum_{k=0}^1 a_{ijk} \cdot f_{ijk}(x,y,z), \\ \textrm{s.t.} \quad &...
• 639
59 views

### Successive approximation in negative dynamic programming

I am studying Stochastic Dynamic Programming using Sheldon Ross's book, "Introduction to Stochastic Dynamic Programming." In the book, Ross defines a dynamic programming algorithm to ...
1 vote
129 views

### Can dynamic programming find globally optimal solutions for scheduling problems

I want to know if dynamic programming can generally find globaly optimal solutions for scheduling problems? I think this might be difficult as dynamic makes one at a time decisions without calculating ...
• 1,682
58 views

### Can I use continuous probability distributions when creating an SDDP.jl model?

I am using SDDP.jl for my research project and want to use continuous distribution, can I do so?
45 views

### How can I write the output stream of SDDP.jl into an excel file?

I am using SDDP.jl for my research project in which I am developing a state-of-the-art actor critic algorithm which I am going to benchmark with SDDP but for it I need to plot graphs which require ...
1 vote
130 views

### Matching algorithm in an order batching problem

There is an order batching problem. Given a set of orders, they need to be split into several batches, with a maximum order number of M per batch. Each order needs to be picked from multiple storage ...
• 115
1 vote
157 views

### Is stochastic dual dynamic programming (SDDP) a deterministic solution algorithm or does it have a stochastic component to it?

I am currently working on a paper in which I am statistically comparing dynamic optimization algorithms like SDDP, Actor-Critics etc. In this regard, should I be running SDDP algorithm for my ...
1 vote
207 views

### Wagner's-Whitin Algorithm

I'm having trouble in solving this problem dealing with the Wagner's-Whitin Algorithm, because the holding and ordering costs are not given, we only have the optimal costs from the beginning to each ...
1 vote
81 views

### Solving stochastic dynamic problem by space state MATLAB program

I have a maximization problem as shown in the picture below. The output has a common shock z that follows a two-state Markov chain with a transition matrix Π. Does anyone know how I would go about ...
• 11
1 vote
114 views

### Single item unconstrained lot-sizing with multiple suppliers and minimum order quantities

Variation of the traditional lot-sizing problem - with some additional complexities: multiple suppliers (S1, S2, S3), with different procurement lead-time Suppliers have to be allocated based on a ...
• 119
107 views

### Bellman Equation for nonlinear model

Consider the following model: \begin{align*} max \quad Z &= 19x_1 - 3x_1^2 + 5x_2^2 - x_2^4 + 4x_3 \\ & s.t. \quad x_1 + 3x_2 + 3x_3 \leq 7 \\ & \quad \quad \quad x_1,x_2,x_3 \geq 0 \end{...
100 views

### Optimal spending of cash problem

I have often wondered whether there is an optimal way to spend cash denominations. For example: Suppose that Bob needs to pay Jill \$5, Jane \$10, Billy \$3.50 and John \$45.75. Furthermore suppose ...
50 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 ...
193 views

### How to model history-dependent dynamic program?

Suppose there is a dynamic program that the state of the problem grows over time (more info is added to the state of the problem over time) and at each time, we need all historical data, full history, ...
• 2,160
242 views

### Dynamic program for knapsack in $O(W)$ space?

A familiar dynamic programming algorithm for the binary knapsack problem  \begin{align} \text{maximize}\quad & v \cdot x \\ \text{subject to} \quad & w \cdot x \leq W \\ \quad&x_i \text{ ...
• 584
32 views

### How to establish the optimal value functions and optimal control policy for a controlled random walk problem?

Question: How to establish an explicit characterization of both the optimal value functions and the optimal control policy for a controlled random walk? Background: Assume our system is a perfectly-...
• 141
77 views

### Linear programming approach to dynamic programming - an initial pair of state-decisions

I aim to solve the following Bellman equation: v(\vec{s}) = \min_{\vec{x} \in \Xi_{\vec{s}}} \big\{c(\vec{s}, \vec{x}) + \lambda \times \sum_{\vec{s}^{'}\in S} p(\vec{s}^{'} | \...
• 615
609 views

### What kind of data structure should be used to store labels when implementing a labeling algorithm?

The shortest path problem with resource constraints is a common subproblem when doing column generation. It is often solved with a labeling algorithm. The procedure is very well explained here and ...
• 668
2k views

### Efficiency of Forward vs. Backward Recursion in Dynamic Programming

I have a question that has been bothering me for a while: In our OR-introduction course, we introduce the concept of Dynamic Programming via backward recursion: Working backwards from a final state (...
• 121
1 vote
144 views

### Simple inventory control with stochastic demand

There is a factory that produces one unit of stock uniformly so that $q$ units of stock are produced during a day. The warehouse near a factory has the maximal capacity of $q$ items, i.e. a daily ...
• 11
153 views

### Why are these constraint equations equal?

If we consider the dynamic lot sizing problem with: $d_i$ as the demand per period $i$ and denote $\sum_{i=1}^t d_i$ being the total demand up to period $t$, where $t$ can take values $1, \dots, T$ ...
• 1,053
1 vote
66 views

• 103