OptimJ

OptimJ est une extension pour Java avec support de langage pour l'écriture de modèles d'optimisation et d'abstractions pour le traitement de données en masse. Les extensions et le produit propriétaire implémentant les extensions ont été développés par Ateji qui a cessé ses activités en septembre 2011. OptimJ vise à fournir une notation algébrique claire et concise pour la modélisation d'optimisation, en supprimant les barrières de compatibilité entre la modélisation d'optimisation et les outils de programmation d'applications, et en apportant des techniques d'ingénierie logicielle telles que l'orientation objet et la prise en charge des IDE modernes aux experts en optimisation.

Les modèles OptimJ sont directement compatibles avec le code source Java, les bibliothèques Java existantes telles que l'accès aux bases de données, la connexion à Excel ou les interfaces graphiques. OptimJ est compatible avec les outils de développement tels qu'Eclipse, CVS, JUnit ou JavaDoc. OptimJ est disponible gratuitement avec les solveurs suivants : lp_solve, glpk, formats de fichiers LP ou MPS et prend également en charge les solveurs commerciaux suivants : MOSEK , IBM ILOG CPLEX Optimization Studio.

OptimJ combine des concepts issus des langages impératifs orientés objet avec des concepts issus des langages de modélisation algébrique pour les problèmes d'optimisation. Nous allons ici passer en revue les concepts d'optimisation ajoutés à Java, en commençant par un exemple concret.

Le but d'un problème de coloration de carte est de colorier une carte de manière à ce que les régions partageant une frontière commune aient des couleurs différentes. Cela peut être exprimé dans OptimJ comme suit.

exemples de packages ;
// un modèle simple pour le problème de coloration de carte 
public model SimpleColoring solver lpsolve { // nombre maximal de couleurs int nbColors = 4 ;
// les variables de décision contiennent la couleur de chaque pays 
var int belgique dans 1 .. nbColors ; var int danemark dans 1 .. nbColors ; var int allemagne dans 1 .. nbColors ;
// les pays voisins doivent avoir des 
contraintes de couleur différentes { belgique != allemagne ; allemagne != danemark ; }
// un point d'entrée principal pour tester notre modèle 
public static void main ( String [] args ) { // instancier le modèle SimpleColoring m = new SimpleColoring ();
// résolvez- 
le m . extract (); m . solve ();
// imprimer les solutions 
System . out . println ( "Belgique : " + m . value ( m . belgique )); System . out . println ( "Danemark : " + m . value ( m . denmark )); System . out . println ( "Allemagne : " + m . value ( m . allemagne )); } }

Les lecteurs familiers avec Java remarqueront une forte similitude avec ce langage. En effet, OptimJ est une extension conservatrice de Java : tout programme Java valide est également un programme OptimJ valide et a le même comportement.

Cet exemple de coloriage de carte montre également des fonctionnalités spécifiques à l'optimisation qui n'ont pas d'équivalent direct en Java, introduites par les mots-clés model, var, constraints.

Un modèle est une extension d'une classe Java qui peut contenir non seulement des champs et des méthodes mais aussi des contraintes et une fonction objective. Il est introduit par le modelmot-clé et suit les mêmes règles que les déclarations de classe. Un modèle non abstrait doit être lié à un solveur, introduit par le mot-clé solver. Les capacités du solveur détermineront le type de contraintes qui peuvent être exprimées dans le modèle, par exemple un solveur linéaire tel que lp solve n'autorisera que des contraintes linéaires.

modèle public SimpleColoring solveur lpsolve

Les langages impératifs tels que Java fournissent une notion de variables impératives , qui représentent essentiellement des emplacements de mémoire dans lesquels il est possible d'écrire et de lire.

OptimJ introduit également la notion de variable de décision, qui représente essentiellement une quantité inconnue dont on cherche la valeur. Une solution à un problème d'optimisation est un ensemble de valeurs pour toutes ses variables de décision qui respecte les contraintes du problème. Sans variables de décision, il ne serait pas possible d'exprimer des problèmes d'optimisation. Le terme « variable de décision » vient de la communauté de l'optimisation, mais les variables de décision dans OptimJ sont le même concept que les variables logiques dans les langages logiques tels que Prolog.

