Los lenguajes de modelado algebraico ( AML ) son lenguajes de programación informática de alto nivel para describir y resolver problemas de alta complejidad para cálculos matemáticos a gran escala (es decir, problemas del tipo de optimización a gran escala ). [1] Una ventaja particular de algunos lenguajes de modelado algebraico como AIMMS , [1] AMPL , [2] GAMS , [1] MathProg , Mosel , [1] [3] y OPL es la similitud de su sintaxis con la notación matemática de los problemas de optimización. Esto permite una definición muy concisa y legible de problemas en el dominio de la optimización, que está respaldada por ciertos elementos del lenguaje como conjuntos, índices, expresiones algebraicas, índices dispersos poderosos y variables de manejo de datos, restricciones con nombres arbitrarios. La formulación algebraica de un modelo no contiene ninguna pista sobre cómo procesarlo.
Un AML no resuelve esos problemas directamente; en cambio, llama a algoritmos externos apropiados para obtener una solución. Estos algoritmos se denominan solucionadores y pueden manejar cierto tipo de problemas matemáticos como:
- problemas lineales
- problemas de enteros
- (entero mixto) problemas cuadráticos
- problemas mixtos de complementariedad
- programas matemáticos con restricciones de equilibrio
- sistemas no lineales restringidos
- problemas generales no lineales
- programas no lineales con derivadas discontinuas
- problemas de enteros no lineales
- problemas de optimización global
- problemas de optimización estocástica
Elementos principales
Los elementos centrales de una AML son:
- un intérprete de lenguaje de modelado (el propio AML)
- enlaces de solucionador
- interfaces de usuario (UI)
- instalaciones de intercambio de datos
Criterios de diseño
La mayoría de las AML siguen ciertos principios de diseño:
- una combinación equilibrada de elementos declarativos y procedimentales
- Arquitectura e interfaces abiertas a otros sistemas.
- diferentes capas con separación de:
- modelo y datos
- métodos de modelo y solución
- modelo y sistema operativo
- modelo e interfaz
Generación de modelos basados en datos
La mayoría de los lenguajes de modelado explotan las similitudes entre los modelos estructurados y las bases de datos relacionales [4] proporcionando una capa de acceso a la base de datos, que permite al sistema de modelado acceder directamente a los datos de fuentes de datos externas (por ejemplo, estos [5] manejadores de tablas para AMPL). Con el refinamiento de las tecnologías analíticas aplicadas a los procesos comerciales, los modelos de optimización se están convirtiendo en una parte integral de los sistemas de soporte de decisiones; Los modelos de optimización se pueden estructurar y estratificar para representar y soportar procesos comerciales complejos. En tales aplicaciones, la estructura de datos multidimensional típica de los sistemas OLAP se puede asignar directamente a los modelos de optimización y las operaciones típicas de MDDB se pueden traducir en operaciones de agregación y desagregación en el modelo subyacente [6].
Historia
Los lenguajes de modelado algebraico tienen sus raíces en los programas de generación de matrices y redacción de informes (MGRW), desarrollados a finales de los setenta. Algunos de estos son MAGEN, MGRW (IBM), GAMMA.3, DATAFORM y MGG / RWG. Estos sistemas simplificaron la comunicación de las instancias de problemas a los algoritmos de solución y la generación de un informe legible de los resultados.
Un generador de matrices temprano para LP se desarrolló alrededor de 1969 en el Mathematisch Centrum (ahora CWI), Amsterdam. [7] Su sintaxis era muy cercana a la notación matemática habitual, utilizando subíndices en sigmas. La entrada para el generador consistió en secciones separadas para el modelo y los datos. Encontró usuarios en universidades y en la industria. El principal usuario industrial fue la siderúrgica Hoogovens (ahora Tata Steel), donde se utilizó durante casi 25 años.
Un gran paso hacia los lenguajes de modelado modernos se encuentra en UIMP [8] , donde se analiza por primera vez la estructura de los modelos de programación matemática tomados de la vida real, para resaltar el agrupamiento natural de variables y restricciones que surgen de dichos modelos. Esto condujo a características de estructura de datos, que apoyaron el modelado estructurado; en este paradigma, todas las tablas de entrada y salida, junto con las variables de decisión, se definen en términos de estas estructuras, de manera comparable al uso de subíndices y conjuntos. Esta es probablemente la característica más notable común a todas las AML modernas y permitió, con el tiempo, una separación entre la estructura del modelo y sus datos, y una correspondencia entre las entidades en un modelo MP y los datos en bases de datos relacionales. Por lo tanto, un modelo podría finalmente instanciarse y resolverse en diferentes conjuntos de datos, simplemente modificando sus conjuntos de datos.
La correspondencia entre las entidades de modelado y los modelos de datos relacionales , [4] hizo posible generar instancias de modelos sin problemas mediante la obtención de datos de bases de datos corporativas. Esta característica ahora representa gran parte de la usabilidad de la optimización en aplicaciones de la vida real y es compatible con la mayoría de los lenguajes de modelado conocidos.
Referencias
- ↑ a b c d Kallrath, Joseph (2004). Lenguajes de modelado en optimización matemática . Publicaciones académicas de Kluwer. ISBN 978-1-4020-7547-6.
- ^ Robert Fourer; David M. Gay; Brian W. Kernighan (1990). "Un lenguaje de modelado para la programación matemática" . Ciencias de la gestión . 36 (5): 519–554–83. doi : 10.1287 / mnsc.36.5.519 .
- ^ Gueret, Christelle; Prins, Christian; Sevaux, Marc (2002). Aplicaciones de Optimización con Xpress-MP . Optimización del tablero limitada. ISBN 0-9543503-0-8.
- ^ a b Gautam Mitra; Cormac Lucas; Shirley Moody; Bjarni Kristjansson (1995). "Conjuntos e índices en el modelado de programación lineal y su integración con modelos de datos relacionales" . Optimización Computacional y Aplicaciones . 4 (3): 262–283.
- ^ [1] Controladores de tablas de hojas de cálculo y bases de datos para AMPL
- ^ Koutsoukis, N .; Mitra, G .; Lucas, C. (1999). "Adaptación del procesamiento analítico en línea para el modelado de decisiones: la interacción de las tecnologías de la información y la decisión" . Sistemas de apoyo a la toma de decisiones . 26 (1): 1–30. doi : 10.1016 / S0167-9236 (99) 00021-4 . Consultado el 22 de noviembre de 2017 .
- ^ Jac. M. Anthonisse, Un sistema de entrada para problemas de programación lineal, Statistica Neerlandica 24 (1970), 143-153.
- ^ Francis D Ellison; Gautam Mitra (1982). "UIMP: interfaz de usuario para programación matemática" (PDF) . Transacciones ACM en software matemático . 8 (3): 229-255. doi : 10.1145 / 356004.356005 . Archivado desde el original (PDF) el 18 de enero de 2014 . Consultado el 16 de enero de 2014 .