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.
52 questions
-1
votes
0
answers
27
views
Labeling algorithms modification for subproblem constraints
this is rephrased version of a previous question, to be a bit more precise. This is my proposed labeling algorithm to solve the Subproblems in my Branch&Price algorithm.
Labeling Algorithm
For ...
- 43
3
votes
2
answers
201
views
Finding multiple non-crossing optimal paths across a weighted grid with minimum vertical spacing
I’m working on an optimization problem that I believe can be framed as a graph or flow problem, but I haven’t found a good existing formulation that scales efficiently. I’d like advice on how to model ...
- 133
0
votes
0
answers
34
views
Pseudo-polynomial time dynamic programing for this subset sum variant
We define the all-subset-sum problem as follows. Given a set $S$ of positive integers and a target $T$, the goal is to find all the maximal distinct subsets of $S$ summing to $T$.
A maximal set is a ...
- 303
0
votes
1
answer
127
views
What do we call the situation when SDDP can solve non-recoursable problem due to feasible actions that lead to later infeasibility can not be optimal?
More comprehensively, what is the technical term of the situation in which the SDDP (stochastic dual dynamic programming) algorithm can solve a non-recoursable problem because the feasible actions ...
0
votes
0
answers
76
views
Dynamic Programming Tabulation
I am struggling with the following problem.
A college student has 7 days remaining before final examinations begin in her four courses, and she wants to allocate this study time as effectively as ...
- 1
2
votes
1
answer
144
views
How can I compute the "value" of one unit of inventory with linear programming?
In the following inventory problem, there are $N$ units of inventory available at the beginning of the time horizon $T$. Each day $t\in T$, it is possible to sell one unit of the inventory at price $...
- 488
1
vote
0
answers
85
views
DP for a variation of the knapsack problem?
I have a variation of the knapsack problem where each item has a profit ($p_i$), weight ($w_i$), and penalty ($t_i$). The objective is to maximize the summation of the selected items' profits minus ...
- 613
1
vote
0
answers
34
views
Is there any survey about studies of the efficacy of different refueling algorithms as the distance of the graph becomes larger?
Have there been any comprehensive surveys or meta-analyses examining the efficacy of various refueling algorithms(such as this or approximation algorithms etc) across varying graph distances? ...
- 119
1
vote
0
answers
58
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
1
answer
117
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. ...
- 113
2
votes
2
answers
173
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 &...
- 639
0
votes
1
answer
89
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
1
answer
218
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,722
2
votes
1
answer
96
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?
0
votes
1
answer
66
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 ...