What (if any) optimization problem do I have?

Question

Suppose I owe (no interest) 300 and 600 dollars with due dates in 12 and 24 months, respectively. The trivial idea is to consider both debts independently and put aside monthly $\frac{300}{12}=25$ dollars for the first debt and $\frac{600}{24}=25$ for the second one. Therefore, I have to put aside \$50 each of the first 12 months and \$25 in the second 12 months which is rather imbalanced.

Intuitively it is clear that the smarter idea is to put aside $\frac{300+600}{24}=37.5$ monthly for the whole 24 months interval: I have $37.5 \cdot 12 = 450$ dollars in 12 months which is enough to pay the first debt ($300$) and I'm left with $450-300=150$ dollar for the second debt. For the second 12 months I get another $37.5 \cdot 12 = 450$ bucks. $150 + 450 = 600$ and I'm good to go.

It is also clear (or not?) that the procedure above makes sense if the "later" debt is larger than the "earlier" one: if I would have to pay \$600 first (in 12 months) there were no chance I put aside less than 50 dollars per month...

Now a more complex example. Suppose I have several debts (just random numbers):

debt (\$)	due in (months)
600	3
160	4
1200	6
1400	7
900	9
300	10
1800	12

For each month (from 1 to 12) I want to know the smallest possible amount of money I have to put aside taking all the listed debts into account.

Is it an optimization problem? If so, to which of the well known ones can it be boiled down?

Answer 1

Let $n$ be the longest term (in months) of any of the loans.

Let $D_1,D_2,...,D_n$ be the amount due in month $n$. (Some of these values may be $0$.)

Let $C_k$ be the total cumulative amount due of all loans through month $k$.

Let $A_k=\frac{C_k}{k}$. This represents the average amount due over the first $k$ months.

In your second example, we have the $D$s being $0,0,600,160,0, 1200,1400,0,900,300,0,1800$. (All amounts dollars.)

So the $C$s (cumulative totals) are $0,0,600,760,760,1960,3360,3360,4260,4560,4560,6360$.

The $A$s are $0,\;0,\;200,\;190,\;152,\;326.67,\;480,\;420,\;473.33,\;456,\;414.55,\;530$

In this example, because the largest average is last, that amount ($530$) represents the amount you should deposit each month.

However, more generally, find the maximum $A_k$ and for the first $k$ months, deposit that amount. At the end of those $k$ months, you will have exactly paid off your loans through those $k$ months (with no leftover money saved for payments). Then recalibrate (in the same way) for the remaining months. Your subsequent deposit amounts will be lower. Depending on how many maximum averages you run into, you may have to recalibrate several more times.

Answer 2

So it looks like what you want to do is pay the same amount in total every month over the horizon of the longest maturity (not sure about the significance of this; as mentioned in the comments, in real life it makes sense to wait to pay in full at the maturity date, but I'll go along with your premise).

To formalize the question, you have loan $i$ in the amount $A_i$ with a maturity of $T_i$ months, $i=1,...,n.$ Without loss, order the loans by maturity so $T_1\leq T_2\leq...\leq T_n.$ You want to find the amount you pay toward loan $i$ in month $t$, given by $a_{i,t}$, satisfying the following:

-Nonnegativity: $a_{i,t}\geq 0$

-Non-delinquency: $\sum_{t=1}^{T_i} a_{i,t}=A_i.$

-No excess payments: $a_{i,t}= 0,\quad \forall t>T_i$

-Equal monthly payments: $\sum_{i=1}^n a_{i,t}=\frac{1}{T_n}\sum_{i=1}^n A_i$

In your example, these conditions imply a payment schedule like this (blanks are TBD):

where yellow cells are the row sums and green cells are the column sums. Note how there would be no solutions if, for instance, the first loan matured in 1 month instead of 3 months.

In general, this problem can have no solutions or multiple solutions (indeed, infinitely many if payments are on a continuum). One solution (somewhat arbitrary) is to start with the loan with the shortest maturity and pay as much as possible on the first month and whatever cannot be paid in the first month, carry over to the next month and pay as much as possible etc. until the non-delinquency constraint for the shortest maturity loan is met. Then proceed to the loan with the next shortest maturity and do the same (I am describing the procedure informally; you can write a formal algorithm). For your example, this procedure gives a payment schedule like this:

This solution pays as much as possible in earlier months for short term loans. Equivalently, it pays as much as possible in later months for long term loans. You can consider other solutions as desired.