OptimJ es una extensión para Java con soporte de lenguaje para escribir modelos de optimización y abstracciones para el procesamiento masivo de datos. Las extensiones y el producto propietario que implementa las extensiones fueron desarrollados por Ateji que cerró en septiembre de 2011. [1] OptimJ tiene como objetivo proporcionar una notación algebraica clara y concisa para el modelado de optimización, eliminando las barreras de compatibilidad entre el modelado de optimización y las herramientas de programación de aplicaciones. y llevar técnicas de ingeniería de software como la orientación a objetos y el soporte IDE moderno a los expertos en optimización.
Paradigma | orientado a objetos |
---|---|
Diseñada por | Ateji |
Apareció por primera vez | 2006 |
Sitio web | www.Ateji.com |
Influenciado por | |
Java |
Los modelos OptimJ son directamente compatibles con el código fuente de Java, las bibliotecas Java existentes, como el acceso a la base de datos, la conexión a Excel o las interfaces gráficas. OptimJ es compatible con herramientas de desarrollo como Eclipse, CVS, JUnit o JavaDoc. OptimJ está disponible gratis con los siguientes solucionadores: formatos de archivo lp_solve, glpk, LP o MPS y también es compatible con los siguientes solucionadores comerciales: Gurobi , MOSEK , IBM ILOG CPLEX Optimization Studio.
Conceptos de lenguaje
OptimJ combina conceptos de lenguajes imperativos orientados a objetos con conceptos de lenguajes de modelado algebraico para problemas de optimización. Aquí revisaremos los conceptos de optimización agregados a Java, comenzando con un ejemplo concreto.
El ejemplo de colorear un mapa
El objetivo de un problema de coloración de mapas es colorear un mapa para que las regiones que comparten un borde común tengan colores diferentes. Puede expresarse en OptimJ de la siguiente manera.
ejemplos de paquetes ;// un modelo simple para el problema de colorear mapa modelo público SimpleColoring solver lpsolve { // número máximo de colores int nbColors = 4 ; // las variables de decisión tienen el color de cada país var int belgium in 1 .. nbColors ; var int dinamarca en 1 .. nbColors ; var int germany in 1 .. nbColors ; // los países vecinos deben tener restricciones de color diferentes { bélgica ! = alemania ; alemania ! = dinamarca ; } // un punto de entrada principal para probar nuestro modelo public static void main ( String [] args ) { // instanciar el modelo SimpleColoring m = new SimpleColoring (); // resolverlo m . extraer (); m . resolver (); // Soluciones de impresión System . fuera . println ( "Bélgica:" + m . valor ( m . bélgica )); Sistema . fuera . println ( "Dinamarca:" + m . valor ( m . dinamarca )); Sistema . fuera . println ( "Alemania:" + m . valor ( m . alemania )); } }
Los lectores familiarizados con Java notarán una gran similitud con este lenguaje. De hecho, OptimJ es una extensión conservadora de Java: cada programa Java válido es también un programa OptimJ válido y tiene el mismo comportamiento.
Este ejemplo de mapa de coloración también muestra características específicas de optimización que no tienen un equivalente directo en Java, introducido por las palabras clave model
, var
, constraints
.
Conceptos específicos de quirófano
Modelos
Un modelo es una extensión de una clase Java que puede contener no solo campos y métodos, sino también restricciones y una función objetivo. Se introduce mediante la model
palabra clave y sigue las mismas reglas que las declaraciones de clase. Un modelo no abstracto debe estar vinculado a un solucionador, introducido por la palabra clave solver
. Las capacidades del solucionador determinarán qué tipo de restricciones se pueden expresar en el modelo, por ejemplo, un solucionador lineal como lp solve solo permitirá restricciones lineales.
modelo público SimpleColoring solver lpsolve
Variables de decisión
Los lenguajes imperativos como Java proporcionan una noción de variables imperativas , que básicamente representan ubicaciones de memoria en las que se puede escribir y leer.
OptimJ también introduce la noción de variable de decisión, que básicamente representa una cantidad desconocida cuyo valor se está buscando. Una solución a un problema de optimización es un conjunto de valores para todas sus variables de decisión que respeta las restricciones del problema; sin las variables de decisión, no sería posible expresar problemas de optimización. El término "variable de decisión" proviene de la comunidad de optimización, pero las variables de decisión en OptimJ son el mismo concepto que las variables lógicas en lenguajes lógicos como Prolog.
Las variables de decisión tienen tipos especiales introducidos por la palabra clave var
. Hay un var
tipo para cada posible tipo de Java.
// un tipo var para un tipo primitivo de Java var int x ; // un tipo var para una clase definida por el usuario var MyClass y ;
En el ejemplo de coloración del mapa, las variables de decisión se introdujeron junto con el rango de valores que pueden tomar.
var int germany in 1 .. nbColors ;
Esto es solo un equivalente abreviado de poner una restricción a la variable.
Restricciones
Las restricciones expresan condiciones que deben ser verdaderas en cualquier solución del problema. Una restricción puede ser cualquier expresión booleana de Java que involucre variables de decisión.
En el ejemplo de coloración de mapas, este conjunto de restricciones establece que en cualquier solución al problema de coloración de mapas, el color de Bélgica debe ser diferente del color de Alemania y el color de Alemania debe ser diferente del color de Dinamarca.
restricciones { bélgica ! = alemania ; alemania ! = dinamarca ; }
El operador !=
es el operador estándar de Java no igual.
Las restricciones suelen venir en lotes y pueden cuantificarse con el forall
operador. Por ejemplo, en lugar de enumerar todos los países y sus vecinos explícitamente en el código fuente, se puede tener una matriz de países, una matriz de variables de decisión que representan el color de cada país y una matriz boolean[][] neighboring
o un predicado (una función booleana) boolean isNeighbor()
.
restricciones { forall ( País c1 : países , País c2 : países , : isNeighbor ( c1 , c2 )) { el color [ c1 ] ! = color de [ c2 ] ; } }
Country c1 : countries
es un generador: itera c1
sobre todos los valores de la colección countries
.
:isNeighbor(c1,c2)
es un filtro: mantiene solo los valores generados para los que el predicado es verdadero (el símbolo :
puede leerse como "si").
Suponiendo que la matriz countries
contiene belgium
, germany
y denmark
, y que el predicado isNeighbor
devuelve true
las parejas ( Belgium
, Germany
) y ( Germany
, Denmark
), entonces este código es equivalente al bloque de restricciones del ejemplo de coloración del mapa original.
Objetivos
Opcionalmente, cuando un modelo describe un problema de optimización, se puede establecer en el modelo una función objetivo a minimizar o maximizar.
Conceptos generalistas
Los conceptos generalistas son conceptos de programación que no son específicos de los problemas de quirófano y que tendrían sentido para cualquier tipo de desarrollo de aplicaciones. Los conceptos generalistas agregados a Java por OptimJ hacen que la expresión de los modelos OR sea más fácil o más concisa. A menudo están presentes en lenguajes de modelado más antiguos y, por lo tanto, proporcionan a los expertos en quirófano una forma familiar de expresar sus modelos.
Matrices asociativas
Mientras que las matrices de Java solo se pueden indexar por enteros basados en 0, las matrices de OptimJ se pueden indexar por valores de cualquier tipo. Estas matrices se denominan normalmente matrices asociativas o mapas. En este ejemplo, la matriz age
contiene la edad de las personas, identificadas por su nombre:
int [ String ] edad ;
El tipo que int[String]
denota una matriz de int
indexados por String
. Acceder a matrices OptimJ utilizando la sintaxis estándar de Java:
edad [ "Stephan" ] = 37 ; x = edad [ "Lynda" ] ;
Tradicionalmente, las matrices asociativas se utilizan mucho en la expresión de problemas de optimización. Las matrices asociativas OptimJ son muy útiles cuando se asocian a su sintaxis de inicialización específica. Los valores iniciales se pueden dar en definición intensional , como en:
int [ String ] edad = { "Stephan" -> 37 , "Lynda" -> 29 };
o se puede dar en una definición extensiva , como en:
int [ String ] length [ String name : names ] = name . longitud ();
Aquí cada una de las entradas length[i]
se inicializa con names[i].length()
.
Inicialización extendida
Tuplas
Las tuplas son omnipresentes en la informática, pero están ausentes en la mayoría de los lenguajes convencionales, incluido Java. OptimJ proporciona una noción de tupla a nivel de lenguaje que puede ser muy útil como índices en combinación con matrices asociativas.
(: int , String :) myTuple = new (: 3 , "Tres" :); String s = myTuple # 1 ;
Los tipos de tupla y los valores de tupla se escriben entre (:
y :)
.
Rangos
Comprensiones
Las comprensiones , también llamadas operaciones agregadas o reducciones, son expresiones OptimJ que extienden una operación binaria dada sobre una colección de valores. Un ejemplo común es la suma:
// la suma de todos los enteros de 1 a 10 int k = sum { i | int i en 1 .. 10 };
Esta construcción es muy similar a la notación de suma sigma grande utilizada en matemáticas, con una sintaxis compatible con el lenguaje Java.
Las comprensiones también se pueden utilizar para crear colecciones, como listas, conjuntos, multisets o mapas:
// el conjunto de todos los números enteros del 1 al 10 HashSet < Integer > s = ` hashSet () { i | int i en 1 .. 10 };
Las expresiones de comprensión pueden tener una expresión arbitraria como objetivo, como en:
// la suma de todos los cuadrados de números enteros de 1 a 10 int k = sum { i * i | int i en 1 .. 10 };
También pueden tener una cantidad arbitraria de generadores y filtros:
// la suma de todos f (i, j), para 0 <= i <10, 1 <= j <= 10 y i! = j int k = sum { f ( i , j ) | int i : 10 , int j : 1 .. 10 , : i ! = j }
No es necesario que la comprensión se aplique solo a valores numéricos. Las comprensiones de construcción de conjuntos o conjuntos múltiples, especialmente en combinación con tuplas de cadenas, permiten expresar consultas muy similares a las consultas de bases de datos SQL:
// seleccionar el nombre de las personas con edad> 18 ` multiSet () { p . nombre | Persona P : personas , : p . edad > 18 }
En el contexto de los modelos de optimización, las expresiones de comprensión proporcionan una forma concisa y expresiva de preprocesar y limpiar los datos de entrada y formatear los datos de salida.
Entorno de desarrollo
OptimJ está disponible como complemento de Eclipse. El compilador implementa una traducción de fuente a fuente de OptimJ a Java estándar, proporcionando así compatibilidad inmediata con la mayoría de las herramientas de desarrollo del ecosistema Java.
OptimJ GUI y creación rápida de prototipos
Dado que el compilador de OptimJ conoce la estructura de todos los datos utilizados en los modelos, puede generar una vista gráfica estructurada de estos datos en tiempo de compilación. Esto es especialmente relevante en el caso de matrices asociativas donde el compilador conoce las colecciones utilizadas para indexar las diversas dimensiones.
La vista gráfica básica generada por el compilador recuerda a un cubo OLAP . Luego, se puede personalizar de muchas formas diferentes, desde simples colores hasta proporcionar nuevos widgets para mostrar elementos de datos.
La interfaz gráfica de usuario OptimJ generada por el compilador evita que el experto en quirófano tenga que escribir todo el código de pegamento necesario al asignar bibliotecas gráficas a datos. Permite la creación rápida de prototipos, proporcionando pistas visuales inmediatas sobre la estructura de los datos.
Otra parte de la interfaz gráfica de usuario de OptimJ informa en tiempo real las estadísticas de rendimiento del solucionador. Esta información se puede utilizar para comprender los problemas de rendimiento y mejorar el tiempo de resolución. En este momento, solo está disponible para lp_solve.
Solucionadores compatibles
OptimJ está disponible de forma gratuita con los siguientes formatos de archivo lp_solve, glpk, LP o MPS de solucionadores y también es compatible con los siguientes solucionadores comerciales: Gurobi , Mosek, IBM ILOG CPLEX Optimization Studio.
enlaces externos
Referencias
- ^ "Ateji está cerrado" . Consultado el 11 de enero de 2012 .
- Desarrollo rápido de aplicaciones con OPTIMJ, un informe de experiencia de un profesional. David Gravot, Patrick Viry. EURO 2010 (Lisboa)
- OptimJ utilizado en un modelo de optimización para líneas de montaje de modelos mixtos, Universidad de Münster
- OptimJ utilizado en una técnica aproximada de cálculo de equilibrio perfecto en subjuegos para juegos repetidos, Universidad Laval