Optimización de la lista de jugadores de béisbol

Question

Estoy intentando optimizar mediante programación una lista de jugadores de Fantasy Baseball que requiere un número fijo de jugadores por posición (2 receptores, 5 jardineros, etc.) y tiene una restricción salarial (el precio total del draft no puede superar los n dólares). El éxito de la lista se basa en la producción combinada del equipo en las categorías de bateo (o lanzamiento).

Tengo proyecciones de las contribuciones estadísticas estimadas de cada jugador, a partir de las cuales puedo determinar (utilizando la puntuación estándar) su valor aproximado. Para este ejercicio, podemos suponer que he puesto el precio adecuado a cada jugador.

Para esta liga en particular, hay seis categorías de bateo (HR, RBI, Bases Robadas, etc)... y las proyecciones que tengo me permiten determinar cuánto contribuirá cada jugador dentro de cada categoría estadística.

Dados los 154 jugadores que se pueden draftear, y requiriendo 14 bateadores por equipo - da un asombroso número de 26.327.386.978.706.200.000 combinaciones diferentes. Obviamente, no quiero intentar un método de fuerza bruta para probar cada combinación posible de jugadores para determinar una lista óptima. (Tendría muchas listas demasiado caras, y muchas listas que valdrían 14 dólares (o menos)).

Está claro que tengo que ser más inteligente en esto y estoy buscando algún tipo de orientación para empezar.

Lo que he probado:

Mi primer intento de optimizar la lista fue seleccionar los MEJORES x jugadores (donde x = el número de jugadores necesarios en una posición). Una vez que tuve esos 14 jugadores, estaba MUY por encima del salario máximo, así que determiné en qué categoría era más fuerte y reduje al mejor jugador de esa categoría con el siguiente mejor jugador del grupo (sustituyendo, por ejemplo, a Miguel Cabrera por Evan Longoria). A continuación, volví a calcular el valor de la plantilla (que seguía estando muy por encima) y, de nuevo, determiné la categoría "más fuerte" y traté de sustituir al mejor jugador de esa categoría por el siguiente mejor jugador de la reserva no asignada.

El proceso se repite hasta que la suma total de la plantilla está justo por debajo del umbral salarial. Estoy LIGERAMENTE contento con los resultados... pero me pregunto si no hay una mejor manera de trabajar a través de posibles combinaciones de roster de una manera que:

Maximiza cada categoría constituyente (hay poco valor en añadir Home Runs por ejemplo, si ya tienes suficiente para ganar - y eres deficiente en Bases Robadas). Así que "nivelar" las categorías constituyentes es importante. Te mantiene lo más cerca posible (sin sobrepasar) el coste total de la plantilla. Una vez más - Estoy buscando dirección - alguien más competente en matemáticas para decir "esto es claramente un problema de mochila y aquí es cómo usted debe estar pensando a través de ...."

Soy programador... no matemático y cualquier ayuda que este grupo pudiera proporcionarme sería muy apreciada.

Saludos

[Nota: Movido de mathoverflow.net por indicación de la comunidad].

Answer 1

A priori, parece un problema de programación entera, pero no has especificado qué es lo que quieres optimizar. Es decir, si enumeramos los jugadores disponibles como $i=1,2,3,\ldots,N(=154)$ , dejemos que $p_i$ ser jugador $i$ y que $x_i=1$ ou $0$ indique si draftea al jugador $i$ o no, entonces dos restricciones son

$$\sum_i x_i=14\quad\text{and}\quad\sum_ip_ix_i\le C$$

donde $C$ es el límite salarial. Habrá restricciones adicionales correspondientes a los requisitos sobre el número máximo o mínimo de receptores, jardineros, etc. Pero la cuestión es cómo describir matemáticamente las "contribuciones" combinadas de los jugadores.

Por ejemplo, supongamos que limitamos las cosas a dos categorías, digamos home runs y bases robadas, y supongamos que el jugador $i$ en cada categoría es $h_i$ y $s_i$ respectivamente. Podemos definir

$$H(x_1,\ldots,x_N)=\sum_i h_ix_i\quad\text{and}\quad S(x_1,\ldots,x_N)=\sum_is_ix_i$$

Pero todavía necesidad de especificar una función objetivo $W(H,S)$ que optimizar, y parece que esa función, sea cual sea, va a ser no lineal (ya que has indicado que hay rendimientos decrecientes para cada categoría). En resumen, aún no has planteado tu pregunta de forma que pueda responderse matemáticamente.

Answer 2

