# 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. – PLanderos33 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. – RobPratt 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. – Geoffrey Brent 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? – PLanderos33 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. – RobPratt 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}$$