# Formulate a problem as Mixed Linear Programming problem

I need to formulate the following problem as a Mixed Integer Linear Programming problem

A farmer needs to establish a 17-year business plan where he will decide when to sell or buy a new truck. The farmer cannot sell the truck before it is two years old but he must sell it by the time it is 5 years old. The price of a new truck is 43,000 USD but loses 10% of its value when bought plus an extra 7% each year. Aditionally, we know that truck prices go up 5% every year with respect to last year.

The annual operating expense of the truck is 1300 USD and each year it goes up by 15%.

So far, the only thing that I have is that I need to minimize the cost - profit function but have no idea how to make it linear or how to even begin to formulate the restrictions. Every similar problem that I have found uses a dynamic programming approach.

From context, I'm assuming that the farmer always needs to have a truck, and the question is when he should replace it.

For the constraints, you can formulate in terms of 17 binary decision variables: $$x_1$$ = "replace in year 1?", $$x_2$$ = "replace in year 2?", ...etc.

"Cannot sell before it is two years old": i.e. cannot replace in two consecutive years, i.e. no two consecutive $$x_i$$ can both be 1. So $$x_1+x_2 \le 1, x_2+x_3 \le 1, ...$$

"Must sell by the time it is five years old": i.e. if we replace it in year $$n$$, must replace again somewhere between years $$n+1$$ to $$n+5$$. That is, if $$x_n=1$$, $$x_{n+1}, x_{n+2},...,x_{n+5}$$ can't all be zero. Since they're all binary variables, this can be expressed as: $$x_n \le x_{n+1}+x_{n+2}+...+x_{n+5}$$. (I'll leave it to you to figure out how to handle the ends of the time period.)

The replacement costs are then a simple linear function of your $$x_i$$, since they only depend on what year you're buying new trucks - the fact that it's an exponential function of the year doesn't matter, it's still linear in your x-variables.

The tricky part of the problem is in how to handle the costs that depend on how long you've had the truck, i.e. operating expenses and -1*resale value.

One way to handle this in a linear framework would be to introduce a set of auxiliary binary variables $$y_{i,j}$$ where $$y_{i,j}=1$$ if and only if there is a truck which is bought in year $$i$$ and sold in year $$j$$.

You can then express the total operating costs and resale minus-costs as a linear function of these $$y_{i,j}$$ (again, be sure to consider end cases!). Now you just need to set some constraints that relate the $$x_i$$ to the $$y_{i,j}$$ in a way that enforces the definition of $$y_{i,j}$$. That is: $$y_{i,j} = 1$$ if and only if $$x_i=x_j=1$$ and none of the values between them are 1. This can be done by two linear inequality constraints which shouldn't be too hard to figure out - if you have difficulty here please comment and I'll expand on it.

This expands the problem size a bit, because you're creating 17^2 = 289 extra auxiliary variables, but if efficiency is a concern you can cut that down quite a bit by noticing that $$y_{i,j}$$ can only be 1 if $$2 \le j-i \le 5$$.

edit: as Rob Pratt suggested in comments, you can eliminate the $$x_i$$ from the problem altogether by applying flow balance constraints: if $$y_{i,j}=1$$ there must be exactly one $$k$$ such that $$y_{j,k}=1$$ and so forth. (Again, glossing over end conditions.)

Keeping the $$x_i$$s in the problem may make it easier to understand what's going on, but being able to transform the problem is a very useful skill and worth developing.

• You were correct in your assumption that the farmer always needs to have a truck. Great answer. It makes perfect sense. Sep 29 '20 at 2:49
• You can think of $y_{i,j}$ as an arc variable in a directed acyclic network with one node per time period. If you introduce flow balance constraints, you don’t need the $x$ variables and associated constraints. It is no coincidence that Bellman’s equation applies to both shortest paths and dynamic programming. The nodes are the states, and the arcs are the actions. Sep 29 '20 at 12:35
• @RobPratt Yeah, the $x_i$ can be eliminated altogether - I left them in because I thought it'd be easier to understand this way, but I might expand my answer to acknowledge this. Sep 30 '20 at 0:15
• @RobPratt So you´re thinking of establishing each year as a node and each arc would be a transition whose value would be the cost of selling and buying that year? Sep 30 '20 at 17:21
• Yes, each year is a node, and there is an arc from $i$ to $j$, where $j\in\{i+2,i+3,i+4,i+5\}$, with arc cost equal to the additional costs incurred by making that transition. Sep 30 '20 at 17:26

The following model gives the purchasing temporal sequence for truck so that the cash flow is optimal within the planning horizon of 17 years. The model requires $$68$$ Boolean variables ($$68=17 \cdot 4$$) and $$17$$ integers variables (1 integer variable for each year). Every year will be designate by means of a pedice $$k=1, 2, \cdots, m=17$$.

For each year the possible choices are basically two:

“sell” or “buy” the truck in the k-th year

By the contest, there are four kind of available plans:

1-st plan: keep the truck $$2$$ years, $$t_1=2$$;

2-nd plan: keep the truck $$3$$ years, $$t_2=3$$;

3-rd plan: keep the truck $$4$$ years, $$t_3=4$$;

4-rd plan: keep the truck $$5$$ years, $$t_4=5$$.

We designate by means of a pedice $$j=1, 2, \cdots , 4$$ the kind of adopted plan for each year. As a consequence, we need $$17 \cdot 4 = 68$$ variables in order to define all possible decisions. Let introduce the Boolean variable $$x_{k,j}$$:

• $$x_{k,j}=1$$ if in k-th year I decide to keep the truck as many years as specified by the j-th plan
• $$x_{k,j}=0$$ if in k-th year I decide to not keep the truck as many years as specified by the j-th plan.

For example, the sequence $$x_{1,3}= x_{2,3}= \cdots = x_{k-1,3}= x_{k+1,3}= \cdots = 0$$ and $$x_{k,3}=1$$ is suitable to describe the choice of buying the truck in year k and keeping it 3 years.

Unitary Time Period

The planning horizon $$T$$ is divided into a finite set of $$m$$ instants: $$t_{k+1}= t_k + \Delta h_k$$ where $$K=0,1, \cdots, m-1$$. The discretization step will be chosen constant and with an extent of 1 year: $$\Delta h_k = \Delta h = 1$$ year. In this way, $$T= \Delta t_1 + \cdots + \Delta t_m = m \cdot \Delta h$$ and in our case study we have $$m=17$$ with $$t_0=0$$.

Temporal Constraints

We introduce $$m=17$$ equations and variables $$A_k$$ that track in each year how long the truck will be kept for the future years.

$$A_1 = \sum_{j=1}^{4} x_{1,j} \cdot t_j$$

$$A_2 = A_1 - 1 + \sum_{j=1}^{4} x_{2,j} \cdot t_j$$

$$\vdots$$

$$A_m = A_{m-1} - 1 + \sum_{j=1}^{4} x_{m,j} \cdot t_j$$

For example, in the first year if we decide to buy the truck and to keep it for three years (2nd plan), it results: $$A_1 = \sum_{j=1}^{4} x_{1,j} \cdot t_j = t_2 = 3$$ because $$x_{1,2}=1$$ and $$x_{1,1}=x_{1,3}= x_{1,4}= 0$$. In order to impose that in every year there is a truck in service, we add further $$m$$ constraints: $$A_k \geq 1 \quad \forall k=1,\ldots,m$$.

Finally, the constraint $$\sum_{k=1}^{17} \sum_{j=1}^{4} x_{k,j} \cdot t_j \leq 17$$ makes sure that all investment choices are made within the fixed planning horizon $$T$$ and generate cash flows with maturity no later than horizon planning $$T=17$$.

In order to avoid the unacceptable situation of buying a truck when the plan of the previous truck has not yet come to an end, we introduce $$m-1$$ additional constraints as follows:

$$\left\{ \begin{array}{l} \sum_{j=1}^{4} x_{1,j} \cdot t_j \leq (1 - \sum_{j=1}^{4} x_{2,j} ) \cdot M +1 \\ A_{1} -1 + \sum_{j=1}^{4} x_{2,j} \cdot t_j \leq (1 - \sum_{j=1}^{4} x_{3,j} ) \cdot M +1 \\ \vdots \\ A_{m-2} -1 + \sum_{j=1}^{4} x_{m-1,j} \cdot t_j \leq (1 - \sum_{j=1}^{4} x_{m,j} ) \cdot M +1 \\ \end{array} \right.$$

where $$M > \max_j t_j$$

Whenever $$A_{k-1} = A_{k-2} -1 + \sum_{j=1}^{4} x_{k-1,j} \cdot t_j \geq 2$$ we have $$(1 - \sum_{j=1}^{4} x_{k,j} ) \cdot M +1 = M+1$$, so it implicitly requires that in the following period $$\sum_{j=1}^{4} x_{k,j} = 0$$ for every $$j$$. On the other hand, suppose at time $$k$$ we buy a truck with regards to $$\tilde j$$ plan earlier than expected, that is when being $$A_{k-2} \geq 2$$ then $$A_{k-2} -1 + t_{\tilde j} \leq 1$$ holds. This last inequality is not possible if $$A_{k-2} \geq 2$$. As a result, it is not possible to buy a truck before sell the previous one. Of course, it is possible buy a truck in $$k-1$$ period if $$A_{k-2} =1$$.

Objective Function

$$\max (revenue - cost) = \max (revenue) + \max (-cost) = \max (revenue) - \min (cost)$$

revenue $$=\sum_{k=1}^{17} r_k ( \sum_{j=1}^{4} x_{k,j})$$

cost $$=\sum_{k=1}^{17} c_k ( \sum_{j=1}^{4} x_{k,j})$$

where $$r_k$$ and $$c_k$$ for $$k=1, \cdots, 17$$ play the role of coefficients. These coefficients can be easily calculated as:

• $$r_k= 45000 \cdot (1-0.10) \cdot (1-0.07)^{k-1}$$
• $$c_k= 45000 \cdot (1+0.05)^{k-1}$$