OptimJ

OptimJ
Paradigm objektorienterad
Designad av Ateji
Dök först upp 2006 ( 2006 )
Hemsida www.Ateji.com
Influerad av
Java

OptimJ är ett tillägg för Java med språkstöd för att skriva optimeringsmodeller och abstraktioner för bulkdatabehandling. Tilläggen och den egenutvecklade produkten som implementerar tilläggen har utvecklats av Ateji som lades ner i september 2011. OptimJ syftar till att tillhandahålla en tydlig och koncis algebraisk notation för optimeringsmodellering, ta bort kompatibilitetsbarriärer mellan optimeringsmodellering och applikationsprogrammeringsverktyg, och ta med programvara tekniska tekniker som objektorientering och modernt IDE-stöd till optimeringsexperter.

OptimJ-modeller är direkt kompatibla med Java-källkod, befintliga Java-bibliotek som databasåtkomst, Excel-anslutning eller grafiska gränssnitt. OptimJ är kompatibel med utvecklingsverktyg som Eclipse, CVS, JUnit eller JavaDoc. OptimJ är tillgänglig gratis med följande lösare: lp_solve, glpk, LP eller MPS filformat och stöder även följande kommersiella lösare: MOSEK , IBM ILOG CPLEX Optimization Studio.

Språkbegrepp

OptimJ kombinerar koncept från objektorienterade imperativspråk med koncept från algebraiska modelleringsspråk för optimeringsproblem. Här kommer vi att granska de optimeringskoncept som lagts till i Java, och börjar med ett konkret exempel.

Exempel på kartfärgning

Målet med ett kartfärgningsproblem är att färglägga en karta så att regioner som delar en gemensam kant har olika färger. Det kan uttryckas i OptimJ enligt följande. 

 


    

  
     

  
        
        
        

  
   
      
      
  

  
      
  
    
        

    
    
    

    
      
      
      
  
 paketexempel  ;  _  // en enkel modell för kartfärgningsproblemet  offentlig  modell  SimpleColoring-  lösaren  lpsolve  {  // maximalt antal färger  int  nbColors  =  4  ;  // beslutsvariabler håller färgen för varje land  var  int  belgium  i  1  ..  nbColors  ;  var  int  danmark  i  1  ..  nbColors  ;  var  int  tyskland  i  1  ..  nbColors  ;  // grannländer måste ha en annan färgbegränsning  {  belgium  !  =  tyskland  ;  tyskland  !=  danmark  ;  }  // en huvudingång för att testa vår modell  public  static  void  main  (  String  []  args  )  {  // instansiera modellen  SimpleColoring  m  =  new  SimpleColoring  ();  // lös det  m  .  extrakt  ();  m  .  lösa  ();  // utskriftslösningar  System  .  ut  .  println  (  "Belgien: "  +  m  .  värde  (  m  .  belgien  ));  System  .  ut  .  println  (  "Danmark: "  +  m  .  värde  (  m  .  danmark  ));  System  .  ut  .  println  (  "Tyskland: "  +  m  .  värde  (  m  .  tyskland  ));  }  }

Läsare som är bekanta med Java kommer att märka en stark likhet med detta språk. OptimJ är faktiskt en konservativ förlängning av Java: varje giltigt Java-program är också ett giltigt OptimJ-program och har samma beteende.

Det här kartfärgningsexemplet visar också funktioner som är specifika för optimering som inte har någon direkt motsvarighet i Java, introducerade av nyckelorden model , var , constraints .

ELLER-specifika begrepp

Modeller

En modell är en förlängning av en Java-klass som inte bara kan innehålla fält och metoder utan även begränsningar och en objektiv funktion. Det introduceras av modellnyckelordet och följer samma regler som klassdeklarationer. En icke-abstrakt modell måste kopplas till en lösare, introducerad av nyckelordet lösare . Lösarens förmåga kommer att avgöra vilken typ av begränsningar som kan uttryckas i modellen, till exempel kommer en linjär lösare som lp solve endast att tillåta linjära begränsningar. 

     offentlig  modell  SimpleColoring  lösare  lpsolve

Beslutsvariabler

Imperativa språk som Java tillhandahåller en uppfattning om imperativa variabler , som i princip representerar minnesplatser som kan skrivas till och läsas från.

