Optimization theory and applications assessed assignment 

3: dynamic programming 

The objective: the objective of this assessed assignment is to devise a software package in Matlab or 

Python which will be used to solve dynamic programming (DP) problems. These two packages will 

have input fifiles which encode the dynamic programming task under consideration and correspondingly 

two output fifiles. One output fifile will give the individual steps involved in the computation and the 

second fifile will give the solution found. 

Deadline: 1:00 PM on Friday 10th December 2021. This is the Friday of the penultimate week 

of term. This is the fifinal assessment for this unit. 

The two dynamic programming tasks to consider are worth 10 marks each. They are as follows: 

Task 1: write a dynamic programming package to fifind the shortest route through a network. 

The programme should be initialised to fifind a solution to a problem of the form of Figure 28, where 

a network is presented with a number of stages and label links indicating the cost of going from one 

node to another. The task described there is to go from an node A to the line BC. The relevant 

dynamic programming method to use is described on page 105 of the course notes and is a Bellman 

or functional equation. The program should be initialised to solve the problem stated on pages 104 

and 105 of the course. However it should be generalizable to solve an arbitrary problem of this form 

with a number of stages between a node A and line BC, of this form. The number of stages should 

not exceed 6 and there are two choices (up or down) at each node. 

Task 2: write a program to solve the capital budgeting problem as stated on page 106 of the 

course notes with the Bellman or functional equation as stated on page 107 of the notes. The program 

should be initialised to solve the problem described in Table 5 at the start of section 5.2 (a capital 

budgeting problem). As for the shortest route through network problem, however, the program should 

be general and flflexible enough to handle capital budgeting problems of up to four stages and four nodes 

per stage. 

The materials will be uploaded to the assessment pages on Blackboard for this course and will have 

the following components: 

(1) The source code for your DP solvers, e.g. network.py and 

capbud.py. 

(2) The input fifiles, inputnetwork.txt and inputcapbud.txt 

which will be initialised to the net

work and capital budgeting problems mentioned in the notes in chapter 5. How to present 

the relevant information to the program is left up to you, but you include text information in 

1these input fifiles which gives the relevant information of number of stages, and all other relevant 

information. 

(3) Output fifiles called lognetwork.txt and logcapbud.txt for the two DP tasks considered. These 

log fifiles should present the internal working steps of the two methods. 

(4) Two output fifiles called solutionnetwork.txt and solutioncapbud.txt which gives the solu

tion, with any extra text clearing indicating the nature of the solution. 

(5) A readme.txt fifile which gives any extra information as to how to run your program, how to 

alter the input, and interpret the log fifile and solution fifiles, as appropriate. 

For this smaller assessed assignment there is no associated research project. 

The mark distribution and assessment of the coursework: Both these subprojects have 10 

marks each and the marking schedule is similar (the total for this assignment is then 20 marks). In 

both cases the marks are as follows: 5/10 for the correct solution of the problems mentioned under 

shortest route through a network and the capital budgeting problem as described in chapter 5, and 5/10 

marks each for the ability to handle a more general problem of these types, with a flflexible number of 

stages and nodes per stage. Of the 10 marks assigned to each subproject, 6 marks (3 each) go with 

correct execution of the program according to the log fifile and 4 marks (2 each) for the correct answer. 

2