TecNoticias, tu portal de información

Foto de Taylor Vick en Unsplash

Formulación y solución de un problema de granja de servidores estocásticos de dos etapas

La programación estocástica (SP) es un marco para modelar problemas de optimización que involucran incertidumbre [1]. En muchos casos, los modelos SP toman la forma de un problema de dos etapas. La primera etapa consiste en encontrar las decisiones deterministas óptimas. Estas decisiones se basan en información que sabemos que es cierta (también conocidas como decisiones aquí y ahora). La segunda etapa consiste en tomar decisiones que se basan en la aleatoriedad (también llamada decisión de recurso), dadas nuestras decisiones de la primera etapa. El problema de optimización tiene como objetivo minimizar la pérdida (o maximizar la ganancia) que resulta de la decisión de la primera etapa más la pérdida esperada que resulta de la decisión de la segunda etapa. Matemáticamente, esto se puede escribir en el siguiente formato:Formulario general 2SP (Imagen del autor) En este artículo, demostraré cómo formular y resolver uno de estos problemas usando Gurobi. Pongamos este marco en perspectiva con un ejemplo: un problema de granja de servidores. Digamos que estamos tratando de diseñar una granja de servidores para nuestra empresa y necesitamos instalar núcleos de CPU, GPU y TPU para ayudar a manejar los recursos informáticos de nuestra empresa dada la cantidad de espacio que tenemos y nuestro presupuesto inicial para comprar servidores. Tenemos una estimación general de la demanda del próximo mes para cada recurso y las distribuciones que siguen. En aras de la simplicidad, ignoraremos los meses futuros después del próximo mes (aunque es posible hacer un programa estocástico de múltiples etapas para manejar esto). Ejecutar los servidores en el futuro costará una pequeña cantidad, pero si no lo hacemos Para satisfacer la demanda, tendremos que aprovechar los recursos de computación en la nube, lo que aumentará significativamente nuestros costos operativos.
En este ejemplo, nuestra decisión de la primera etapa (la decisión del aquí y ahora) es la cantidad de cada recurso a comprar. La decisión de la segunda etapa (recurso) es la cantidad de cómputo en la nube a comprar. Nuestro objetivo es minimizar el costo operativo de la granja de servidores. Este problema de optimización se puede escribir de la siguiente manera:Formulación Server Farm 2SP (Imagen del autor) Donde x representa la cantidad de cada núcleo que compraremos, y representa la cantidad de cómputo en la nube que aprovecharemos, i son nuestros costos de instalación, B es nuestro presupuesto de instalación, s es el tamaño de los núcleos , S es nuestro espacio disponible, c son nuestros costos de computación en la nube y d(xi) es nuestra demanda aleatoria. Para resolver el problema anterior, implementaremos una técnica llamada aproximación de promedio de muestra [2]. Este método implica generar un gran número (K) de posibles realizaciones (escenarios) de la variable aleatoria a través del muestreo Monte Carlo y tratar cada realización como un subproblema individual. [2]. Esto ayuda a discretizar la aleatoriedad y, por lo tanto, la hace solucionable sin perder demasiada fidelidad de la información. Esto significa que en lugar de tener solo 1 conjunto de variables de segunda etapa, tendremos K variables y la expectativa de nuestro valor de segunda etapa es el valor promedio de nuestras realizaciones. Con esto, nuestra formulación cambia a:Reformulación de SAA (Imagen del autor) Si bien esta formulación se puede implementar en una variedad de lenguajes de programación y solucionadores de programación lineal (por ejemplo, SCIP, CPLEX, CVXPY), nos centraremos en resolver este problema utilizando Gurobi: Solucionador de programación matemática de última generación. Gurobi tiene API para lenguajes como Python, MATLAB, R y Java, pero la mayoría de sus usuarios prefieren usar la API de Python [4], por lo que lo usaremos aquí. Primero, importaremos nuestros paquetes (numpy y gurobipy) e inicializaremos (inventaremos) los datos para nuestro problema. En este problema, i es el costo de inversión, es decir, el espacio que ocupa cada elemento. , Bis nuestro presupuesto, y Sis nuestro máximo espacio. Otra variable a destacar es la demanda en cada escenario d_xi. Luego podemos usar Gurobi para resolver nuestro problema. Primero, definiremos nuestro modelo con gp.model(), estableceremos el objetivo (minimizar) e inicializaremos nuestras variables de decisión. Como puede ver en los ejemplos anteriores, tanto nuestra demanda (d_xi) como nuestra variable de decisión de segunda etapa (y) no son vectores unidimensionales, sino una matriz, ya que ambos tienen un índice de escenario en nuestra formulación. Después de esto, podemos definir nuestra función objetivo: una cosa buena de Gurobi es que admite operaciones de multiplicación de matrices numpy al definir restricciones y objetivos, lo que facilita la codificación si piensa en multiplicaciones de matrices (por ejemplo, i @ x). Gurobi también admite operaciones de suma, lo que también reduce la barrera de entrada. Aquí calculamos el costo de la primera etapa, luego tomamos el costo promedio de la segunda etapa. Ahora podemos pasar a definir nuestras restricciones: La primera línea de código asegura que el costo de instalar servidores internos no exceda nuestro presupuesto B. La segunda line se asegura de que solo compremos tantos servidores como tengamos espacio. La tercera línea de código garantiza que la cantidad de servidores instalados y la cantidad de recursos de cómputo en la nube en el escenario k aprovechados sean suficientes para satisfacer la demanda en el escenario k. Ahora que el problema está completamente definido, podemos simplemente resolverlo y tomar nuestra decisión óptima llamando a m.optimize(): Los valores óptimos de las variables se almacenan en cada variable que definimos y se puede acceder a ellos a través de variable_name.x. Si bien podríamos haber obtenido los valores óptimos para las variables x e y, solo nos importan las decisiones que podemos tomar ahora (x). Este enfoque nos brinda una solución de alta calidad, pero tiene inconvenientes. El primer inconveniente es que a medida que aumenta el número de escenarios, el modelo se volverá exponencialmente más difícil de resolver. Por ejemplo, solo necesitábamos tomar 6 decisiones verdaderas, pero el uso de la aproximación del promedio de la muestra hizo que nuestro modelo tomara 153 decisiones (3 de primera etapa, 3 de segunda etapa para 50 escenarios). Esto significa que los algoritmos de descomposición (como la descomposición de Benders para SP lineales) [3]) a menudo deben usarse para paralelizar el cálculo. Otra consideración es que, desafortunadamente, Gurobi no es software libre. Si bien Gurobi ofrece una licencia académica que muchos estudiantes e investigadores aprovechan, las personas que no están afiliadas a una universidad pueden tener dificultades para acceder a este software. Una alternativa de código abierto a Gurobi es SCIP [5]. Ambos comparten un lenguaje de modelado similar para que los usuarios de Gurobi puedan adaptarse fácilmente a SCIP y viceversa. Elegí demostrar este concepto con Gurobi en lugar de SCIP debido a una preferencia personal junto con el rápido rendimiento del solucionador de Gurobi. Eso no significa que SCIP sea inferior. De hecho, muchos investigadores de optimización que se centran en desarrollar o mejorar los algoritmos de optimización prefieren SCIP, ya que su naturaleza de código abierto permite a los usuarios modificar cada parte del solucionador, lo que les permite probar nuevas metodologías. El código completo para este problema se puede encontrar aquí.Trabajos citados[1] A. Philpott, ¿Qué es la programación estocástica? (2022), Sociedad de Programación Estocástica.[2] AJ Kleywegt, A. Shapiro, T, Homem-de-Mello. El método de aproximación del promedio de muestras para la optimización discreta estocástica (2002), SIAM Journal on Optimization.[3] SS Nielsen, SA Zenios. Descomposición de dobladores paralelos escalables para programación lineal estocástica (1997), Computación paralela Volumen 23, Número 8.[4] Gurobi. Comenzando con Gurobi (2022), sitio web de Gurobi[5] Bestúzheva et. Alabama. SCIP Optimization Suite 8.0 (2021), Optimización en línea