18 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/~...
user avatar
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 ...
user avatar
  • 5,191
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 ...
user avatar
  • 8,340
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 ...
user avatar
  • 8,340
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 ...
user avatar
  • 1,769
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....
user avatar
  • 1,711
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 ...
user avatar
  • 1,711
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=\...
user avatar
  • 22.7k
4 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 ...
user avatar
  • 22.7k
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 ...
user avatar
  • 10.4k
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 ...
user avatar
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{...
user avatar
  • 22.7k
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 ...
user avatar
  • 2,050
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 ...
user avatar
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 ...
user avatar
  • 10.4k
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$ ...
user avatar
  • 22.7k
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 ...
user avatar
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.
user avatar
  • 22.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 ...
user avatar
  • 31.1k
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 ...
user avatar
  • 5,191
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 ...
user avatar
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$...
user avatar
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 ...
user avatar
  • 21
1 vote

How to model history-dependent dynamic program?

Apart from some "current" values, a state of the state machine can include the history of the previous state changes. Say the state consists of the two booleans, current state and previous ...
user avatar
  • 121
1 vote

What kind of data structure should be used to store labels when implementing a labeling algorithm?

I can't speak to "state of the art implementations", but I would store the labels in lexicographic order of resource levels. Let's say vector $x$ is our new label and we want to see if it is ...
user avatar
  • 31.1k
1 vote
Accepted

Formulate a problem as Mixed Linear Programming problem

From context, I'm assuming that the farmer always needs to have a truck, and the question is when he should replace it. For the constraints, you can formulate in terms of 17 binary decision variables: ...
user avatar
1 vote

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 ...
user avatar

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