Yo quizás miraría los resultados de ligas pasadas y vería qué posiciones contribuyen a la victoria general de la liga (RP, 1B, OF) y qué categorías (W, RBI, WHIP, SB). Esto es similar al hockey, donde un jugador obtiene una puntuación +/-.

Answer 3

Tengo un Algoritmo Genético (AG)/enfoque de fuerza bruta que es muy rápido. Es un AG estándar, pero la forma de hacerlo más rápido es mediante la reducción de datos.

La clave para que vaya más rápido es mirar a tus jugadores por conjuntos. En el ejemplo que has dado necesitas

2 receptores 5 jardineros

Abordaré las demás posiciones más adelante.

Como sabrás, el número de combinaciones posibles de estas dos posiciones es enorme. Suponiendo 30 equipos, 3 jardineros por equipo. Tienes 90 posibles jugadores de campo entre los que elegir 5. Es decir, 90*89*88*87*86=~5 mil millones de combinaciones únicas. Si incluimos a los receptores, la cifra asciende a billones.

Sin embargo, puedes eliminar combinaciones mirando el coste y el rendimiento de los jugadores por punto de precio por posición.

Primero reducimos los datos. Veamos los 5 jardineros. Usando un AG puedes criar soluciones candidatas de cinco jardineros para cada punto de precio. Con cada punto de precio me refiero a todos los puntos de precio posibles (calculados a continuación). El número de puntos de precio es mucho menor que el número de combinaciones únicas de jardineros, así que esto elimina un montón de posibilidades.

En este ejemplo, nuestro universo es de sólo 2 receptores y 5 jardineros. Supongamos que nuestro presupuesto es de 100 dólares y que hay muchos receptores y jardineros que sólo cuestan 1 dólar cada uno. Eso significa que lo máximo que podemos pagar por nuestros jardineros es 98 pavos usando la fórmula (presupuesto total) - (cantidad mínima gastada en receptores) = (cantidad que queda para los jardineros) o 100 - 2 = 98 (disponible para los jardineros) y el presupuesto más bajo para los jardineros es 5 pavos (1 por cada jardinero). Utilizando un AG, crear soluciones para cada uno de los 98 - 5 = 93 puntos de precio.

Las soluciones finales sólo requieren 2 receptores, por lo que se puede utilizar la fuerza bruta para dar con el mejor dúo de receptores para todos los precios. Como ya se ha dicho, lo mínimo que se puede gastar en receptores son 2 dólares. Lo máximo que puedes gastar es 100 - 5 (para los jardineros) = 95 dólares. En consecuencia, hay 93 puntos de precio (95 - 2 = 93) para los que se necesitan dúos de receptores óptimos.

Ahora haz más reducción de datos: mira tus combos de posiciones individuales. En cada punto de precio, busca combinaciones que tengan un rendimiento menor y un coste mayor que otras combinaciones. Por ejemplo, digamos que tienes un grupo de 5 jardineros que te da 1000 puntos de fantasía y te cuesta 90 dólares. También tienes un quinteto que te devuelve los mismos puntos de fantasía por sólo 80 dólares. Puedes eliminar el quinteto más caro y de menor rendimiento porque nunca formará parte de la solución óptima. Nunca pagarías más por menos.

Tenga en cuenta que si tiene criterios adicionales, como que quiere un quinteto apilado, podría quedarse con el grupo más caro, pero eso queda fuera del alcance de esta explicación.

Después de toda esta reducción de datos, puede utilizar la fuerza bruta para encontrar las combinaciones de dúos de receptores y quintetos de jardineros que le proporcionen el mejor rendimiento por punto de precio.

Sólo hay dos grupos, receptores y lanzadores, por lo que el número máximo (si no se eliminó ningún grupo en los pasos anteriores) de combinaciones únicas son 93 dúos de receptores X 93 quintetos de jardineros = ~10.000, lo que es muy inferior a los billones de posibilidades que contemplabas en un principio.

Entonces se eliminan los combos quinteto x dúo, como el anterior, que nunca podrían formar parte de una solución óptima. Al final, debería haber un máximo de 93 soluciones, una para cada nivel de precios.

Ahora puedes pensar en estos dúos fusionados de catcher y quintetos de outfield como un bloque una especie de posición OF-CA y utilizar el bloque con otros combos que explores (como pitchers, infielders, etc.).

Esto es muy rápido porque estás haciendo GA con conjuntos pequeños (dúos y quintetos). Si tienes un ordenador rápido puedes hacerlo en milisegundos. La parte de fuerza bruta debería ser igual de rápida si has hecho la reducción de datos correctamente.