Dynamic Programming

Question 1

what is the general idea of DP

Answer 1

Divide a problem into sub problems, solve sub problems independently, and use relations between the sub problems to fidn a solution to the original problem

Question 2

what is the relation between shortest path and DP?

Answer 2

They are strongly related. We can regard each DP problem as a shortest path problem in an acyclic network.

Question 3

what is the difficulty with DP

Answer 3

Formulating problems so that they mimic shortest path problems

Question 4

advantage of DP?

Answer 4

All arcs and nodes do not need ot be stored explicitly.

Question 5

What do we requrie to be able ot use DP?=

Answer 5

THe problem must have a dynamic structure where we can divide the problem into a number of sequential “stages”. We regard it as a case qhere we need to make a decision at each stage.

Question 6

The stages, what are they?

Answer 6

Depends on the application. Typically it is related to time periods.

Question 7

How are sub problems defined?

Answer 7

We define a subproblem by considering one possible state in a stage. So, we define all subproblems (from a stage) as resulting from the various states we can achieve by our decisions.

Question 8

What do we clal the optimal decision?

Answer 8

A control.

Question 9

What do we call variables with optimal decisions?

Answer 9

Control variables

Question 10

what is the relationship between states and stages? Broadly speaking

Answer 10

In a stage and state, a decision will make a new state in the next stage.

Question 11

what is the computation we make in each node?

Answer 11

To satisfy the Bellman equation.

y_j = min [i:(i,j) in B] {y_i + c_ij}, j=2, …, n

this means: Keeping j fixed (but for all j) we select y_j to be the smallest value we find from y_i + c_ij whne we consider all possible values of i, where the arc (i,j) is in the set of arcs.
c_ij defines the cost on the arc.
y_i defines the “shortest path from source to i”.

Question 12

elaborate on what the Bellman equation does

Answer 12

y_j = min [i:(i,j) in B] {y_i + c_ij}, j=2, …, n

this means: Keeping j fixed (but for all j) we select y_j to be the smallest value we find from y_i + c_ij whne we consider all possible values of i, where the arc (i,j) is in the set of arcs.
c_ij defines the cost on the arc.
y_i defines the “shortest path from source to i”.

At some specific node j, we compute its “value” by considering all possible combinations of 1-arc moves in combination with the optimal value on the other side of those 1-arc moves.

Question 13

When can we solve all Bellman equations using a systemaic approach?

Answer 13

When there are no cycles

Question 14

What is DP regarded as?

Answer 14

DP can be considered as a systematic approach to solving the Bellmann’s

Question 15

what is the principle of optimality?

Answer 15

Given the current state, the optimal decision for each of the remaining stages must not depend on previously reached states of previously chosen decisions.

Question 16

What is the result/outcome of the principle of optimality?

Answer 16

Each problem can be solved to optimality using only its subproblems

Question 17

elaborate on the transition function

Answer 17

T_t(s_t, x_t)

The transition function describes which state we will get from performing a certain action/decision in the next stage given a current state and control decision.

Question 18

how does the objective function look like in DP?

Answer 18

we need one term per stage t.

∑c_t(x_t, s_t) [t=1, T]

So, the objective function could be to minimize the cost in each stage.

Question 19

how do we compute the optimal solution using DP?=

Answer 19

Done sequentially using recursion. One stage at a time.

We need a recursion function f_t(s_t) that defines the total cost thus far.

We can give the total cost recursio nfunction as:

f_t(s_t) = min ∑c_i (s_i, x_i) [i=1, T]

We are ultimately searching for f_1(s_1).

The computations of f_t(s_t) is found using the computations done in stage t+1

The recursion relation can be defined as:

f_t(s_t)= min[x_t] [c_t(s_t,x_t) + ∑c_i(s_i,x_i)[i=t+1, T]]
which is equal to

