Skip to main content

# Tag Info

## Hot answers tagged dynamic-programming

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,514
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,412
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,667
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,667
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,623
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,623
5 votes
Accepted

• 32.7k
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 ...
• 39.5k
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,514
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.
• 32.7k
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.5k
3 votes
Accepted

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

For a linear function $g(a)$, the function $g(a)^+=\max(g(a),0)$ is piecewise linear (with two pieces). Also, finite combinations (weighted sums) of piecewise linear functions are piecewise linear. ...
• 32.7k
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 ...
• 39.5k
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,412
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 ...
• 12.2k
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$...
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,485
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 ...
• 981

Only top scored, non community-wiki answers of a minimum length are eligible