Skip to main content

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.

15 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
6 votes
0 answers
173 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
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
60 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
0 answers
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 ...
stewardbranson's user avatar
3 votes
0 answers
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-...
Jxson99's user avatar
  • 141
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
161 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
0 answers
203 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
101 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
143 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
63 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,160
1 vote
0 answers
86 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
0 answers
36 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
  • 676
-1 votes
0 answers
22 views

During a disaster response, operating cost of temporary logistics facilities should be how many times the step up cost of these facilities?

I am optimizing a multi-stage optimization model for disaster response relief delivery. In this regard, I want to know the realistic values of cost parameters related to the operating and setup costs ...
Engr. Moiz Ahmad's user avatar