Optim J

Optim J
Paradygmat zorientowany obiektowo
Zaprojektowany przez Ateji
Po raz pierwszy pojawiły się 2006 ( 2006 )
Strona internetowa www.Ateji.com
Pod wpływem
Javy

OptimJ to rozszerzenie dla języka Java z obsługą języków do pisania modeli optymalizacyjnych i abstrakcji do masowego przetwarzania danych. Rozszerzenia i zastrzeżony produkt implementujący rozszerzenia zostały opracowane przez firmę Ateji, która zakończyła działalność we wrześniu 2011 r. OptimJ ma na celu zapewnienie jasnej i zwięzłej notacji algebraicznej do modelowania optymalizacyjnego, usuwanie barier kompatybilności między modelowaniem optymalizacyjnym a narzędziami do programowania aplikacji oraz wprowadzanie oprogramowania techniki inżynieryjne, takie jak zorientowanie obiektowe i nowoczesne wsparcie IDE dla ekspertów ds. optymalizacji.

Modele OptimJ są bezpośrednio kompatybilne z kodem źródłowym Java, istniejącymi bibliotekami Java, takimi jak dostęp do bazy danych, połączenie z Excelem lub interfejsy graficzne. OptimJ jest kompatybilny z narzędziami programistycznymi, takimi jak Eclipse, CVS, JUnit czy JavaDoc. OptimJ jest dostępny bezpłatnie z następującymi solwerami: lp_solve, glpk, LP lub MPS, a także obsługuje następujące komercyjne solwery: MOSEK , IBM ILOG CPLEX Optimization Studio.

Pojęcia językowe

OptimJ łączy koncepcje z zorientowanych obiektowo języków imperatywnych z koncepcjami z algebraicznych języków modelowania dla problemów optymalizacyjnych. Tutaj przejrzymy koncepcje optymalizacji dodane do Javy, zaczynając od konkretnego przykładu.

Przykład kolorowania mapy

Celem problemu kolorowania mapy jest pokolorowanie mapy w taki sposób, aby regiony mające wspólną granicę miały różne kolory. Można to wyrazić w OptimJ w następujący sposób. 

 


    

  
     

  
        
        
     przykłady  pakietów  ;  // prosty model problemu z kolorowaniem map  public  model  SimpleColoring  solver  lpsolve  {  // maksymalna liczba kolorów  int  nbColors  =  4  ;  // zmienne decyzyjne przechowują kolor każdego kraju  var  int  belgia  w  1  ..  nbColors  ;  var  int  dania  w  1  ..  nbColors  ;  var  int  Niemcy     

  
   
      
      
  

  
      
  
    
        

     w  1  ..  nbKolory  ;  // sąsiednie kraje muszą mieć inny kolor  ograniczenia  {  belgia  !=  niemcy  ;  Niemcy  !=  Dania  ;  }  // główny punkt wejścia do testowania naszego modelu  public  static  void  main  (  String  []  args  )  {  // utworzenie instancji modelu  SimpleColoring  m  =  new  SimpleColoring  ();  // rozwiązać 
    
    

    
      
      
     m  .  ekstrakt  ();  m  .  rozwiązać  ();  // rozwiązania do drukowania  System  .  na  zewnątrz  println  (  "Belgia: "  +  m  .  wartość  (  m  .  belgia  ));  systemu  .  na  zewnątrz  println  (  "Dania: "  +  m  .  wartość  (  m  .  dania  ));  systemu  .  na zewnątrz   
  
 .  println  (  "Niemcy: "  +  m  .  wartość  (  m  .  niemcy  ));  }  }

Czytelnicy zaznajomieni z Javą zauważą silne podobieństwo do tego języka. Rzeczywiście, OptimJ jest konserwatywnym rozszerzeniem Javy: każdy prawidłowy program Java jest również poprawnym programem OptimJ i zachowuje się tak samo.

Ten przykład kolorowania mapy pokazuje również cechy charakterystyczne dla optymalizacji, które nie mają bezpośredniego odpowiednika w Javie, wprowadzone przez słowa kluczowe model , var , ograniczenia .

Koncepcje specyficzne dla sali operacyjnej

modele

Model to rozszerzenie klasy Java, które może zawierać nie tylko pola i metody, ale także ograniczenia i funkcję celu. Jest wprowadzany przez model i podlega tym samym zasadom, co deklaracje klas. Model nieabstrakcyjny musi być powiązany z solverem, wprowadzanym przez słowo kluczowe solver . Możliwości solvera określą, jakiego rodzaju ograniczenia można wyrazić w modelu, na przykład solver liniowy, taki jak lp solve , dopuszcza tylko ograniczenia liniowe. 

     model  publiczny  Solver  SimpleColoring  lpsolve

Zmienne decyzje

Języki imperatywne, takie jak Java, zapewniają pojęcie zmiennych imperatywnych , które zasadniczo reprezentują lokalizacje pamięci, do których można zapisywać iz których można czytać.

