Formulación matemática de un problema de optimización

Question

Tengo el siguiente problema de optimización.

Hay N números enteros, $a_{i},a_{i+1},\dots,a_{n}$ donde $a_{i} > 0$ .

Tenemos que dividir estos números en d Los conjuntos y las particiones deben ser contiguos. Por favor, asuma una combinación válida de $N$ y $d$ . Por ejemplo, una partición válida sería como (suponiendo $N = 10$ y $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}$

Ahora, en cada partición, habrá un valor máximo, llámalo como $a^{k}$ para el $k$ La tercera partición en la que $1 \le k \le d$ . Tenemos que minimizar el $\sum_{k = 1}^{d} a^{k}$ .

Así que mi enfoque fue dividir este problema de optimización en subproblemas:

por ejemplo, si $f(i,k)$ = Suma óptima cuando dividimos $1$ a $i$ números en $k$ particiones.

Entonces, $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$ .

Con esta formulación, podemos calcular primero los subproblemas más pequeños y luego construir los subproblemas más grandes.

Pero, no considero discutir el enfoque anterior aquí, debido a su naturaleza algorítmica. Quiero saber si hay otra manera de manejar este problema de optimización de una manera más matemática en lugar de tratamiento algorítmico.

Perdón por el término "vía matemática", porque no conozco tales técnicas si existen.

Gracias.

Answer 1

Se puede resolver el problema mediante programación lineal entera de la siguiente manera. Para cada par $(i,j)$ con $1 \le i \le j \le n$ y la variable de decisión binaria $x_{i,j}$ indicar si una parte $\{a_i,\dots,a_j\}$ aparece en la partición. El problema es minimizar $$\sum_{i,j} \max(a_i,\dots,a_j) x_{i,j}$$ con sujeción a \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} Restricción $(1)$ selecciona exactamente $d$ partes. Restricción $(2)$ obliga a que cada elemento aparezca exactamente en una parte.