Les variables de décision ont des types spéciaux introduits par le mot-clé var. Il existe un vartype pour chaque type Java possible.

// un type var pour un type primitif Java 
var int x ;
// un type var pour une classe définie par l'utilisateur 
var MyClass y ;

Dans l'exemple de coloration de carte, les variables de décision ont été introduites avec la plage de valeurs qu'elles peuvent prendre.

var int allemagne en 1 .. nbColors ;

Il s’agit simplement d’un raccourci équivalent à l’application d’une contrainte sur la variable.

Les contraintes expriment des conditions qui doivent être vraies dans toute solution du problème. Une contrainte peut être n'importe quelle expression booléenne Java impliquant des variables de décision.

Dans l'exemple de coloration de carte, cet ensemble de contraintes stipule que dans toute solution au problème de coloration de carte, la couleur de la Belgique doit être différente de la couleur de l'Allemagne, et la couleur de l'Allemagne doit être différente de la couleur du Danemark.

contraintes { belgique != allemagne ; allemagne != danemark ; }

L'opérateur !=est l'opérateur différent de Java standard.

Les contraintes sont généralement fournies par lots et peuvent être quantifiées avec l' forallopérateur. Par exemple, au lieu de lister tous les pays et leurs voisins explicitement dans le code source, on peut avoir un tableau de pays, un tableau de variables de décision représentant la couleur de chaque pays et un tableau boolean[][] neighboringou un prédicat (une fonction booléenne) boolean isNeighbor().

contraintes { forall ( Pays c1 : pays , Pays c2 : pays , : isNeighbor ( c1 , c2 )) { couleur [ c1 ] != couleur [ c2 ] ; } }

Country c1 : countriesest un générateur : il itère c1sur toutes les valeurs de la collection countries.

:isNeighbor(c1,c2)est un filtre : il ne conserve que les valeurs générées pour lesquelles le prédicat est vrai (le symbole :peut être lu comme "si").

En supposant que le tableau countriescontient belgium, germanyet denmark, et que le prédicat isNeighborrenvoie truepour les couples ( Belgium , Germany) et ( Germany, Denmark), alors ce code est équivalent au bloc de contraintes de l'exemple de coloration de carte d'origine.

En option, lorsqu'un modèle décrit un problème d'optimisation, une fonction objective à minimiser ou à maximiser peut être énoncée dans le modèle.

Les concepts généralistes sont des concepts de programmation qui ne sont pas spécifiques aux problèmes de RO et qui auraient du sens pour tout type de développement d'application. Les concepts généralistes ajoutés à Java par OptimJ rendent l'expression des modèles de RO plus facile ou plus concise. Ils sont souvent présents dans les langages de modélisation plus anciens et offrent ainsi aux experts de RO une manière familière d'exprimer leurs modèles.

Alors que les tableaux Java ne peuvent être indexés que par des entiers de base 0, les tableaux OptimJ peuvent être indexés par des valeurs de tout type. Ces tableaux sont généralement appelés tableaux associatifs ou cartes. Dans cet exemple, le tableau agecontient l'âge des personnes, identifiées par leur nom :

int [ Chaîne ] âge ;

Le type int[String]désignant un tableau de intindexé par String. Accès aux tableaux OptimJ à l'aide de la syntaxe Java standard :

âge [ "Stephan" ] = 37 ; x = âge [ "Lynda" ] ;

Traditionnellement, les tableaux associatifs sont largement utilisés dans l'expression de problèmes d'optimisation. Les tableaux associatifs d'OptimJ sont très pratiques lorsqu'ils sont associés à leur syntaxe d'initialisation spécifique. Les valeurs initiales peuvent être données dans une définition intentionnelle , comme dans :

int [ String ] âge = { "Stéphan" -> 37 , "Lynda" -> 29 };

