Minimizar la desviación estándar de los valores totales de los grupos de elementos (¿optimización?) en r

Question

Soy totalmente novato, pero creo que lo que busco es ayuda con un problema de optimización.

Tengo un conjunto de unos 26 artículos, cada uno con un valor determinado. Quiero distribuir estos artículos en 8 grupos de la forma más equitativa posible, teniendo en cuenta que una distribución perfectamente equitativa no es posible debido a los valores individuales de los artículos. Creo que una forma de medir la igualdad de los artículos en los grupos es tomar la desviación estándar de las sumas de los valores de los artículos en cada grupo.

¿Existe algún paquete en R que pueda ayudarme a minimizar la desviación estándar de estas sumas alterando la asignación de elementos a los grupos?

Por cierto, se trata de un problema de "división del patrimonio", en el que cada artículo tiene un valor conocido, y no se puede hacer una puja/subasta.

Answer 1

Hay una variedad de medidas de uniformidad de las sumas (valores de grupo). Por ejemplo, una alternativa es intentar minimizar la diferencia entre la suma mayor y la menor.

Minimizar la desviación estándar es lo mismo que minimizar la varianza.

Sin embargo, la media de las sumas es fija, por lo que minimizar la varianza es lo mismo que minimizar la suma de los cuadrados de los valores de los grupos .

Esto se acerca un poco más a un problema de optimización "estándar".

Está algo relacionado con el Problema de programación de un taller de trabajo y una serie de otros problemas.

Hay varios programas de programación de trabajos, algunos de los cuales podrían funcionar en tu problema, pero normalmente tienden a centrarse en minimizar el tiempo máximo de finalización (que correspondería a minimizar el conjunto más grande, lo que puede no darte una buena solución).

De un vistazo rápido parece que el partitions en R puede generar particiones por ti - pero desafortunadamente el número de posibles particiones va a ser enorme en tu caso, así que tendrás que conformarte con algún algoritmo aproximado (de forma similar a algunos de los problemas de bin-packing, por ejemplo). [Los algoritmos aproximados pueden generar a menudo muy buenas soluciones].

Puede haber algún valor en esto:

http://www.colorado.edu/education/DMP/fair_division.html

pero parece que se fija sobre todo en las soluciones de licitación.

Si tiene un problema mixto (es decir, que incluye activos divisibles como el efectivo), su trabajo debería ser más fácil.

Se podría decir que hay que empezar con alguna solución razonable y utilizar, por ejemplo, la búsqueda tabú o el recocido simulado o algo así para intentar mejorarla.

Si se trata de un problema puntual, ¿puedes publicar algunos números proporcionales a los valores (no afectará en nada multiplicarlos por alguna constante arbitraria como 1,375)?

Answer 2

Esto se conoce como el "problema de la partición" y se resuelve preferentemente con un programación dinámica enfoque. Puedes leerlo en el capítulo 8.5 de "The Algorithm Design Manual" de Steven Skiena. Y puedes encontrar una implementación en R para minimizar la varianza en el hilo "optimization challenge" de R-help en enero de 2010.

EDITAR : Lo siento, de alguna manera interpreté mal la tarea, asumiendo que la secuencia de valores jugaría un papel. Como una especie de compensación mostraré cómo resolvería esto como un problema de mochila múltiple, reduciendo las capacidades de la mochila hasta que no se encuentre ninguna solución.

library(adagio)                     # contains a multiple knapsack solver
set.seed(7531)
w <- sample(1:100, 26)              # 26 items used as weights (integers)
p <- rep(1, 26)                     # with equal profits all

t <- 200; k <- rep(t, 8)            # 8 knapsacks with equal capacities
sol <- mknapsack(p, w, k, bck = 1)  # starting with capacity 200
while (all(sol$ksack > 0)) {        # diminish capacity until not all
    t <- t-1; k <- rep(t, 8)        # items can be packed
    Sol <- sol                      # keep the last feasible solution
    sol <- mknapsack(p, w, k, bck = -1)
}                                   # will take a few seconds to minutes

y <- numeric(8)                     # find weight in each knapsack
for (i in 1:8) y[i] <- sum(w[Sol$ksack == i])
y                                   # 161 161 160 161 161 161 159 161

Esto no conducirá en todos los casos a una solución de mínima varianza, pero se acercará mucho a ella.

Answer 3

Yo diría que una solución (no puedo demostrar que sea óptima) para este problema es ordenar los elementos de menor a mayor y partir de ahí. En esta disposición, los elementos que se encuentran junto a otros siempre aportarán la menor contribución posible a la SD global.

Tuve un problema similar y lo resolví de esta manera. Sin embargo, tuve la ventaja de tener un tamaño de grupo constante. El método para su problema todavía tendría que evaluar todos los grupos posibles..