Formulate a problem as Mixed Linear Programming problem

Question

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.

Answer 1

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.

Answer 2

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}$