19
votes
Solving a knapsack problem with a lot of items
For the knapsack problem, you just use the Pisinger's code. It implements an exact algorithm, it is the fastest algorithm known in the literature, and it is open-source: http://hjemmesider.diku.dk/~...
- 1,394
11
votes
Suggestion of some courses in sequential decision making
There are a few courses on Coursera that offer such learning materials.
Greedy Algorithms, Minimum Spanning Trees, and Dynamic Programming (Intermediate)
The primary topics in this part of the ...
- 5,341
9
votes
Solving a knapsack problem with a lot of items
A comprehensive comparison of different approaches to solving the knapsack problem is given in the recent paper1 by Ezugwu et al., where the authors compare the performance of the following approaches ...
- 8,622
6
votes
Accepted
Optimal set order to maximize stochastic reward
As it is explained here, this problem is a portfolio selection problem. The player should select the first $n$ booths with the maximum $E(g_i)=p_i \times r_i$ in which $E(g_i)$ represents the expected ...
- 8,622
6
votes
Accepted
Dynamic programming example
The "cost" values in the lower left table are calculated as the sum of the cost of buying the car ($12000$), plus the total maintenance cost of each year of owning the car, minus the trade in cost ...
- 1,799
5
votes
Accepted
Dynamic program for knapsack in $O(W)$ space?
There is a recursive scheme which makes it possible to retrieve the optimal solution with an $O(n + W)$ memory. It is described in Section 3.3 of the book "Knapsack Problems" (Kellerer et al....
- 2,495
5
votes
Efficiency of Forward vs. Backward Recursion in Dynamic Programming
First, what is Dynamic Programming? Everyone has its own definition. The one I use is "Solving a problem recursively, while storing the results of the sub-problems to avoid recomputing them ...
- 2,495
5
votes
Accepted
Why are these constraint equations equal?
The two sets of constraints are not the same, but both sets provide a formulation for the problem. The relationship between the two is that if you take a solution to (2.1) and (2.2), compute $z_t=\...
- 30.4k
5
votes
Accepted
Dynamic Programming - Formulating recurrence relation
You have an instance of the 0-1 knapsack problem where you want to determine which teams to select to maximize the number of wins, subject to a budget. The linked page provides a DP recurrence, which ...
- 30.4k
4
votes
Accepted
Multi-period linear dynamic programming with differing in-period dependencies and changes
Disclaimer : this is more of a hint than a complete answer.
You can use the following model as a starting point to make your own model. I am ignoring two items :
Constraint from option 3:
Under this ...
- 12.9k
4
votes
Solving a variant of multiple knapsack problem/ generalized assignment problem
It looks like there is no relationship between different knapsacks, so you can solve this exactly as $m$ independent 0-1 knapsack problems. Also, for knapsack $j$, you can eliminate any items $i$ ...
- 30.4k
4
votes
The general meaning of "constraint relaxation" in the context of the Shortest Path Problem
To my knowledge, the term relaxation is used to indicate that a constraint (or a group of constraints) is removed from the model, rendering a model that is more loose, less constrained.
In the ...
- 12.9k
4
votes
Dynamic programming problem with machines
For the following I did not check in depth the rules related to end-of-period/beginning of period, so this is something you should carefully check for your problem. However, the approach does not ...
- 2,080
4
votes
Suggestion of some courses in sequential decision making
The previous answer provided a great list on the classical dynamic programming. For Reinforcement learning and Deep Reinforcement learning, a wonderful online free course on RL by David Silver (the ...
- 825
4
votes
How to solve Stochastic Dynamic Program with huge state space?
Just to expand very slightly the comments by Mark: in general exact stochastic dynamic programming scales quite poorly.
Value iteration complexity for each iteration is $O(A S^2)$ where $A$ is the ...
- 211
4
votes
Accepted
Circular reference in states of the Bellman equation
For each state $s$, you want to compute the value function $V(s)$, which satisfies $V(0)=0$ and the Bellman equation for $s \not= 0$:
$$V(s) = \min_\mu\left\{1+\sum_z V(f(s,z)) p(z;\mu)\right\}. \tag{...
- 30.4k
4
votes
Accepted
Bellman Equation for nonlinear model
Let $f(n,b)$ be the maximum objective value for the problem with variables $x_1,\dots,x_n$ and constraint right-hand side $b$. You want to compute $f(3,7)$.
Let $a_i$ be the constraint coefficient of $...
- 30.4k
4
votes
Accepted
Can dynamic programming find globally optimal solutions for scheduling problems
Assuming your state space is discrete (for instance, there are finitely many possible charge levels for the vehicle), and assuming that how much you pay for charging depends on the amount of charging ...
- 37.8k
3
votes
Accepted
What kind of data structure should be used to store labels when implementing a labeling algorithm?
I have experience in writing the code implementing the labelling algorithm used by VRPSolver (https://vrpsolver.math.u-bordeaux.fr). You are right: it is advantageous to keep labels in a contiguous ...
- 1,394
3
votes
Optimal set order to maximize stochastic reward
To get $O(2^M M^2)$ instead of $O(M!)$, you could modify the dynamic programming formulation of the traveling salesman problem, with a state for each subset of booths visited so far.
- 30.4k
3
votes
Accepted
Can I use continuous probability distributions when creating an SDDP.jl model?
Per the SDDP.jl documentation, the answer is no. But see below for a workaround.
Per States, controls, and random variables 3.
Random variables are finite, discrete, exogenous random variables that
...
- 13.1k
2
votes
Accepted
dynamic programming shortest path example
There are algorithms specifically designed for shortest path problems, so dynamic programming is not the most common choice for it. On the other hand, small shortest path examples are commonly used to ...
- 37.8k
2
votes
Accepted
Minimisation of shelving cost problem
I do not understand why the formula for $C_{0,4}$ is as such. A simple check reveals that the unit on the RHS are pounds / (pounds / inch2) = inch2 whereas the unit for the cost is pounds.
We have ...
- 5,341
2
votes
The general meaning of "constraint relaxation" in the context of the Shortest Path Problem
In optimisation theory, creating a relaxation refers to an operation which:
Creates a superset of an underlying set, if the operation is done on a set
Produces a new set of functions that define a ...
- 11.9k
2
votes
Solving a knapsack problem with a lot of items
You don't give that bit of information, but you might be able to use a far more efficient algorithm when knapsack size (let's call it $S$) is small enough (small enough to create an array of each ...
- 21
2
votes
Formulate a problem as Mixed Linear Programming problem
The following model gives the purchasing temporal sequence for truck so that the cash flow is optimal within the planning horizon of 17 years. The model requires $68$ Boolean variables ($68=17 \cdot 4$...
- 365
2
votes
Accepted
Is the Dynamic programming in Operations Research book the same dynamic programming in software industry?
It's definitely the same idea. You can look at dynamic programming as developing a program to deal with large combinatorial problems, where brute force just isn't efficient. It comes down to finding a ...
- 1,043
2
votes
Bellman Equation for nonlinear model
Assuming there are n stages, S symbolized by say $s$ define $x$ as $x_{1,s},x_{2,s}, x_{3,s}$: decision vector $X_s$ and $Z(X_s)$ as optimal value for every stage $s$ subject to same constraint
Using ...
- 3,343
2
votes
Accepted
Is stochastic dual dynamic programming (SDDP) a deterministic solution algorithm or does it have a stochastic component to it?
It depends on the implementation.
Irrespective of whether the model has one scenario or many, it's possible to code an implementation of SDDP that is deterministic in the sense that it will return the ...
- 921
2
votes
Accepted
How can I write the output stream of SDDP.jl into an excel file?
Use the log_file keyword argument to train: https://odow.github.io/SDDP.jl/stable/apireference/#SDDP.train
Or, after training, ...
- 921
Only top scored, non community-wiki answers of a minimum length are eligible