OptimJ introducerar också begreppet beslutsvariabel, som i princip representerar en okänd kvantitet vars värde man söker efter. En lösning på ett optimeringsproblem är en uppsättning värden för alla dess beslutsvariabler som respekterar problemets begränsningar – utan beslutsvariabler skulle det inte vara möjligt att uttrycka optimeringsproblem. Termen "beslutsvariabel" kommer från optimeringsgemenskapen, men beslutsvariabler i OptimJ är samma koncept som logiska variabler i logiska språk som Prolog.

Beslutsvariabler har speciella typer som introduceras av nyckelordet var . Det finns en var- typ för varje möjlig Java-typ. 

  
    

  
     // en var-typ för en primitiv Java-typ  var  int  x  ;  // en var-typ för en användardefinierad klass  var  MyClass  y  ;

I kartfärgningsexemplet introducerades beslutsvariabler tillsammans med intervallet av värden de kan ta.

         var  int  tyskland  i  1  ..  nbColors  ;

Detta är bara en förkortning som motsvarar att sätta en begränsning på variabeln.

Begränsningar

Restriktioner uttrycker villkor som måste vara sanna i varje lösning av problemet. En begränsning kan vara vilket Java-booleskt uttryck som helst som involverar beslutsvariabler.

I kartfärgningsexemplet anger denna uppsättning begränsningar att i alla lösningar på kartfärgningsproblemet måste Belgiens färg vara annorlunda än Tysklands färg och Tysklands färg måste skilja sig från Danmarks färg.

   
      
      
   begränsningar  {  belgien  !=  tyskland  ;  tyskland  !=  danmark  ;  }

Operatören != är standard Java not-equal operator.

Begränsningar kommer vanligtvis i omgångar och kan kvantifieras med den allmänna operatören. Till exempel, istället för att uttryckligen lista alla länder och deras grannar i källkoden, kan man ha en uppsättning länder, en uppsättning beslutsvariabler som representerar färgen på varje land, och en boolesk matris[][] angränsande eller ett predikat ( en boolesk funktion) boolean isNeighbor() . 

 
           
      
  
 constraints  {  forall  (  Land  c1  :  länder  ,  Land  c2  :  länder  ,  :  är Granne  (  c1  ,  c2  ))  {  färg  [  c1  ]  !=  färg  [  c2  ]  ;  }  }

Land c1 : länder är en generator: den itererar c1 över alla värden i insamlingsländerna .

:isNeighbor(c1,c2) ​​är ett filter: det behåller endast de genererade värdena för vilka predikatet är sant (symbolen : kan läsas som "om").

Om vi ​​antar att arrayländerna innehåller Belgien , Tyskland och danmark och att predikatet är Neighbor returnerar sant för paren ( Belgien , Tyskland ) och ( Tyskland , Danmark ), så motsvarar denna kod begränsningsblocket i det ursprungliga kartfärgningsexemplet.

Mål

Valfritt, när en modell beskriver ett optimeringsproblem, kan en objektiv funktion som ska minimeras eller maximeras anges i modellen.

Generalistiska begrepp

Generalistiska koncept är programmeringskoncept som inte är specifika för OR-problem och som skulle vara vettiga för alla typer av applikationsutveckling. De generalistkoncept som lagts till Java av OptimJ gör uttrycket av OR-modeller enklare eller mer koncis. De finns ofta i äldre modelleringsspråk och ger därför OR-experter ett välbekant sätt att uttrycka sina modeller.

Associativa arrayer

Medan Java-arrayer endast kan indexeras med 0-baserade heltal, kan OptimJ-arrayer indexeras med värden av vilken typ som helst. Sådana arrayer kallas vanligtvis associativa arrayer eller kartor. I det här exemplet innehåller arrayåldern åldern på personer, identifierade med deras namn: 

    int  [  String  ]  ålder  ;

Typen int[String] som anger en array av int indexerad av String . Åtkomst till OptimJ-matriser med standard Java-syntax: 

    
     ålder  [  "Stephan"  ]  =  37  ;  x  =  ålder  [  "Lynda"  ]  ;

Traditionellt används associativa arrayer flitigt för att uttrycka optimeringsproblem. OptimJ associativa arrayer är mycket praktiska när de associeras med deras specifika initialiseringssyntax. Initiala värden kan anges i intensional definition , som i: 

    
    
       
 int  [  String  ]  age  =  {  "Stephan"  ->  37  ,  "Lynda"  ->  29  };

