Lenguaje de dominio específico embebido para programación estocástica multietapa en Scala

Abstract

El soporte brindado por los lenguajes de modelado algebraico para trabajar con problemas de programación estocástica multietapa basada en escenarios es, en general, limitado y poco práctico. Las problemáticas incluyen excesiva verbosidad o redundancia, expresividad limitada, dificultad de integración con sistemas externos, ecosistemas cerrados, y dificultad para desarrollar extensiones. Los problemas de programación estocástica basados en escenarios suelen ser tratados como problemas de programación entera mixta a través de su forma extensiva, lo que permite utilizar todas las herramientas disponibles para ese tipo de problemas en la implementación computacional y resolución de los problemas estocásticos. Tratar a los problemas de programación estocástica como problemas enteros mixtos no es ideal. En primer lugar, exige la incorporación del control de la no anticipatividad de las decisiones en los modelos. Por otra parte, no brinda ninguna asistencia en la construcción del árbol de escenarios y la especificación de los valores de los parámetros estocásticos en forma consistente. Por último, no permite explotar la estructura particular de los problemas de programación estocástica en su resolución. En este trabajo se desarrolla un lenguaje de dominio específico (DSL), denominado amphip, en el que se explora una extensión al lenguaje de modelado algebraico para problemas de programación entera mixta, GNU MathProg, para incorporar soporte directo para programación estocástica multietapa basada en escenarios. El DSL es embebido en el lenguaje de programación Scala, permitiendo que los modelos puedan ser transformados y manipulados. El desarrollo es realizado utilizando íntegramente programación funcional, aprovechando el soporte provisto por Scala. El DSL desarrollado permite modelar los problemas de programación estocástica utilizando la formulación con escenarios separados. Las entidades del modelo son declaradas con una sintaxis que logra replicar con gran fidelidad la de MathProg. El DSL provee primitivas para la especificación del árbol de escenarios, las probabilidades, y los valores de los parámetros estocásticos en forma concisa y flexible. Aplicando transformaciones al modelo, se generan automáticamente las restricciones de no anticipatividad y versiones alternativas de los parámetros estocásticos sin escenarios separados, lo que permite construir una forma extensiva que es más eficiente que la se construiría manualmente. La funcionalidad provista puede ser extendida por el usuario, pudiendo definir, con pocas líneas de código, funciones para la construcción de árboles de escenarios con estructuras particulares, esquemas alternativos para definir las probabilidades de los escenarios, y funciones auxiliares para especificar los datos de los parámetros estocásticos tomando en cuenta las instancias particulares de los problemas.

Support provided by algebraic modeling languages for scenario-based multistage stochastic programming is, in general, limited and impractical. Problems include excessive verbosity or redundancy, limited expressiveness, difficulties integrating with external systems, closed ecosystems, and difficulties developing extensions. Scenario-based stochastic programming problemas are usually treated as mixed integer programming problemas through their extensive form, which allows to use all the tools available for that type of problems in the computational implementation and resolution of stochastic problems. Treating stochastic programming problems as mixed integer problems is not ideal. In the first place, it requires the incorporation of control of the non-anticipativity of decisions in the models. Moreover, it does not provide any assistance in building the scenario tree and specifying the values of the stochastic parameters consistently. Finally, it does not allows to exploit the particular structure of stochastic programming problems in their resolution. In this work, a domain specific language (DSL), called amphip, is developed, in which an extension to the algebraic modeling language for mixed integer programming problems, GNU MathProg, is explored to incorporate direct support for scenario-based multistage stochastic programming. The DSL is embedded in the Scala programming language, allowing models to be transformed and manipulated. The development is carried out entirely using functional programming, taking advantage of the support provided by Scala. The developed DSL allows modeling stochastic programming problems using the formulation with separated scenarios. Model entities are declared with a syntax that replicates that of MathProg with great fidelity. The DSL provides primitives for specifying the scenario tree, probabilities, and stochastic parameter values in a concise and flexible way. Applying transformations to the model, the non-anticipativity constraints and alternative versions of the stochastic parameters without separated scenarios are automatically generated, which allows building an extensive form that is more efficient than the one that would be built manually. The functionality provided can be extended by the user, being able to define, with a few lines of code, functions for the construction of scenario trees with particular structures, alternative schemes to define the probabilities of the scenarios, and auxiliary functions to specify the data of the stochastic parameters taking into account the particular instances of the problems.