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.

Filter by
Sorted by
Tagged with
20 votes
3 answers
5k views

Solving a knapsack problem with a lot of items

I am wondering what are the fastest ways(faster than classical dynamic programming) to solve the knapsack problem (to optimality) with $n$ items when $n$ is nearly equal to $10000$ ? Apart from ...
Joffrey L.'s user avatar
14 votes
2 answers
242 views

Suggestion of some courses in sequential decision making

I am studying about sequential decision making and I am willing to know if there is any course which is recorded and is publically available covering topics in dynamic programming (DP), reinforcement ...
Amin's user avatar
  • 2,150
10 votes
2 answers
191 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 ...
sedge's user avatar
  • 103
8 votes
1 answer
583 views

Dynamic programming example

I am going to buy a family car at the beginning of the New Year. I am going to stay in the UK for the next 4 years. I am considering the possibility of being a customer of company A which sells ...
Slim Shady's user avatar
7 votes
2 answers
3k views

The general meaning of "constraint relaxation" in the context of the Shortest Path Problem

I've read that in the context of the Shortest Path Problem, the use of the term "relaxation" ("relaxing edges") [...][the use of the term "relaxation"] is historical. The outcome of a relaxation ...
Alexey's user avatar
  • 169
7 votes
1 answer
1k 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 (...
derhendrik's user avatar
6 votes
2 answers
536 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 ...
gmn's user avatar
  • 632
6 votes
1 answer
372 views

Multi-period linear dynamic programming with differing in-period dependencies and changes

I’m not sure if I’m wording this right but in a nutshell, my problem is: I’m modelling potential actions a boat owner can do to their boat. Let’s say he wants to know over the 50 year lifespan of the ...
dassouki's user avatar
  • 153
6 votes
1 answer
230 views

Dynamic programming problem with machines

A company will be using a new technology for 5 years. For this purpose a specialized machine is required. The company currently has one, which will be 2-year old at the beginning of next year. The ...
Slim Shady's user avatar
6 votes
0 answers
172 views

Minimization of car cost during 4 years problem

I am going to buy a family car at the beginning of the New Year. I am going to stay in the UK for the next 4 years. I am considering the possibility of being a customer of company A which sells BMW ...
Slim Shady's user avatar
5 votes
1 answer
220 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{ ...
Max's user avatar
  • 534
5 votes
1 answer
224 views

Circular reference in states of the Bellman equation

I want to formulate a game of darts as a dynamic program. The goal is to minimize the number of darts thrown while reaching checkout. A dart player has a score s. If his score is s = ...
HJA24's user avatar
  • 113
5 votes
1 answer
477 views

Solving a variant of multiple knapsack problem/ generalized assignment problem

Consider $m$ knapsack and $n$ items. With each knapsack $j$ associated a capacity $c(j)$ and with each item $i$ associated a profit $p(i,j)$ (that depends on the knapsack, so it's not exactly the ...
Joffrey L.'s user avatar
5 votes
1 answer
1k views

Minimisation of shelving cost problem

A library must build shelving to shelve $200$ 4-inch high books, $100$ 8-inch high books, and $80$ 12-inch high books. Each book is 0.5-inch thick. The library has several ways to store books. ...
Slim Shady's user avatar
5 votes
0 answers
77 views

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

I aim to solve the following Bellman equation: \begin{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}^{'} | \...
mdslt's user avatar
  • 615
5 votes
0 answers
58 views

Convergence of an approximate DP for a stochastic shortest path problem

I'm new to the field of sequential decision making. I got intrigued by a stochastic shortest path problem, described in Chapter 5 of this book by W. Powell. Consider the following stochastic shortest ...
Joris Kinable's user avatar
3 votes
1 answer
151 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$ ...
Steven01123581321's user avatar
3 votes
1 answer
254 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,150
3 votes
1 answer
231 views

Is the Dynamic programming in Operations Research book the same dynamic programming in software industry?

Mostly when I search dynamic programming in google I get : dynamic programming (DP) in python, in C++, in java from web pages like geekforgeeks, litecode, codechef, and so on. But in the operation ...
Locker05's user avatar
3 votes
0 answers
49 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
0 answers
29 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-...
Jxson99's user avatar
  • 141
2 votes
2 answers
137 views

Can the following problem be solved recursively?

Consider the following problem \begin{equation} \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 &...
mhdadk's user avatar
  • 611
2 votes
1 answer
44 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?
Engr. Moiz Ahmad's user avatar
2 votes
0 answers
99 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 ...
Benjamin Beer's user avatar
2 votes
0 answers
159 views

Why is exact TDTSP solving much harder to do than TSP solving?

I was thinking about exact methods for solving the Time Dependent TSP (TDTSP). Clearly, it is at least as complex as TSP because it extends TSP, but why is it for exact approaches that difficult to ...
maxmitz's user avatar
  • 659
2 votes
0 answers
84 views

Dynamic Programming problem of affecting equipment with budget constraint

I have a problem that I must formulate as a DP problem and solve. A hospital is split up into 4 sections, each section has 1 or 2 or 3 backup generators. We have to maximize the likelihood that no ...
ndrb's user avatar
  • 21
1 vote
1 answer
204 views

Dynamic Programming - Formulating recurrence relation

We wish to apply dynamic programming techniques to find the optimal betting strategy for a pool to wager on the outcome of the NCAA men's basketball tournament 64 teams compete in a single ...
user620842's user avatar
1 vote
1 answer
114 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 ...
PeterBe's user avatar
  • 1,632
1 vote
2 answers
221 views

Formulate a problem as Mixed Linear Programming problem

I need to formulate the following problem as a Mixed Integer Linear Programming problem A farmer needs to establish a 17-year business plan where he will decide when to sell or buy a new truck. The ...
PLanderos33's user avatar
1 vote
2 answers
118 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 ...
Ying's user avatar
  • 105
1 vote
1 answer
131 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 ...
Engr. Moiz Ahmad's user avatar
1 vote
1 answer
71 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 ...
Julia's user avatar
  • 11
1 vote
0 answers
192 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 ...
Charlie1604's user avatar
1 vote
1 answer
95 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 ...
anerjee's user avatar
  • 119
1 vote
0 answers
140 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 ...
user8949's user avatar
1 vote
0 answers
62 views

How to check if the state of a dynamic program is Markovian or not?

Based on Markov chain context, we say a stochastic process is Markovian if the state at time $t+1$, $S_{t+1}$ just depends on the state in the previous step, that is, $\Pr\left( S_{t+1}|S_1, S_2, \...
Amin's user avatar
  • 2,150
1 vote
0 answers
79 views

Bellman equation for darts that minimizes the number of turns

I want to formulate a game of darts as a dynamic program again. This question is closely related to my previous post where I wanted to minimize the number of throws to reach checkout. Now the goal is ...
HJA24's user avatar
  • 113
0 votes
2 answers
102 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{...
OpenAtTheClose's user avatar
0 votes
1 answer
54 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 ...
Resting Platypus's user avatar
0 votes
1 answer
39 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 ...
Engr. Moiz Ahmad's user avatar
0 votes
1 answer
182 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, ...
Amin's user avatar
  • 2,150
0 votes
0 answers
35 views

When is time window reduction applicable?

Desrochers, Desrosiers and Solomon (1992) presents a method for reducing the size of the time windows for the VRPTW. Given other versions of the VRPTW, what are the requirements on the problem for it ...
gmn's user avatar
  • 632
0 votes
0 answers
60 views

Best strategy for the secretary problem with known distribution

The optimal strategy for the well known secretary problem with $n$ candidates is to reject the first $\lceil \frac{n}{e} \rceil-1$ candidates, and then select the first subsequent applicant that is ...
Kuifje's user avatar
  • 13.2k
-2 votes
1 answer
340 views

dynamic programming shortest path example

Could someone please show how he uses dynamic programming to solve for minimum cost of getting from 1 to 6? Is it recommended to use dynamic programming to solve this? Edit: I know that dynamic ...
Slim Shady's user avatar