Solving large-scale two-stage stochastic optimization problems by specialized interior point method

Abstract

Two-stage stochastic optimization models give rise to very large linear problems (LP). Several approaches have been devised for efficiently solving them, among which are interior-point methods (IPM). However, using IPM, the linking columns that are associated with first-stage decisions cause excessive fill-ins for the solutions of the normal equations, thus making the procedure computationally expensive. We have taken a step forward on the road to a better solution by reformulating the LP through a variable splitting technique which has significantly reduced the solution time. This work presents a specialized IPM that first applies variable splitting, then exploits the structure of the deterministic equivalent formulation of the stochastic problem. The specialized IPM works with an algorithm that combines Cholesky factorization and preconditioned conjugate gradients for solving the normal equations when computing the Newton direction for stochastic optimization problems in which the first-stages variables are large enough. Our specialized approach outperforms standard IPM. This work provides the computational results of two stochastic problems from the literature: (1) a supply chain system and (2) capacity expansion in an electric system. Both linear and quadratic formulations were used to obtain instances of up to 39 million variables and six million constraints. When used in these applications, the computational results show that our procedure is more efficient than alternative state-of-the-art IP implementations (e.g., CPLEX) and other specialized methods for stochastic optimization.

Los modelos de optimización estocástica de dos etapas dan lugar a problemas lineales (PL) muy grandes. Se han ideado varios enfoques para resolverlos de manera eficiente, entre los que se encuentran los métodos de punto interior (MPI). Sin embargo, al usar MPI, las columnas de enlace que están asociados con las decisiones de la primera etapa provocan rellenos excesivos para las soluciones de las ecuaciones normales, lo que hace que el procedimiento sea computacionalmente costoso. Hemos dado un paso adelante en el camino hacia una mejor solución al reformular el PL mediante una técnica de división variable que ha reducido significativamente el tiempo de solución. Este trabajo presenta un MPI especializado que primero aplica la división de variables y luego explota la estructura de la formulación determinista equivalente del problema estocástico. El MPI especializado trabaja con un algoritmo que combina la factorización Cholesky y gradientes conjugados precondicionados para resolver las ecuaciones normales al calcular la dirección de Newton para problemas de optimización estocástica en los que las variables de las primeras etapas son lo suficientemente grandes. Nuestro enfoque especializado supera al MPI estándar. Este trabajo proporciona los resultados computacionales de dos problemas estocásticos de la literatura: (1) un sistema de cadena de suministro y (2) expansión de capacidad en un sistema eléctrico. Se utilizaron formulaciones tanto lineales como cuadráticas para obtener instancias de hasta 39 millones de variables y seis millones de restricciones. Cuando se utiliza en estas aplicaciones, los resultados computacionales muestran que nuestro procedimiento es más eficiente que las implementaciones de PI alternativas de última generación (por ejemplo, CPLEX) y otros métodos especializados para la optimización estocástica.