Chapter 2

Dynamic programming
Introduction
Dynamic programming is applicable to many optimization problems with
linear or nonlinear constraints, in continuous or discrete variables, having a certain
property known as decomposability. The term 'Dynamic Programming' comes from the fact that the
method has first been applied to the optimization of dynamic systems i.e. evolving at
course of time. However, the principle of the PD is more general and can apply to
optimization problems where time does not intervene, as in the LPNE.
The basic idea of PD is to try to replace the optimization of a function at n
Variables for solving a number of optimization problems, easier to
solve (for example, the optimization of a problem with a single variable). In this sense, the method
may be reconsidered as a decomposition method.
La PD est dûà Bellman qui fait premier à formuler le principe d’optimalité : « Dans une
optimal sequence of decisions regardless of the first decision made, the decisions
subsequent form an optimal subsequence, given the results of the first
decision
Before presenting the formalism of dynamic programming, we present in what
Here is an illustrative example explaining the principle of programming reasoning.
dynamic.
Illustrative example: Inventory management problem
The following table shows, for the 5 periods subject to the study, the quantities of a
Certainly, a merchant wants to resell, as well as the unit purchase prices.

Period i 1 2 3 4 5
Request 2 3 4 3 2
Price 13 15 20 11 12

Knowing that this merchant has a storage capacity of 5 units (the storage cost is
null), the problem is to determine the optimal purchasing policy, that is to say we seek to
determine the quantities to purchase in each period to minimize the total purchase cost
over the 5 periods. In addition, we have:

Purchases are made at the beginning of each period.

We must store the sales of the current period
3. We start and end with a zero stock
4. The quantities purchased must necessarily be whole numbers.

Let's ask: quantity purchased at the period (j∈ N,j =1,5)

remaining quantity in stock at the end of the period

 is called a state variable. It describes the state of the system at the end of the period

is called decision variable. The variables and must therefore be satisfied:

i. 0≤ <= 5- j=1,2,...,5 (1) and (2)

ii. = =0
iii. = + -

The previous problem can thus be formulated as a MILP:

( )∑

(P)