ou peut être donné dans une définition extensionnelle , comme dans :

int [ String ] length [ String nom : noms ] = nom . length ();

Ici, chacune des entrées length[i]est initialisée avec names[i].length().

Les tuples sont omniprésents en informatique, mais absents de la plupart des langages courants, y compris Java. OptimJ fournit une notion de tuple au niveau du langage qui peut être très utile comme index en combinaison avec des tableaux associatifs.

(: int , String :) myTuple = new (: 3 , "Trois" :); String s = myTuple # 1 ;

Les types de tuple et les valeurs de tuple sont tous deux écrits entre (:et :).

Les compréhensions , également appelées opérations d'agrégation ou de réduction, sont des expressions OptimJ qui étendent une opération binaire donnée sur une collection de valeurs. Un exemple courant est la somme :

// la somme de tous les entiers de 1 à 10 
int k = sum { i | int i in 1 .. 10 };

Cette construction est très similaire à la notation de sommation grand sigma utilisée en mathématiques, avec une syntaxe compatible avec le langage Java.

Les compréhensions peuvent également être utilisées pour créer des collections, telles que des listes, des ensembles, des multi-ensembles ou des cartes :

// l'ensemble de tous les entiers de 1 à 10 
HashSet < Integer > s = ` hashSet (){ i | int i in 1 .. 10 };

Les expressions de compréhension peuvent avoir une expression arbitraire comme cible, comme dans :

// la somme de tous les carrés des entiers de 1 à 10 
int k = sum { i * i | int i in 1 .. 10 };

Ils peuvent également avoir un nombre arbitraire de générateurs et de filtres :

// la somme de tous les f(i,j), pour 0<=i<10, 1<=j<=10 et i!=j 
int k = somme { f ( i , j ) | int i : 10 , int j : 1 .. 10 , : i != j }

La compréhension ne doit pas s'appliquer uniquement aux valeurs numériques. Les compréhensions par construction d'ensembles ou de multi-ensembles, notamment en combinaison avec des tuples de chaînes, permettent d'exprimer des requêtes très similaires aux requêtes de base de données SQL :

// sélectionner le nom parmi les personnes dont l'âge > 18 
` multiSet (){ p . name | Person p : persons , : p . age > 18 }

Dans le contexte des modèles d’optimisation, les expressions de compréhension fournissent un moyen concis et expressif de prétraiter et de nettoyer les données d’entrée et de formater les données de sortie.

OptimJ est disponible sous forme de plug-in Eclipse. Le compilateur implémente une traduction source à source d'OptimJ vers Java standard, offrant ainsi une compatibilité immédiate avec la plupart des outils de développement de l'écosystème Java.

Étant donné que le compilateur OptimJ connaît la structure de toutes les données utilisées dans les modèles, il est capable de générer une vue graphique structurée de ces données au moment de la compilation. Cela est particulièrement pertinent dans le cas de tableaux associatifs où le compilateur connaît les collections utilisées pour indexer les différentes dimensions.

La vue graphique de base générée par le compilateur rappelle un cube OLAP . Elle peut ensuite être personnalisée de différentes manières, depuis la simple coloration jusqu'à la fourniture de nouveaux widgets pour l'affichage des éléments de données.

L'interface graphique OptimJ générée par le compilateur évite à l'expert en OR d'écrire tout le code de liaison nécessaire lors du mappage des bibliothèques graphiques aux données. Elle permet un prototypage rapide, en fournissant des indications visuelles immédiates sur la structure des données.

Une autre partie de l'interface graphique OptimJ fournit des statistiques de performances en temps réel provenant du solveur. Ces informations peuvent être utilisées pour comprendre les problèmes de performances et améliorer le temps de résolution. Pour le moment, elles ne sont disponibles que pour lp_solve.

OptimJ est disponible gratuitement avec les solveurs suivants : lp_solve, glpk, LP ou formats de fichiers MPS et prend également en charge les solveurs commerciaux suivants : Mosek, IBM ILOG CPLEX Optimization Studio.