Multi-period linear dynamic programming with differing in-period dependencies and changes

Disclaimer : this is more of a hint than a complete answer.

You can use the following model as a starting point to make your own model. I am ignoring two items :

• Constraint from option 3:

Under this option, he also must paint one year after the Option 3 repair at the same additional cost of $1M/boat.

• Surface area constraints

You will have to tweak what follows to take the above constraints into account.

This relaxation of your problem can be solved as a shortest path problem in the following directed acyclic graph:

Define one node per year, from $0$ to $50$. Then, define an edge from $i$ to $j$, $i<j$, if it is feasible for the owner to do some maintenance on years $i$ and $j$, and nothing years $i+1, i+2, ..., j-1$.

The cost function on these edges is defined according to the $3$ options. So for example, between nodes $i$ and $i+1,i+2,i+3,i+4,i+5$, the cost is $1$ M dollars (option 1). Between nodes $i$ and $i+7,i+8, i+9$, it is $1.4$ M dollars (option 2). And between nodes $i$ and $i+10$, it is $1.6$ M dollars (option 3).

If the max budget is not satisfied, do not create the corresponding edges.

The shortest path from node $1$ to $50$ determines the cheapest maintenance strategy for the owner of the boat.

EDIT #1

The fact that the above is shortest path problem hints that the problem could probably be solved with dynamic programming. Anyway, one way to address the problem is to consider "states." A state $(t,s)$ is defined by two parameters : $t\in \{1,...,50\}$ and $s\in \{0,1,2,...,400\}$. $t$ denotes the year, and $s$ denotes the surface area that is left unpainted year $t$. In the above answer, partial surface areas were ignored, so all vertices correspond to $(t,0)$ states.

Once you have defined such states, create a grid where nodes represent all possible states. And create an (oriented) edge $(i,j)$ between two vertices $i=(t_i,s_i)$, $j=(t_j,s_j)$ if the following holds:

• $t_j > t_i$,
• $(i,j)$ is a feasible transition in terms of budget,
• $(i,j)$ is a feasible transition in terms of painting strategy

Also, create a source node and link it to all vertices (if feasible), and a sink node, to which all vertices are linked (if feasible). Once you have all the edges, add the corresponding cost. For example, on edge $(i,j)$, if $s_j > s_i$, it means you do nothing, and so the cost is $0$. If $s_j \le s_i $, it means you are painting $s_i - s_j - A_{ij}$ $m^2$, where $A_{ij}$ denotes the surface deteriorated between $t_j$ and $t_i$, at a cost which depends on which option ($1,2,3$) you are using (and so on the length of edge $(i,j)$).

Once you have defined such an oriented graph. A path from the source node to the sink node defines a maintenance strategy, and the shortest path defines the best (cheapest) strategy.

The constraint in option 3 :

Under this option, he also must paint one year after the Option 3 repair at the same additional cost of $1M/boat.

needs to be addressed (I think) with integer programming. You will have to formulate the shortest path problem as a MIP (easy), and add extra constraints and variables to take into account the fact that if you use an edge corresponding to a $10$ year transition, then you must use an edge corresponding to a $1$ year transition the year after.