OptimJ wprowadza również pojęcie zmiennej decyzyjnej, która zasadniczo reprezentuje nieznaną wielkość, której wartość się szuka. Rozwiązaniem problemu optymalizacyjnego jest zbiór wartości wszystkich jego zmiennych decyzyjnych, który respektuje ograniczenia problemu — bez zmiennych decyzyjnych nie byłoby możliwe wyrażenie problemów optymalizacyjnych. Termin „zmienna decyzyjna” pochodzi od społeczności zajmującej się optymalizacją, ale zmienne decyzyjne w OptimJ to ta sama koncepcja, co zmienne logiczne w językach logicznych, takich jak Prolog.

Zmienne decyzyjne mają specjalne typy wprowadzone przez słowo kluczowe var . Istnieje var dla każdego możliwego typu Java. 

  
    

  
     // typ var dla prymitywnego typu Javy  var  int  x  ;  // typ var dla klasy zdefiniowanej przez użytkownika  var  MyClass  y  ;

W przykładzie kolorowania mapy wprowadzono zmienne decyzyjne wraz z zakresem wartości, jakie mogą przyjmować.

         var  int  niemcy  za  1  ..  nbKolory  ;

Jest to tylko skrócony odpowiednik nałożenia ograniczenia na zmienną.

Ograniczenia

Ograniczenia wyrażają warunki, które muszą być spełnione w każdym rozwiązaniu problemu. Ograniczeniem może być dowolne wyrażenie boolowskie języka Java obejmujące zmienne decyzyjne.

W przykładzie kolorowania mapy ten zestaw ograniczeń stwierdza, że ​​w każdym rozwiązaniu problemu kolorowania mapy kolor Belgii musi różnić się od koloru Niemiec, a kolor Niemiec musi różnić się od koloru Danii.

   
      
      
   ograniczenia  {  belgia  ! =  niemcy  ;  Niemcy  !=  Dania  ;  }

Operator != jest standardowym operatorem nierówności w Javie.

Ograniczenia zazwyczaj pojawiają się w partiach i można je określić ilościowo za pomocą operatora forall . Na przykład, zamiast jawnie wymieniać wszystkie kraje i ich sąsiadów w kodzie źródłowym, można mieć tablicę krajów, tablicę zmiennych decyzyjnych reprezentujących kolor każdego kraju oraz tablicę boolean[][] sąsiadującą lub predykat ( funkcja logiczna) boolean isNeighbor() . 

 
           
      
  
 ograniczenia  {  forall  (  Kraj  c1  :  kraje  ,  Kraj  c2  :  kraje  ,:  isNeighbor  (  c1  ,  c2  )  )  {  color  [  c1  ]  !=  color  [  c2  ]  ;  }  }

Country c1:countries jest generatorem: iteruje c1 po wszystkich wartościach w kolekcji countrys .

:isNeighbor(c1,c2) ​​jest filtrem: przechowuje tylko wygenerowane wartości, dla których predykat jest prawdziwy (symbol : można odczytać jako „jeśli”).

Zakładając, że tablica country zawiera belgię , niemcy i dania , a predykat isNeighbor zwraca wartość true dla par ( Belgia , Niemcy ) i ( Niemcy , Dania ), to ten kod jest odpowiednikiem bloku ograniczeń z oryginalnego przykładu kolorowania mapy.

Cele

Opcjonalnie, gdy model opisuje problem optymalizacji, w modelu można określić funkcję celu, która ma zostać zminimalizowana lub zmaksymalizowana.

Koncepcje ogólne

Koncepcje ogólne to koncepcje programistyczne, które nie są specyficzne dla problemów OR i miałyby sens dla każdego rodzaju tworzenia aplikacji. Ogólne koncepcje dodane do Javy przez OptimJ sprawiają, że wyrażanie modeli OR jest łatwiejsze lub bardziej zwięzłe. Często są obecne w starszych językach modelowania, dzięki czemu zapewniają ekspertom OR znajomy sposób wyrażania swoich modeli.

Tablice asocjacyjne

Podczas gdy tablice Java mogą być indeksowane tylko przez liczby całkowite od 0, tablice OptimJ mogą być indeksowane przez wartości dowolnego typu. Takie tablice są zwykle nazywane tablicami asocjacyjnymi lub mapami. W tym przykładzie tablica wiek zawiera wiek osób identyfikowanych na podstawie ich nazw: 

    int  [  String  ]  wiek  ;

Typ int[String] oznaczający tablicę int indeksowaną przez String . Dostęp do tablic OptimJ przy użyciu standardowej składni Java: 

    
     wiek  [  "Stefan"  ]  =  37  ;  x  =  wiek  [  "Lynda"  ]  ;

Tradycyjnie tablice asocjacyjne są często używane do wyrażania problemów optymalizacyjnych. Tablice asocjacyjne OptimJ są bardzo przydatne, gdy są powiązane z ich specyficzną składnią inicjalizacji. Wartości początkowe można podać w definicji intencjonalnej , jak w: 

    
    
       
 int  [  String  ]  wiek  =  {  "Stefan"  ->  37  ,  "Lynda"  ->  29  };

