AMPL ( Un lenguaje de programación matemática ) es un lenguaje de modelado algebraico para describir y resolver problemas de alta complejidad para computación matemática a gran escala (es decir, problemas de tipo optimización y programación a gran escala ). [1] Fue desarrollado por Robert Fourer , David Gay y Brian Kernighan en Bell Laboratories . AMPL admite docenas de solucionadores , tanto de código abierto como de software comercial , incluidos CBC, CPLEX , FortMP , Gurobi , MINOS , IPOPT ,SNOPT , KNITRO y LGO. Los problemas se pasan a los solucionadores como archivos nl . AMPL es utilizado por más de 100 clientes corporativos y por agencias gubernamentales e instituciones académicas. [2]
Paradigma | Multi-paradigma : declarativo , imperativo |
---|---|
Diseñada por | Robert Fourer David Gay Brian Kernighan Bell Labs |
Desarrollador | Optimización AMPL, Inc. |
Apareció por primera vez | 1985 |
Lanzamiento estable | 20131012/12 de octubre de 2013 |
SO | Multiplataforma : Linux , macOS , Solaris , AIX , Windows |
Licencia | Propietario (traductor), gratuito y de código abierto (AMPL Solver Library) |
Extensiones de nombre de archivo | .mod, .dat, .run |
Sitio web | www |
Influenciado por | |
AWK , C | |
Influenciado | |
Pyomo |
Una ventaja de AMPL 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 . Muchos solucionadores modernos disponibles en el servidor NEOS (anteriormente alojado en el Laboratorio Nacional Argonne , actualmente alojado en la Universidad de Wisconsin, Madison [3] ) aceptan entrada AMPL. Según las estadísticas de NEOS, AMPL es el formato más popular para representar problemas de programación matemática.
Características
AMPL presenta una combinación de estilos de programación declarativos e imperativos . La formulación de modelos de optimización se produce a través de elementos del lenguaje declarativo como conjuntos, parámetros escalares y multidimensionales, variables de decisión, objetivos y restricciones , que permiten una descripción concisa de la mayoría de los problemas en el dominio de la optimización matemática.
Los procedimientos y declaraciones de flujo de control están disponibles en AMPL para
- el intercambio de datos con fuentes de datos externas como hojas de cálculo , bases de datos , XML y archivos de texto
- Tareas de pre y posprocesamiento de datos en torno a modelos de optimización.
- la construcción de algoritmos híbridos para tipos de problemas para los que no se dispone de solucionadores eficientes directos.
Para respaldar la reutilización y simplificar la construcción de problemas de optimización a gran escala, AMPL permite la separación del modelo y los datos.
AMPL admite una amplia gama de tipos de problemas, entre ellos:
- Programación lineal
- Programación cuadrática
- Programación no lineal
- Programación de enteros mixtos
- Programación cuadrática de enteros mixtos con o sin restricciones cuadráticas convexas
- Programación no lineal de enteros mixtos
- Programación de cono de segundo orden
- Optimización global
- Problemas de programación semidefinidos con desigualdades de matrices bilineales
- Problemas de la teoría de la complementariedad (MPEC) en variables discretas o continuas
- Programación de restricciones [4]
AMPL invoca un solucionador en un proceso separado que tiene estas ventajas:
- El usuario puede interrumpir el proceso de solución en cualquier momento
- Los errores del solucionador no afectan al intérprete
- La versión de 32 bits de AMPL se puede utilizar con un solucionador de 64 bits y viceversa
La interacción con el solucionador se realiza a través de una interfaz nl bien definida .
Disponibilidad
AMPL está disponible para muchos sistemas operativos populares de 32 y 64 bits , incluidos Linux , macOS , Solaris , AIX y Windows . [5] El traductor es un software propietario mantenido por AMPL Optimization LLC. Sin embargo, existen varios servicios en línea que brindan modelado gratuito y facilidades de resolución utilizando AMPL. [6] [7] También están disponibles una versión gratuita para estudiantes con funcionalidad limitada y una versión gratuita con todas las funciones para cursos académicos. [8]
AMPL se puede utilizar desde Microsoft Excel a través del complemento SolverStudio Excel.
La biblioteca AMPL Solver Library (ASL), que permite leer archivos nl y proporciona la diferenciación automática, es de código abierto. Se utiliza en muchos solucionadores para implementar la conexión AMPL.
Historial de estado
Esta tabla presenta pasos importantes en la historia de AMPL.
Año | Reflejos |
---|---|
1985 | AMPL fue diseñado e implementado [1] |
1990 | Un artículo que describe el lenguaje de modelado AMPL se publicó en Management Science [9]. |
1991 | AMPL admite programación no lineal y diferenciación automática |
1993 | Robert Fourer , David Gay y Brian Kernighan fueron galardonados con el premio ORSA / CSTS [10] de la Operations Research Society of America , por sus escritos sobre el diseño de sistemas de programación matemática y el lenguaje de modelado AMPL. |
1995 | Extensiones para representar estructuras de red y lineales por partes |
1995 | Construcciones de secuencias de comandos |
1997 | Soporte mejorado para solucionadores no lineales |
1998 | AMPL apoya los problemas de la teoría de la complementariedad |
2000 | Acceso relacional a bases de datos y hojas de cálculo |
2002 | Soporte para programación de restricciones [4] |
2003 | AMPL Optimization LLC fue fundada por los inventores de AMPL, Robert Fourer, David Gay y Brian Kernighan. La nueva empresa se hizo cargo el desarrollo y el apoyo del lenguaje de modelado AMPL de Lucent Technologies, Inc . |
2005 | Apertura del grupo de Google de lenguaje de modelado AMPL [11] |
2008 | Kestrel: Introducción de una interfaz AMPL para el servidor NEOS |
2012 | Robert Fourer , David Gay y Brian Kernighan recibieron el premio INFORMS Impact de 2012 como los creadores de uno de los lenguajes de modelado algebraico más importantes. [12] |
2012 | El libro AMPL está disponible gratuitamente en línea [13] |
2013 | Está disponible un nuevo entorno de desarrollo integrado (IDE) multiplataforma para AMPL [14] |
Un modelo de muestra
Se utiliza un problema de transporte de George Dantzig para proporcionar un modelo AMPL de muestra. Este problema encuentra el programa de envío de menor costo que cumple con los requisitos en los mercados y los suministros en las fábricas. [15]
Establecer Plantas ; establecer Mercados ; # Capacidad de la planta p en casos param Capacidad { p en Plantas }; # Demanda en el mercado m en casos param Demanda { m en Mercados }; # Distancia en miles de millas param Distancia { Plantas , Mercados }; # Flete en dólares por caja por mil millas param Flete ; # Costo de transporte en miles de dólares por caja param TransportCost { p en Plantas , m en Mercados } : = Flete * Distancia [ p , m ] / 1000 ; # Cantidades de envío en casos var envío { Plantas , Mercados } > = 0 ; # Los costos totales de transporte en miles de dólares minimizan el costo : suma { p en Plantas , m en Mercados } TransporteCost [ p , m ] * envío [ p , m ]; # Respete el límite de suministro en la planta p s.t. suministro { p en Plantas }: suma { m en Mercados } envío [ p , m ] <= Capacidad [ p ]; # Satisfacer la demanda en el mercado m s.t. demanda { m en Mercados }: suma { p en Plantas } envío [ p , m ] > = Demanda [ m ]; datos ; Establecer Plantas : = seattle san - diego ; establecer Mercados : = nueva - york chicago topeka ; Capacidad param : = seattle 350 san - diego 600 ; PARAM demanda : = nueva - york 325 Chicago 300 Topeka 275 ; param Distancia : nueva - york chicago topeka : = seattle 2.5 1.7 1.8 san - diego 2.5 1.8 1.4 ; param Flete : = 90 ;
Solucionadores
Aquí hay una lista parcial de solucionadores compatibles con AMPL: [16]
Solucionador | Tipos de problemas admitidos |
---|---|
APOPT | programación no lineal de enteros mixtos |
Artelys Knitro | programación lineal, cuadrática y no lineal |
Bonmin | programación no lineal de enteros mixtos |
BPMPD | programación lineal y cuadrática |
COIN-O CBC | programación de enteros mixtos |
COIN-O CLP | programación lineal |
CONOPT | programación no lineal |
Couenne [17] | programación no lineal de enteros mixtos (MINLP) |
CPLEX | Programación lineal, cuadrática, de cono de segundo orden y de enteros mixtos |
Optimizador de CP de CPLEX [18] | programación de restricciones |
FILTRAR | programación no lineal |
FortMP | programación de enteros lineales, cuadráticos y mixtos |
Gecode [19] | programación de restricciones |
Gurobi | Programación lineal, cuadrática, de cono de segundo orden y de enteros mixtos |
IPOPT | programación no lineal |
JaCoP [20] | programación de restricciones |
LGO [21] | optimización no lineal global y local |
lp_solve [22] | programación de enteros lineales y mixtos |
MINOS | programación lineal y no lineal |
MINTO | programación de enteros mixtos |
MOSEK | programación lineal, entera mixta lineal, cuadrática, cuadrática entera mixta, cuadráticamente restringida , cónica y convexa no lineal |
Motor de octeract | Todos los tipos de problemas de optimización sin términos diferenciales o integrales, incluyendo problemas discontinuos con min y max funciones elementales. |
SCIP | programación de enteros mixtos |
SNOPT | programación no lineal |
Sulum [23] | programación de enteros lineales y mixtos |
WORHP | programación no lineal |
XA | programación de enteros lineales y mixtos |
Xpress | optimización cuadrática lineal y convexa y sus contrapartes enteras mixtas |
Ver también
- sol (formato)
- GNU MathProg (anteriormente conocido como GMPL) es un subconjunto de AMPL compatible con el kit de programación lineal GNU [24]
Referencias
- ^ a b Cuatro, Robert ; Gay, David M ; Kernighan, Brian W. (2003). AMPL: un lenguaje de modelado para programación matemática . Estados Unidos: Duxbury Press / Brooks / Cole Publishing Company. ISBN 978-0-534-38809-6.
- ^ "Posición disponible" . Consultado el 29 de julio de 2011 .
- ^ "Acerca de" . Consultado el 11 de agosto de 2015 .
- ^ a b Cuatro, Robert ; Gay, David M. (2002). "Extensión de un lenguaje de modelado algebraico para apoyar la programación de restricciones" . INFORMA Revista de Computación . 14 (4): 322–344. CiteSeerX 10.1.1.8.9699 . doi : 10.1287 / ijoc.14.4.322.2825 .
- ^ "Plataformas" . AMPL Optimizaciones Inc .
- ^ "Servidor NEOS para optimización" . Consultado el 11 de agosto de 2015 .
- ^ "¡Prueba AMPL!" . Consultado el 11 de agosto de 2015 .
- ^ "Descargas AMPL" . Archivado desde el original el 26 de mayo de 2015 . Consultado el 11 de agosto de 2015 .
- ^ Cuatro, Robert ; Gay, David M .; Kernighan, Brian W. (1990). "Un lenguaje de modelado para la programación matemática" (PDF) . Ciencias de la gestión . 36 (5): 519–554–83. doi : 10.1287 / mnsc.36.5.519 .
- ^ INFORMA. "ICS - INFORMA" (PDF) . Consultado el 11 de agosto de 2015 .
- ^ "Grupos de Google" .
- ^ INFORMA. "Premio Impacto INFORMA" . Archivado desde el original el 22 de octubre de 2013 . Consultado el 11 de agosto de 2015 .
- ^ "Descarga gratuita - AMPL: un lenguaje de modelado para programación matemática" . Consultado el 5 de marzo de 2021 .
- ^ "Grupos de Google" . Consultado el 11 de agosto de 2015 .
- ^ Dantzig, George (2016) [1963]. "3. Formulación de un modelo de programación lineal" . Programación lineal y extensiones . Prensa de la Universidad de Princeton. págs. 32–62. ISBN 978-1-4008-8417-9.
- ^ "Solucionadores - AMPL" . Consultado el 21 de enero de 2018 .
- ^ "Couenne" . Archivado desde el original el 29 de octubre de 2013 . Consultado el 27 de octubre de 2013 .
- ^ "mp / solvers / ilogcp en master · ampl / mp · GitHub" . GitHub . Consultado el 11 de agosto de 2015 .
- ^ "mp / solvers / gecode en master · ampl / mp · GitHub" . GitHub . Consultado el 11 de agosto de 2015 .
- ^ "mp / solvers / jacop en master · ampl / mp · GitHub" . GitHub . Consultado el 11 de agosto de 2015 .
- ^ "LGO - AMPL" . Consultado el 11 de agosto de 2015 .
- ^ "Utilizando lpsolve de AMPL" . Consultado el 11 de agosto de 2015 .
- ^ "mp / solvers / sulum en master · ampl / mp · GitHub" . GitHub . Consultado el 11 de agosto de 2015 .
- ^ "Sitio oficial GLPK" . Consultado el 17 de septiembre de 2020 .
enlaces externos
- Página web oficial
- Página de inicio del profesor Fourer en la Universidad Northwestern