I have the following optimization problem at hand.
There are N integer numbers, $a_{i},a_{i+1},\dots,a_{n}$ where $a_{i} > 0$.
We need to partition these numbers into d sets and partitions should be contiguous. Please assume valid combination of $N$ and $d$. For example, a valid partition would be like (assume $N = 10$ and $d = 3$):
$a_{1}, a_{2}, a_{3} \quad |\quad a_{4}, a_{5}, a_{6} \quad |\quad a_{7}, a_{8}, a_{9},a_{10}$
Now, in each partition, there will be a maximum value, call it as $a^{k}$ for the $k$th partition where $1 \le k \le d$. We need to minimize the $\sum_{k = 1}^{d} a^{k}$.
So, my approach was to break down this optimization problem into subproblems:
for example, If $f(i,k)$ = Optimal sum when we partition $1$ to $i$ numbers into $k$ partitions.
Then, $f(i,k+1) = \text{min}\left[f(j,k) + \text{max}\left(a_{j+1},a_{j+2},\dots,a_{i} \right) \right] \quad \text{where} \quad j < i$.
With this formulation, we can calculate smaller subproblems first and then construct the bigger subproblems.
But, I don't consider discussing the above approach here, because of its algorithmic nature. I want to know if there is another way of handling this optimization problem in a more mathematical way instead of algorithmic treatment.
Sorry for the term "mathematical way", because I am not aware of such techniques if exist.
Thanks!
You can solve the problem via integer linear programming as follows. For each pair $(i,j)$ with $1 \le i \le j \le n$, let binary decision variable $x_{i,j}$ indicate whether part $\{a_i,\dots,a_j\}$ appears in the partition. The problem is to minimize $$\sum_{i,j} \max(a_i,\dots,a_j) x_{i,j}$$ subject to \begin{align} \sum_{i,j} x_{i,j} &= d \tag1 \\ \sum_{i,j: i \le k \le j} x_{i,j} &= 1 &&\text{for $k\in \{1,\dots,n\}$} \tag2\\ \end{align} Constraint $(1)$ selects exactly $d$ parts. Constraint $(2)$ forces each element to appear in exactly one part.