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

I’m not sure if I’m wording this right but in a nutshell, my problem is:

I’m modelling potential actions a boat owner can do to their boat. Let’s say he wants to know over the 50 year lifespan of the boat, what’s the cheapest way to maintain the exterior paint.

He has three options:

1. Option 1: first paint at a cost of $1M/boat. Under this option, it is suggested (not a must) to redo the paint at within next 5 years of the previous paint job for the remainder life of the boat. 2. Option 2: If the boat has not been painted in the last 7 years, then it deteriorates to a point where it needs more significant repair at$1.4M. This will include repairs and paint at no extra cost.

3. Option 3: if the boat hasn’t been painted for more than 10 years straight, then some items would have to be replaced at a total cost of \$1.6M/boat. Under this option, he also must paint one year after the Option 3 repair at the same additional cost of$1M/boat.

For the sake of argument and more constraints:

• The surface area of the boat is 400 m2. (Costs should be divided by that number to get the per m2 cost)
• The boat was fully painted 2 years ago, so no paint is required on the boat until period >= 3.
• Minimum repair area = 25m2

At a max budget of \$200K/year for the first 6 years and a max budget of \$300K/yr after, how much should he do from Option 1, 2, and 3 to maximize the condition (painted area)?

Note, I’d like to run this as both a minimization of cost and maximization of condition separate models.

I’m struggling to build the constraints for this model especially the interaction variable on how to build the multiple constraints / variables and summarize them back into results.

EDIT:

Solution must be able to somewhat scale to n boats and i options, and m owners.

EDIT:

Initially I didn't include the deterioration Curve but there is one. I think for simplicity's sake, we can assume that deterioration occurs at a constant 3% a year and one of the constraints is to ensure that no more than 10% is in deteriorating condition.

Furthermore, at Option 1, returns the repaired section to 90% condition rate, option 2 to 95% and option 3 to 100%.

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, 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.

• Thanks for providing a detailed answer. A few questions (1) would this make it a bit more deterministic as there is a do nothing option, (2) how will this scale with multiple boats / owner? (3) Does the node corresponde to “total surface repair” or “partial” as the owner can only work on patches and chunks and not necessarily the hole thing. So one year he can do 100m2 and next year he can do nothing, or he can do 1 x 50m2 repair for this and next year. I really appreciate you putting the time into this Oct 21 '20 at 12:39
• 1) The "do nothing option" is taken into account indirectly, if my understand is correct. An edge from $i$ to $j$ means you do nothing on years between $i$ and $j$. 2) If boats and owners are independent, you can have one such graph per owner, per boat. If an owner has multiple boats, of if a same boat has multiple owners, obviously this does not work anymore 3) Yes in this configuration I considered the whole surface is painted. Oct 21 '20 at 12:47
• So the solution todesn’t work as potentially an owner can have multiple boats but most importantly, the idea is not to do a full repair job in period but rather to only spend up to the maximum amount of \$200k/year as indicated Oct 21 '20 at 12:49
• As warned at the top of my answer, indeed some constraints are ignored, and so as is, the model does not work, it is more of a hint than a complete answer. But you can adapt it so that it works for partial repair jobs. Right now, one node is a full repair job. You can split this node into sub nodes that correspond to partial repair jobs, etc. Oct 21 '20 at 13:04
• You are totally correct there is a deterioration curve that I didn't include in here for simplicity, I have it as a "per year deterioration table" that I created so year (1): deteriorate by 5%, etc. The assumption for now, even incorrect, is that each option treatment takes you back to the original state. In my second version would be to figure out how to return option 1 to 90% state, option 2 to 95% state and option 3 to 100% state. Does that make any sense, and should I add that detail to the question? Oct 23 '20 at 14:02