Questions tagged [dynamic-programming]

Dynamic programming is a mathematical optimization/programming approach applicable if an optimal solution can be constructed efficiently from optimal solutions of its subproblems. A classic example is the Towers of Hanoi.

Filter by
Sorted by
Tagged with
1 vote
1 answer
55 views

Finding the most probable labeling that sums up to some integer

We know that solving the optimization problem such as $$\max_{y_1, \dots,y_n} \sum_{i=1}^{n-1} f_{i,i+1}(y_i,y_{i+1})$$ $$y_i \in \mathbb{N}_0$$ is easy and can be done via dynamic programming (...
user avatar
1 vote
1 answer
13 views

How to assign a known number of different size of outbound packages, to a known (different) number of inbound deliveries?

I am trying to solve a problem that looks like the multiple knapsack problem, the multiple bin packing problem and the subset-sum problem, but isn't exactly one of them. Imagine a warehouse where 4 ...
user avatar
  • 13
0 votes
0 answers
18 views

Solve Value Function Analytically

Say I have a Bellman equation where the state variable is discrete: $$\begin{aligned} r V(n)=& \max _{\lambda}\{\pi n- nc(\lambda)+ \lambda n[V(n+1)-V(n)]\\ &-\mu n[V(n)-V(n-1)]\} \end{aligned}...
user avatar
0 votes
1 answer
24 views

Dynamic programming efficient network

Hello I have a dynamic programming related question. How can I compute the shortest path in hops from starting vertex u to ending vertex v, with the constrain that the vertices and edges will have an ...
user avatar
0 votes
1 answer
42 views

Recurrence relations in dynamic programming

I have the following problem: Assume a truck collects items from a grid with n*n size starting at location (0, 0)and delivers them to a terminal (n, n). The truck can move right, left or down. There ...
user avatar
0 votes
1 answer
59 views

Is the Bellman-Ford algorithm pseudo-polynomial?

We know that the problem of finding a shortest path that visits each node at most once is NP-hard. It seems to me that Bellman-Ford does that but its time complexity it $O(mn)$ so polynomial. Isn't ...
user avatar
0 votes
0 answers
33 views

How do I prove this dynamic programming problem?

Given: $y_i$, $w_i$ - variables at stage $i$, $y_{i} \in \mathbb{R}$, $y_{i} \in \mathbb{R}$; $a\leq w_i \leq b$; $i = 1,\dots,n$ We are also given a function $\phi(\cdot)$ which is continuous. $y_1$ ...
user avatar
1 vote
0 answers
29 views

How is the Wilson-Han-Powell SQP algorithm applied?

Say for example we need to minimize $x_2$ subject to $x_1^2+x_2^2-1=0$ starting at $x_1=x_2=1/2$ and using $B=\nabla^2[x_2+\lambda(x_1^2+x_2^2-1)]$ with $\lambda=1$. Now, the WHP-SQP algorithm goes ...
user avatar
1 vote
0 answers
20 views

A CSP on bit vector operations

I've got a CSP which is based on constraining bit vector variables. It is explained below through an example, followed by the full definition. So, what I'm concerned about is if you have some idea if ...
user avatar
0 votes
1 answer
54 views

Determine the location of a logistics center which is optimally close to its providers

Excuse me if my question is not worded perfectly in mathematical terms. I don't have a strong math background. So, here's the problem which has been brought up by a real-life situation: For simplicity,...
user avatar
1 vote
0 answers
24 views

Max edit distance between binary strings of length n

Given a binary string s of length $n>2$.An edit operation is a single character insert, delete or substitution. The edit distance between two strings is the minimum number of edit operations needed ...
user avatar
1 vote
0 answers
39 views

Mathematical Requirements for Dynamic Programming

As far as I understand, for Dynamic Programming to "work" (I think this means for Dynamic Programming to return a Globally Optimal Solution?), am optimization problem must have the two ...
user avatar
  • 1,842
1 vote
0 answers
30 views

Can Gradient Descent be "Combined" with Dynamic Programming?

In most applications of Gradient Descent (e.g. optimizing the Loss Functions of Neural Networks) - regardless of the "type" of Gradient Descent algorithm being used (e.g. Stochastic Gradient ...
user avatar
  • 1,842
2 votes
1 answer
57 views

Can Machine Learning models be considered as "Approximate Dynamic Programming"?

In the context of certain statistical/machine learning models, such as models that are trying to estimate "optimal policies" (e.g. reinforcement learning) - can we consider these models as &...
user avatar
  • 1,842
2 votes
1 answer
89 views

What was so "Groundbreaking" about Bellman's Equations?

In the context of Decision Making and Game Theory, "Bellman's Equations and Bellman's Conditions of Optimality" are said to be some of the most important mathematical principles in this ...
user avatar
  • 1,842
2 votes
0 answers
55 views

Efficiency curves, what is this called?

I am studying a set of functions. This seems like something other people would have studied too, and I'd like to know what other people are calling this and how to read up on it. These "...
user avatar
0 votes
0 answers
48 views

Ordered Graph Problem

Let G = (V, E) be a directed graph with nodes v1, v2, . . . , vn. We say that G is an ordered graph if it has the following properties. (i) Each edge g Let G = (V, E) be a directed graph with nodes v1,...
user avatar
2 votes
0 answers
33 views

Structured policies in dynamic programming: solving a toy example

I am trying to solve a dynamic programming toy example. Here is the prompt: imagine you arrive in a new city for $N$ days and every night need to pick a restaurant to get dinner at. The qualities of ...
user avatar
0 votes
0 answers
9 views

Reference request: multi-armed bandit problems with analytical solutions

Is there a book/survey on (multi-armed) bandit problems that yield analytical solutions? I.e. has an exactly optimal closed-form solution (e.g. derived using dynamic programming).
user avatar
0 votes
0 answers
15 views

Reference Request for Bandit Problems where myopic strategies are optimal

I recently found a paper (Banks and Sundaram, 1992) on a class of bandit problems where the myopically-optimal strategy (in each period, choose arm that maximizes current period's expected payoff) is ...
user avatar
0 votes
1 answer
56 views

Are these two relations the same?

Suppose we want to find the shortest path with at most $\ell$ edges in a positive weighted directed graph $G=(V,E)$ with weight $w(u,w)$ on each edge. According to Jeff Erickson's algorithms textbook, ...
user avatar
  • 319
0 votes
0 answers
9 views

Risk measures and Bellman's principle of optimality in the context of risk-sensitive MDPs

I'm learning about finite-horizon risk-sensitive Markov Decision Processes (MDP) in the context of stochastic shortest path problems. In a nutshell, instead of finding a policy that minimizes the ...
user avatar
  • 155
0 votes
0 answers
9 views

Speed adjustment on a given path for cost minimization with fixed departure and arrival time

I have an optimization problem which consists in going from a departure point to an arrival point given a set of predefined intermediate points between the departure and the arrival. The departure and ...
user avatar
  • 1
2 votes
0 answers
46 views

Tractable setup for sequential Bayesian estimation with a binary data (in a case where a beta-bernoulli setup seems inappropriate)

An unknown parameter $\theta$ is randomly drawn at time $t=0$ according to prior p.d.f. $\mu_0(\cdot)$ that has support $[L,R]\subseteq\mathbb{R}$. At each time $t\in\{1,2,...\}$ an agent makes an ...
user avatar
1 vote
0 answers
39 views

What the meaning of "impatience" in Bellman equation?

From wiki: A dynamic decision problem ... Finally, we assume impatience, represented by a discount factor $0 < \beta < 1$ What the meaning of "impatience"? I can't understand even if ...
user avatar
  • 111
0 votes
0 answers
24 views

For optimization problems, is the complementary slackness constraint really necessary?

I am dealing with a bilevel optimization problem, and to solve it I am applying the Karush–Kuhn–Tucker conditions to the inner optimization problem. As a result, I can reformulate my bilevel ...
user avatar
1 vote
1 answer
66 views

Expected Number of steps to reach 0.

Consider following problem, You are given $N$ piles, $i^{th}$ pile has size $S_i$. Until size of all the piles become $0$, repeat the following step. With probability $p$, size of atmost one pile will ...
user avatar
0 votes
0 answers
38 views

Solve the optimality equation for this dynamic programming problem

I am learning about stochastic and dynamic programming. I have been going through the book by Sheldon Ross. It's somewhat dated but has a number of examples. I have been trying to work through the ...
user avatar
0 votes
0 answers
36 views

How to proof a greedy algorithm for return loans to bank

This problem was in my homework, now I'm preparing for exam but still couldn't understand it. We have $n$ loans, each loan has initial amount $R[i]$ and interest $a[i]$, and Monthly income $S.$ each ...
user avatar
  • 1
0 votes
0 answers
69 views

Most Likely Number of Wins Given Array of Probabilities

You are given a team's win probability for each game on their schedule in the form P[1..n] where P[i] is the likelihood they win game i. Find the most likely number of wins. For example, if n = 2 and ...
user avatar
  • 95
0 votes
0 answers
23 views

What is the distribution of a future posterior belief given a sequence of data? What if the latter depends on the former?

Let $Y\sim$ Bernoulli($\mu$). The realization $y\in\{0,1\}$ of $Y$ is not observed by the agent, who instead "learns'' about $Y$ over $T\in\mathbb{N}$ time periods. Specifically, in period $t\in\{...
user avatar
5 votes
0 answers
80 views

Optimal control of posterior belief over a finite horizon

$\large \textbf{Preface:}\ $ Below I describe a dynamic programming problem I am not sure how to formalize. In short: a (Bayesian-updating) agent sequentially runs costly experiments over a finite ...
user avatar
0 votes
0 answers
24 views

Multi-Stage Combinatorial Optimization

I am not sure if I used the corret terminology. I think the problem is a multi-stage combinatorial optimization problem. The problem is like this: There is a dynamic equation $$ S_{k+1} = f(S_k,\pi_k) ...
user avatar
1 vote
0 answers
46 views

Maximize the sum of weights of covered intervals

Suppose we are given n open intervals $(a_1, b_1)$, ..., $(a_n, b_n)$, with interval $i$ being assigned a weight $w_i$ for all $i$. We are given an integer $k<n$, and we are allowed to choose $k$ ...
user avatar
  • 163
1 vote
0 answers
14 views

define max function when arguments and operators are given, and you have to decide only where to put braces

I have the following problem: Given a set of $n$ values, $x_1,...,x_n$, and $n-1$ operators between them (that is, we are given the formula $x_1 o_1 x_2 o_2 ... o_{n-1}x_n$), our objective function is ...
user avatar
0 votes
0 answers
13 views

Optimal policies and if we would always choose them

Suppose the value of a policy $\pi$ is defined as $$V^{\pi}(s) =E[R \mid s, a]$$ where $R$ stands for the return associated with following $\pi$ from the initial state $s$. Let an optimal policy be ...
user avatar
3 votes
1 answer
80 views

Optimal stopping of a Poisson Process with a risky reward

I'm confident that there is a well-known solution to this problem, but I am having trouble finding a reference for it. I am also quite rusty on these kinds of problems, so I am having trouble solving ...
user avatar
0 votes
0 answers
16 views

Find the intersection of elements of powerset one by one

Let S = { trigon, tetragon , pentagon , ... ,... } is a set of polygons How to calculate intersection of subsets of (every element actually) ...
user avatar
  • 1
0 votes
0 answers
40 views

Euler Equations in Dynamic Programming: a misunderstanding

I have a question about the solution to infinite horizon problems. Suppose that we have derived the following Lagrangian for a pretty standard growth model in macroeconomics: $ L=\sum_{t=0}^{\infty} \...
user avatar
1 vote
0 answers
45 views

Optimization Problem: Maximize percentage of dependent sum

I have an optimization problem which I currently solved by brute force but I was wondering if there is a more efficient solution. I wasn't able to reduce the problem to some well known problem in ...
user avatar
  • 11
0 votes
0 answers
50 views

Design an algorithm to find k vertices to cover as many edges as possible.

How to design an $O(k^2 n)$-time algorithm to find $k$ vertices in a tree to cover the maximum number of edges, where $G=(V,E)$ is undirected. And $n=|V|,m=|E|$ as usually denoted. What I tried is to ...
user avatar
0 votes
0 answers
36 views

how many triples of positive integers a b c are there so that a+b+c<=S and a*b*c<=P (programming c++) formula without three nested loops

For example, if S and P are 5 and 2, respectively. The answer would be - 4. 1 1 1 1 1 2 1 2 1 2 1 1
user avatar
0 votes
0 answers
16 views

Secure multiparty computation and dynamic programming solution concept?

Consider the usual problem of secure communication, where each of the $I$ agents have a private signal $s_1,s_2,\dots,I$ and they wish to compute any function $f(s_1,s_1,...,s_I)=(x_1,x_2,...,x_I)$ in ...
user avatar
  • 251
1 vote
1 answer
121 views

Source of a Dynamic Programming Algorithm for Finding the Maximum Independent Set in a Graph of Treewidth k

On the Wikipedia page of Tree decomposition, there is a dynamic programming algorithm for finding the maximum independent set in a graph of treewidth $k$. For a node $X_i$ of the tree decomposition, ...
user avatar
  • 11
-2 votes
1 answer
46 views

This is a dynamic programming question. Details can be found in the body(Including an image)

Write the optimal profit of the problem as a function of $z_{k}{(i)}.$ Solve $z_{1}(i)$ for all i ∈ {0,...,α}. Write a recurrence equation satisfied by $z_{k}(i)$ for all (k,i) ∈ {1,...,n} × {0,...,α}....
user avatar
1 vote
1 answer
76 views

How to model history-dependent dynamic program?

Suppose there is a dynamic program that the state of the problem grows over time (more info is added to the state of the problem over time) and at each time, we need all historical data, full history. ...
user avatar
  • 121
2 votes
1 answer
117 views

CSES "Moving Robots": How can we solve this expected value problem?

I am trying to solve the following problem: Given a 8x8 board where each square has one robot on it, define a move as follows: every robot moves either up, down, left, or right (each with an equal ...
user avatar
1 vote
0 answers
17 views

How can we find the minimum cost of redistributing gold.

problem statement: We are given n gold mines having A[i] amount of gold at ith gold mine ...
user avatar
0 votes
0 answers
37 views

Find the most optimal plan to sell the products (Python)

I'm working on a dynamic programming problem and actually, I'm not quite sure whether it is dynamic programming since moving average $M$ is based on previous $M$. No need to consider the efficiency. ...
user avatar
0 votes
0 answers
72 views

Overlapping line-segments

I came across a question that was a part of a coding contest on CodeForces. The contest is over now and this is the link to the question. You are given $n$ lengths of segments that need to be placed ...
user avatar

1
2 3 4 5
12