{ ∈

In the following, we solve (P) by breaking down the problem sequentially into several sub-
problems in the following way; We are first interested in the first period
only then do we seek an optimal purchasing policy for the first two periods, and so on
continuation. At the stage where the solution is determined, we are interested in the subproblem restricted to the first k.
periods. In other words, at step k of the solution, the problem is restricted to the first k variables.
only, until arriving at the initial problem.
1tireperiod :
Under (i), the 1ladyperiod may be ended with 0, 1, 2, or 3 units in stock (i.e. = 0,1,2 or 3).
The corresponding costs are 26, 39, 52, and 65 respectively (for example if =0, = 2 and =2)

2thperiod:
If we want to finish the second period with 0 units in stock:
=0: we distinguish 4 cases:

=5 =0( ) c = 65 + 0 = 65
=4 =1( ) c = 52 + 15 = 67
=3 =2( ) c = 39 + 30 = 69
=2 =3( ) c = 26 + 45 = 71

It is clear that the best decision to make if we want to finish the 2thperiod with zero stock is
to buy 5 units at the 1stoneperiod and 0 units to the second.
Likewise, if one wants to end the second period with 1 unit. , the best strategy to take is
the following: =5 ( ), =1 cost c= 65+15=80
Thus, we obtain the optimal sub-policy to choose in [Link] period is as follows:
Yes =0 ( ) () c=65
Yes =1 ( ) () c=80
 Yes =2 ( ) () c=95
In the same way, we deduce the optimal sub-policy to undertake during the 3thperiod (0≤ ≤ 1):
If =0 ( , , )=(5,2,2) c=95+40=135
Yes =1 ( , , (5,2,3) c = 95 + 60 = 155
The following table summarizes the 5 optimal sub-policies for the 5 periods. The optimal policy is
of course the one corresponding to 5thperiod (with zero stock of course)

Period Costs
cumulative
1week 2 0 2 / / / / 26
period 1 3 / / / / 39
2 4 / / / / 52
3 5 / / / / 65
2th 3 0 5 2 / / / 65 + 0 = 65
period 1 5 1 / / / 65 + 15 = 80
2 5 2 / / / 65+30=95
3th 4 0 5 2 2 / / 95 + 40 = 135
period 1 5 2 3 / / 95 + 60 = 155
4th 3 0 5 2 2 3 / 135+33=168
period 1 5 2 2 4 / 135+44=179
2 5 2 2 5 / 135+55=190
5th 2 0 5 2 2 5 0 190+0=190
period

The optimal policy is therefore: =5 =2 =2 =5, =0

The total cost = 190
Recall that the previous problem can be formulated as an MILP:

( )∑

(P)

{ ∈

The last one can be decomposed (over the 5 periods) into five sub-problems. ( )

( )∑

(α)

{ ∈
Note that the resolution of returns( ) to seeking an optimal sub-policy on the first k
periods knowing that we want to finish the kthperiod with a stock of α units. ((P) ( ))We
let's first set the value of then we solve (a) for each fixed value of
For k=1 for example, by posing ( )value of the objective function of ( ), on a we
we therefore have four sub-problems:
() ( )
(){ with

Note that the previous solving method is based on the recurrence relation that exists between
these subproblems.

Resolution of the inventory management problem using graphs: Bellman Algorithm

The previous inventory management problem can be modeled by a weighted directed graph:
G = (V, E) such that: V = {(i, ) i=1.5 and ∈ {0,1,2,3}} with and 0

((i, ) ( )) ∈ ssi j=i+1 and

We associate with each arc((i, ) ( )) a weight ( ).

This is of course about finding a shorter path from the initial vertex (0.0) to the final vertex (5,0), which
corresponds to the initial problem.

The graph is acyclic, we apply the Bellman algorithm:

We recall below the principle of this algorithm:
Bellman Algorithm: (graph without circuit)
Let G=(V,E) be a weighted directed acyclic graph with a distance

(where weight associated with the stop

Let s be a source vertex without a predecessor.

( ) Represents the (shortest) distance from s to x

Bellman Algorithm
Start
Mark the top : ()
As long as he unmarked vertices, all of whose predecessors have been marked to do
To mark such a summit 'to take note of it'
o()∈ ( )* + = Min { ( )+ d(x,y)}
As long as
End

In our case: ( ) , ( ) ( - )

The optimal path is: (0,0)-(1,3)-(2,2)-(3,0)-(4,2)-(5,0)

Who corresponds to the optimal policy:
Remarks:
The first example of this chapter clearly shows that any solution to the posed problem is a
set of 5 decisions ( ), where every decision represents the purchase for the period.
Par ailleurs, il est aussi clair que chaque décision prise à la périodeine dépend au fait que de l’état du
stock at the end of the period i-1. So we have here a sequential decision process (SDP), where the future does not
depends only on the present and not on the past, schematized as follows:

["End of period 1","End of period 2","End of period 3","End of period 4","End of period 5"]

State State of State of State of State of State

initial of you stock stock stock stock final of you
stock stock
0 1 2 3 0 1 2 0 1 0 1 2
step1 step2 step3 step4
2. We assume that throughout this chapter we will only focus on the problems
combinatorial optimization, whose modeling in the form of a PDS is feasible, thus
justifiable by dynamic programming.

Functioning of dynamic programming

Some fundamental concepts associated with a PDS (evolutionary systems)

Let's consider a PDS in n steps modeling a certain combinatorial optimization problem whose
Criterion (objective) is a minimization and evolution from an initial state. towards a final state

For each step we define two sets and as well as two applications and where
set of decisions that can be made at step k
set of states in which the system is at the end of step k
:

( ) ( )
( ) cost associated with decision-making when the system is in the state to the
final stage k-1.
:

( ) ( )

being the transition function that ensures the system moves from one state to another when a
the decision is made
 Application to the inventory management problem

These different concepts applied to the introductory example are:

n=5 (five steps: one for each purchasing period)
For the period k:
possible purchases for period k
possible states of the stock at the end of period k
Let's ask: * +

:
( )

:
( ( )

Representation of a PDS by diagram

Entries

Step 1 outputs Step k-1 exits Step k

Cost: ( ) Cost: ( )

The objective sought in PDS is the establishment of a strategy, based on a sequence of

decision
{ + as such ∑ ( ) be minimal with:

{
( )
Theorem
Any subpolicy of an optimal sequence is also optimal.
Proof
We use reasoning by contradiction. Let's suppose the opposite (i.e. There exists a sub-policy
of an optimal policy, but which is not optimal).
 ( * )
Let it be + an optimal policy of a PDS in n steps (problem of
minimization in our case), and

( ) * + { + an optimal sub-policy of ( )

Let's now suppose that there is a non-optimal sub-policy.

( ) { } { + of ( )

Let's note by ( ( )) of a non-optimal policy of a state , and

by ( ( ))the cost of an optimal state policy So a year ago:

C( ( C( ) ( ( ()) ( () )) ( (( )) ( )
( ( ))

Impossible ( ( )) ( ( )).

Note:
A PDS is therefore characterized by the Markov assumption (the future depends only on the present) and
by the Markov property, also called the principle of optimality (previous theorem).
These 2 characteristics facilitate the calculation of the cost of the optimal policy through relationships.
of recurrence called: forward recurrence or backward recurrence.
Recurrence relations:
Recurrence before:
Let us note by ( ) the cost of an optimal policy of a state toward a state , who is also
the cost of the shortest path of an appropriate graph from a node towards a node .

( )= C ( ( )) where
( * ) + and ( )
The calculation ofwill
( ) be done recursively using the following relation whose validity
is due to the principle of optimality of a DP

() *( ) ( )* ( ) ( +
{
()

( ) cost of an optimal policy of a state towards a state

optimal solution of the restriction of the problem posed at the first k steps
optimal solution of the subproblem of the initial problem.
Example:
Let's take the first example of this chapter, along with its linear model.