eller kan ges i extensionsdefinition , som i: 

         int  [  String  ]  length  [  String  name  :  names  ]  =  namn  .  längd  ();

initieras var och en av posternas längd[i] med namn[i].length() .

Utökad initiering

Tuples

Tuples är allestädes närvarande i datorer, men frånvarande från de flesta vanliga språk inklusive Java. OptimJ ger en föreställning om tuple på språknivå som kan vara mycket användbar som index i kombination med associativa arrayer. 

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

Tuppeltyper och tuppelvärden skrivs båda mellan (: och :) .

Avstånd

Förståelser

Förståelser , även kallade aggregatoperationer eller reduktioner, är OptimJ-uttryck som utökar en given binär operation över en samling värden. Ett vanligt exempel är summan: 

  
               // summan av alla heltal från 1 till 10  int  k  =  summa  {  i  |  int  i  i  1  ..  10  };

Denna konstruktion är mycket lik den big-sigma summeringsnotation som används i matematik, med en syntax som är kompatibel med Java-språket.

Förståelser kan också användas för att bygga samlingar, såsom listor, uppsättningar, multiset eller kartor:

  
              // mängden av alla heltal från 1 till 10  HashSet  <  Integer  >  s  =  `  hashSet  (){  i  |  int  i  i  1  ..  10  };

Förståelseuttryck kan ha ett godtyckligt uttryck som mål, som i:

  
               // summan av alla kvadrater av heltal från 1 till 10  int  k  =  summa  {  i  *  i  |  int  i  i  1  ..  10  };

De kan också ha ett godtyckligt antal generatorer och filter:

  
                    // summan av alla f(i,j), för 0<=i<10, 1<=j<=10 och i!=j  int  k  =  summa  {  f  (  i  ,  j  )  |  int  i  :  10  ,  int  j  :  1  ..  10  ,  :  i  !=  j  }

Förståelse behöver inte bara gälla numeriska värden. Uppsättningar eller multiset-byggnadsförståelser, särskilt i kombination med tuplingar av strängar, gör det möjligt att uttrycka frågor som mycket liknar SQL-databasfrågor:

  
             // välj namn från personer där ålder > 18  `  multiSet  (){  p  .  namn  |  Person  p  :  personer  ,  :  p  .  ålder  >  18  }

I samband med optimeringsmodeller ger förståelseuttryck ett kortfattat och uttrycksfullt sätt att förbearbeta och rensa indata och formatera utdata.

Utvecklingsmiljö

OptimJ är tillgänglig som en Eclipse plug-in. Kompilatorn implementerar en källa-till-källa-översättning från OptimJ till standard Java, vilket ger omedelbar kompatibilitet med de flesta utvecklingsverktyg i Java-ekosystemet.

OptimJ GUI och Rapid Prototyping

Eftersom OptimJ-kompilatorn känner till strukturen för all data som används i modeller, kan den generera en strukturerad grafisk vy av dessa data vid kompilering. Detta är särskilt relevant i fallet med associativa arrayer där kompilatorn känner till samlingarna som används för att indexera de olika dimensionerna.

Den grundläggande grafiska vyn som genereras av kompilatorn påminner om en OLAP-kub . Den kan sedan anpassas på många olika sätt, från enkel färgläggning till att tillhandahålla nya widgets för att visa dataelement.

Det kompilatorgenererade OptimJ-gränssnittet sparar OR-experten från att skriva all limkod som krävs när grafiska bibliotek mappas till data. Det möjliggör snabb prototypframställning genom att ge omedelbara visuella tips om datastrukturen.

En annan del av OptimJ GUI rapporterar i realtid prestandastatistik från lösaren. Denna information kan användas för att förstå prestationsproblem och förbättra lösningstiden. För närvarande är den endast tillgänglig för lp_solve.

Lösare som stöds

OptimJ är tillgänglig gratis med följande lösare lp_solve, glpk, LP eller MPS filformat och stöder även följande kommersiella lösare: Mosek, IBM ILOG CPLEX Optimization Studio.

externa länkar


Hämtad från " https://en.wikipedia.org/w/index.php?title=OptimJ&oldid=1054582141 "