Skip to main content
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/~...
Ruslan Sadykov's 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 ...
TheSimpliFire's user avatar
  • 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 ...
Oguz Toragay's user avatar
  • 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 ...
Oguz Toragay's user avatar
  • 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 ...
dxb's user avatar
  • 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....
fontanf's user avatar
  • 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 ...
fontanf's user avatar
  • 2,623
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=\...
RobPratt's user avatar
  • 32.7k
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 ...
RobPratt's user avatar
  • 32.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 ...
Kuifje's user avatar
  • 13.5k
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$ ...
RobPratt's user avatar
  • 32.7k
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 ...
Kuifje's user avatar
  • 13.5k
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 ...
Paul Bouman's user avatar
  • 2,100
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 ...
Afshin Oroojlooy's user avatar
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 ...
CarrKnight's 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{...
RobPratt's user avatar
  • 32.7k
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 $...
RobPratt's user avatar
  • 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 ...
prubin's user avatar
  • 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 ...
Ruslan Sadykov's 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.
RobPratt's user avatar
  • 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 ...
Mark L. Stone's user avatar
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. ...
RobPratt's user avatar
  • 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 ...
prubin's user avatar
  • 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 ...
TheSimpliFire's user avatar
  • 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 ...
Nikos Kazazakis's 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 ...
sqlnoob's user avatar
  • 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$...
marco tognoli's user avatar
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 ...
Steven01123581321's user avatar
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 ...
Sutanu Majumdar's user avatar
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 ...
Oscar Dowson's user avatar

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