= min[x_t] [c_t(s_t,x_t) + f_(t+1)(s_(t+1)]

This shows how solving for f_t(s_t) requires the solution to f_(t+1)(s_(t+1)), its next component.

Question 20

how do we start the recursion?

Answer 20

We need to define a value for T+1. typically done using 0.

Question 21

What do we actually find from all the recursions+

Answer 21

we find all the transitions and costs.

When we have found all of these, we can find the optimal solution by backtracking the optimal controls.

Question 22

Forward vs backward recursion?

Answer 22

The way we solve the states. We have described backwards recursion till now.

In backwards recursion, we first deal with stage T, then T-1, and the last stage we deal with is stage 1. In each stage, we compute the optimal way of getting from the lowest cost from this stage.

Question 23

What is the important difference in results between forward and backwards recursion?

Answer 23

the only differnece is that one of them gives us the action we should take next, and the other gives the action we optimally already have taken.

Question 24

Elaborate on the 10-step generalized DP model

Answer 24

1) Define the STAGES, for t=1,…,T
2) Define the CONTROL VARIABLES, x_t for t=1, …, T
3) Define the STATES, s_t, for t=1, …, T
4) Define the TRANSITION FUNCTION, T_t(s_t, x_t), which gives the connection between states and decisions in the current stage and the next stage.
If using forward rec: s_(t-1) = T_t(s_t, x_t)
if using backward rec: s_(t+1= = T_t(s_t, x_t)

5) Define the RECURSION FUNCTION, f_t(s_t) which rexpresses the optimal objective function value for the stages computed so far as a function of the current state:
f_t(s_t) = min ∑c_i(s_i, x_i)[dependent on recursion]

6) Formulate the RECURSION RELATIONS

For instance, f_t(s_t) = min[x_t] {c_t(s_t, x_t) + f_(t+1)(s_(t+1))} if backward recursion

7) Introduce the INITIAL CONDITIONS

8) Specify RESTRICTIONS to control variables and states, x_t in X_t

9) Make COMPUTAITONS stage after stage

10) Make a BACKTRACK to find the optimal solution.

Question 25

elaborate on the procedure of DP

Answer 25

First, we need to define stages. These stages refer to the sequential decisions we need to make. The important part here is that the sequence makes sense, not necessarily that there is a time component there. FOr intance, knapsack problems have sequantial decisions.

Then we define the variables. This is akin to defining the actual decisions we need to make at the various stages. The decision we ultimately end up taking will depend on the state.

Then we define our states. This is basicllyu defining the differnet scenarios we might find ourselves in. For instance, in shortest path a state can be a specific position.

Now we need to define the relationship between the state+decision in one stage and the next state stage. We define this as the TRANSITION FUNCTION. The transition ufnctyion gives a state, either the future state (backward recursion) or the previous state (using forward recursion). So, based on a stage (subscript t) we enter the current state and a decision from the current state, and we will get the relationship between this and the next state. The next state is the state at the next stage.

Now we have the sequence of decisions we need to make, we have all possible states, and we have all possible actions. We also have the relationship between current state and the next state as a function of current state and a decision.

The next thing we need is the RECURSION FUNCTION.
The recursion function specify the cost, or whatever else we are optimzing for for. I nthe shortest path problem, the recursion function will be measuring cost in terms of distance.
the recursion function is defined so that the “cost” in stage t is given as f_t(s_t) = min ∑ci(si, xi)[]

The sum will either be from 1 to t, or from t to T depending on whether we use backward or forward recursion. If forward, it is from i=1 to t. IF backwards recursion, it is from i=t to T.
So, this function should give us the minimal cost of getting from a state to a state whne considerign the sequential nature of the problem.

Then we need the RECURSION RELATIONS. This is what actually build the earlier function. The key is htat the recursion function earlier is what we use to compute the optimal obejcevtuve function value for the stages computed so far. The recursion relations are about idk, book doesnt say
However, the relations are basically the Bellmans.