Dynamic programming (DP) is a creative approach to problem solving that involves breaking a large, difficult problem into a series of smaller, easy to solve problems. By solving this series of smaller problems, we are able to assemble the optimal solution to the initial large problem. A detailed discussion of this model may be found in Developing More Advanced Models.

MODEL:

SETS:

! Dynamic programming illustration (see Anderson,

  Sweeney & Williams, An Intro to Mgt Science,

  6th Ed.). We have a network of 10 cities. We

  want to find the length of the shortest route

  from city 1 to city 10.;

 

! Here is our primitive set of ten cities, where

  F( i) represents the shortest path distance

  from city i to the last city;

 CITIES /1..10/: F;

 

! The derived set ROADS lists the roads that

  exist between the cities (note: not all city

  pairs are directly linked by a road, and roads

  are assumed to be one way.);

 ROADS( CITIES, CITIES)/

  1,2  1,3  1,4

  2,5  2,6  2,7

  3,5  3,6  3,7

  4,5  4,6

  5,8  5,9

  6,8  6,9

  7,8  7,9

  8,10

  9,10/: D;

! D( i, j) is the distance from city i to j;

ENDSETS

 

DATA:

! Here are the distances that correspond to the

  above links;

 D =

    1    5    2

   13   12   11

    6   10    4

   12   14

    3    9

    6    5

    8   10

    5

    2;

ENDDATA

 

! If you are already in City 10, then the cost to

 travel to City 10 is 0;

F( @SIZE( CITIES)) = 0;

 

! The following is the classic dynamic programming

 recursion. In words, the shortest distance from

 City i to City 10 is the minimum over all

 cities j reachable from i of the sum of the

 distance from i to j plus the minimal distance

 from j to City 10;

@FOR( CITIES( i)| i #LT# @SIZE( CITIES):

 F( i) = @MIN( ROADS( i, j): D( i, j) + F( j))

);

END

Model: DYNAMB