lub można podać w definicji ekstensjonalnej , jak w: 

         int  [  łańcuch  ]  długość  [  nazwa  ciągu  :  nazwy  ]  =  nazwa  .  długość  ();

Tutaj każdy z wpisów length[i] jest inicjowany nazwami[i].length() .

Rozszerzona inicjalizacja

Krotki

Krotki są wszechobecne w informatyce, ale nie występują w większości głównych języków, w tym w Javie. OptimJ zapewnia pojęcie krotki na poziomie języka, które może być bardzo przydatne jako indeksy w połączeniu z tablicami asocjacyjnymi. 

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

Typy krotek i wartości krotek są zapisywane między (: i :) .

Zakresy

Zrozumienia

Wyrażenia , zwane także operacjami agregującymi lub redukcjami, to wyrażenia OptimJ, które rozszerzają daną operację binarną na zbiór wartości. Typowym przykładem jest suma: 

  
               // suma wszystkich liczb całkowitych od 1 do 10  int  k  =  sum  {  i  |  int  i  w  1  ..  10  };

sumacyjnej big-sigma , ze składnią zgodną z językiem Java.

Zrozumienia mogą być również używane do budowania kolekcji, takich jak listy, zbiory, zbiory wielozbiorowe lub mapy:

  
              // zbiór wszystkich liczb całkowitych od 1 do 10  HashSet  <  Integer  >  s  =  `  hashSet  (){  i  |  int  i  w  1  ..  10  };

Wyrażenia rozumienia mogą mieć dowolne wyrażenie jako cel, na przykład:

  
               // suma wszystkich kwadratów liczb całkowitych od 1 do 10  int  k  =  sum  {  i  *  i  |  int  i  w  1  ..  10  };

Mogą też mieć dowolną liczbę generatorów i filtrów:

  
                    // suma wszystkich f(i,j), dla 0<=i<10, 1<=j<=10 i i!=j  int  k  =  sum  {  f  (  i  ,  j  )  |  int  ja  :  10  ,  int  j  :  1  ..  10  ,  :  ja  !=  j  }

Zrozumienie nie musi odnosić się tylko do wartości liczbowych. Zrozumienia budujące zestawy lub wielozbiory, zwłaszcza w połączeniu z krotkami łańcuchów, umożliwiają wyrażanie zapytań bardzo podobnych do zapytań do bazy danych SQL:

  
             // wybierz nazwisko spośród osób, których wiek > 18  `  multiSet  (){  p  .  imię  |  Osoba  p  :  osoby  ,  :  s  .  wiek  >  18 lat   }

W kontekście modeli optymalizacyjnych wyrażenia rozumienia zapewniają zwięzły i wyrazisty sposób wstępnego przetwarzania i czyszczenia danych wejściowych oraz formatowania danych wyjściowych.

Środowisko deweloperskie

OptimJ jest dostępny jako wtyczka Eclipse. Kompilator implementuje tłumaczenie typu source-to-source z OptimJ na standardową Javę, zapewniając w ten sposób natychmiastową kompatybilność z większością narzędzi programistycznych ekosystemu Java.

OptimJ GUI i szybkie prototypowanie

Ponieważ kompilator OptimJ zna strukturę wszystkich danych używanych w modelach, jest w stanie wygenerować ustrukturyzowany graficzny widok tych danych w czasie kompilacji. Jest to szczególnie istotne w przypadku tablic asocjacyjnych, w których kompilator zna kolekcje używane do indeksowania różnych wymiarów.

Podstawowy widok graficzny generowany przez kompilator przypomina kostkę OLAP . Można go następnie dostosowywać na wiele różnych sposobów, od prostego kolorowania po udostępnianie nowych widżetów do wyświetlania elementów danych.

Generowany przez kompilator graficzny interfejs użytkownika OptimJ oszczędza ekspertowi sali operacyjnej pisanie całego kodu kleju wymaganego podczas mapowania bibliotek graficznych na dane. Umożliwia szybkie tworzenie prototypów, dostarczając natychmiastowych wizualnych wskazówek dotyczących struktury danych.

Kolejna część OptimJ GUI raportuje w czasie rzeczywistym statystyki wydajności z solvera. Informacje te można wykorzystać do zrozumienia problemów z wydajnością i skrócenia czasu rozwiązywania. W tej chwili jest dostępny tylko dla lp_solve.

Obsługiwane solwery

OptimJ jest dostępny bezpłatnie z następującymi solwerami lp_solve, glpk, LP lub MPS, a także obsługuje następujące solwery komercyjne: Mosek, IBM ILOG CPLEX Optimization Studio.

Linki zewnętrzne


Pobrano z „ https://en.wikipedia.org/w/index.php?title=OptimJ&oldid=1054582141 ”