オプティムJ

OptimJ は、最適化モデルと大量データ処理の抽象化を記述するための言語サポートを備えたJavaの拡張機能です。拡張機能と拡張機能を実装する独自の製品は、2011 年 9 月に倒産した Ateji によって開発されました。 ^[1] OptimJ は、最適化モデリングのための明確で簡潔な代数表記法を提供し、最適化モデリングとアプリケーション プログラミング ツール間の互換性の障壁を取り除き、オブジェクト指向や最新の IDE サポートなどのソフトウェア エンジニアリング手法を最適化の専門家に提供することを目的としています。

OptimJ モデルは、Java ソース コード、データベース アクセス、Excel 接続、グラフィカル インターフェイスなどの既存の Java ライブラリと直接互換性があります。OptimJ は、Eclipse、CVS、JUnit、JavaDoc などの開発ツールと互換性があります。OptimJ は、lp_solve、glpk、LP、MPS ファイル形式のソルバーで無料で使用でき、MOSEK、IBM ILOG CPLEX Optimization Studio などの商用ソルバーもサポートしています。

OptimJ は、オブジェクト指向命令型言語の概念と、最適化問題のための代数モデリング言語の概念を組み合わせています。ここでは、具体的な例から始めて、Java に追加された最適化の概念を確認します。

地図の色付け問題の目的は、共通の境界を共有する領域が異なる色になるように地図を色付けすることです。これは、OptimJ では次のように表現できます。

パッケージの例; 

// マップカラーリング問題の簡単なモデル
public model SimpleColoringソルバーlpsolve { // 色の最大数int nbColors = 4 ;    

  
     

  // 決定変数は各国の色を保持します
var int belgium in 1 .. nbColors ; var int denmark in 1 .. nbColors ; var int germany in 1 .. nbColors ;        
        
        

  // 隣接する国は異なる色の
制約を持つ必要があります{ベルギー!=ドイツ;ドイツ!=デンマーク; }   
      
      
  

  // モデルをテストするためのメイン エントリ ポイント
public static void main ( String [] args ) { // モデルをインスタンス化しますSimpleColoring m = new SimpleColoring ();      
  
    
        

    
//解くm.extract () ; m.solve ( ) ;    
    

    //
ソリューションを出力System.out.println ( "ベルギー: " + m.value ( m.belgium ) ) ; System.out.println ( "デンマーク: " + m.value ( m.denmark ) ) ; System.out.println ( "ドイツ: " + m.value ( m.germany ) ) ; } }​​​​​​      
      
      
  

Java に精通している読者は、この言語との強い類似性に気付くでしょう。実際、OptimJ はJava の保守的な拡張です。有効な Java プログラムはすべて有効な OptimJ プログラムでもあり、同じ動作をします。

このマップの色分けの例では、、、 modelというキーワードで導入された、Java には直接相当するものがない最適化に特有の機能も示されていますvar。constraints

モデルは、フィールドとメソッドだけでなく、制約と目的関数も含めることができる Java クラスの拡張です。これはキーワードによって導入されmodel、クラス宣言と同じルールに従います。非抽象モデルは、キーワードによって導入されるソルバーにリンクする必要がありますsolver。ソルバーの機能によって、モデルで表現できる制約の種類が決まります。たとえば、lpsolveなどの線形ソルバーは線形制約のみを許可します。

パブリックモデルSimpleColoringソルバーlpsolve    

Java などの命令型言語では、基本的に書き込みおよび読み取りが可能なメモリの場所を表す 命令型変数の概念が提供されます。

OptimJ では、決定変数の概念も導入されています。これは基本的に、値を検索する未知の量を表します。最適化問題の解決策は、問題の制約を尊重するすべての決定変数の値のセットです。決定変数がなければ、最適化問題を表現することはできません。「決定変数」という用語は最適化コミュニティから来ていますが、OptimJ の決定変数は、Prolog などの論理言語の論理変数と同じ概念です。

決定変数には、キーワードによって導入される特別な型がありますvar。var可能な Java 型ごとに型が存在します。

  // Java プリミティブ型の var 型
var int x ;    

  // ユーザー定義クラスの var 型
var MyClass y ;    

マップの色付けの例では、決定変数と、それが取る値の範囲が紹介されました。

  var intドイツin 1 .. nbColors ;      

これは、変数に制約を設定するのと同じ簡略表現です。

制約は、問題のあらゆる解決において真でなければならない条件を表します。制約は、決定変数を含む任意の Java ブール式にすることができます。

地図の色付けの例では、この制約セットは、地図の色付けの問題に対するどの解決策でも、ベルギーの色はドイツの色と異なる必要があり、ドイツの色はデンマークの色と異なる必要があることを示しています。

  制約{ベルギー!=ドイツ;ドイツ!=デンマーク; } 
      
      
  

演算子は、!=標準の Java 不等号演算子です。

制約は通常、バッチで提供され、forall演算子を使用して定量化できます。たとえば、ソース コードですべての国とその近隣国を明示的にリストする代わりに、国の配列、各国の色を表す決定変数の配列、および配列boolean[][] neighboringまたは述語 (ブール関数)を持つことができますboolean isNeighbor()。

制約{ forall ( Country c1 :国, Country c2 :国, : isNeighbor ( c1 , c2 )) { color [ c1 ] != color [ c2 ] ; } } 
           
      
  

Country c1 : countriesはジェネレータです。c1コレクション内のすべての値を反復処理しますcountries。

:isNeighbor(c1,c2)フィルターです。述語が真である生成された値のみを保持します (シンボル:は「if」と読み取れます)。

配列に、およびがcountries含まれており、述語が( 、) および ( 、 )の組み合わせに対してを返すと仮定すると、このコードは元のマップの色付けの例の制約ブロックと同等になります。 belgiumgermanydenmarkisNeighbortrueBelgium GermanyGermanyDenmark

オプションとして、モデルが最適化問題を記述する場合、最小化または最大化される目的関数をモデル内で記述できます。

ジェネラリスト概念は、OR の問題に固有のものではなく、あらゆる種類のアプリケーション開発に意味のあるプログラミング概念です。OptimJ によって Java に追加されたジェネラリスト概念により、OR モデルの表現がより簡単に、またはより簡潔になります。これらの概念は古いモデリング言語によく含まれているため、OR の専門家にはモデルを表現する使い慣れた方法が提供されます。

Java 配列は 0 から始まる整数でのみインデックス付けできますが、OptimJ 配列は任意の型の値でインデックス付けできます。このような配列は、通常、連想配列またはマップと呼ばれます。この例では、配列にはage名前で識別される人の年齢が含まれています。

  int [文字列]年齢; 

によってインデックス付けされたint[String]配列を表す型。標準の Java 構文を使用して OptimJ 配列にアクセスします。 intString

  年齢[ "Stephan" ] = 37 ; x =年齢[ "Lynda" ] ;  
    

従来、連想配列は最適化問題の表現に頻繁に使用されています。OptimJ 連想配列は、特定の初期化構文に関連付けると非常に便利です。初期値は、次のように、内包的定義で指定できます。

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

または、次のように外延定義で与えることもできます。

  int [文字列] length [文字列name : names ] = name . length ();      

ここで、各エントリはlength[i]で初期化されますnames[i].length()。

タプルはコンピューティングの分野では広く使用されていますが、Java を含むほとんどの主流言語には存在しません。OptimJ は言語レベルでタプルの概念を提供し、連想配列と組み合わせたインデックスとして非常に役立ちます。

  (: int 、String :) myTuple = new (: 3 、"Three" :); String s = myTuple # 1 ;          
     

タプル型とタプル値は両方とも(:と の間に記述されます:)。

内包表記は、集約演算または縮約とも呼ばれ、値の集合に対して特定のバイナリ演算を拡張する OptimJ 式です。一般的な例としては、次の合計があります。

  // 1 から 10 までのすべての整数の合計
int k = sum { i | int i in 1 .. 10 };              

この構造は数学で使用されるビッグシグマ加算表記法に非常に似ており、構文は Java 言語と互換性があります。

内包表記は、リスト、セット、マルチセット、マップなどのコレクションを構築するためにも使用できます。

  // 1 から 10 までのすべての整数の集合
HashSet < Integer > s = ` hashSet (){ i | int i in 1 .. 10 };             

理解式は、次のように任意の式をターゲットとして持つことができます。

  // 1 から 10 までのすべての整数の平方の合計
int k = sum { i * i | int i in 1 .. 10 };              

任意の数のジェネレータとフィルターを持つこともできます。

  // すべての f(i,j) の合計。0<=i<10、1<=j<=10、i!=j の場合
int k = sum { f ( i , j ) | int i : 10 , int j : 1 .. 10 , : i != j }                   

理解は数値にのみ適用する必要はありません。セットまたはマルチセット構築の理解は、特に文字列のタプルと組み合わせることで、SQL データベース クエリに非常によく似たクエリを表現できるようになります。

  // age > 18 の persons から name を選択
` multiSet (){ p . name | Person p : persons , : p . age > 18 }            

最適化モデルのコンテキストでは、理解式は、入力データを前処理してクリーンアップし、出力データをフォーマットするための簡潔で表現力豊かな方法を提供します。

OptimJ は Eclipse プラグインとして利用できます。コンパイラはOptimJ から標準 Java へのソース間変換を実装しているため、Java エコシステムのほとんどの開発ツールとの互換性がすぐに得られます。

OptimJ コンパイラはモデルで使用されるすべてのデータの構造を認識しているため、コンパイル時にこのデータの構造化されたグラフィカル ビューを生成できます。これは、コンパイラがさまざまな次元のインデックス付けに使用されるコレクションを認識している連想配列の場合に特に重要です。

コンパイラによって生成される基本的なグラフィカル ビューは、OLAP キューブを彷彿とさせます。単純な色付けから、データ要素を表示するための新しいウィジェットの提供まで、さまざまな方法でカスタマイズできます。

コンパイラによって生成された OptimJ GUI により、OR の専門家は、グラフィカル ライブラリをデータにマッピングするときに必要なグルー コードをすべて記述する必要がなくなります。データの構造に関する視覚的なヒントを即座に提供することで、迅速なプロトタイピングが可能になります。

OptimJ GUI の別の部分は、ソルバーからのパフォーマンス統計をリアルタイムで報告します。この情報は、パフォーマンスの問題を理解し、解決時間を改善するために使用できます。現時点では、lp_solve でのみ使用できます。

OptimJ は、lp_solve、glpk、LP、または MPS ファイル形式のソルバーで無料で利用でき、Mosek、IBM ILOG CPLEX Optimization Studio などの商用ソルバーもサポートしています。

• OptimJ によるオブジェクト指向モデリング
• OptimJ 言語マニュアル
• OptimJ GUI

• OPTIMJ による迅速なアプリケーション開発、実践者の体験レポート。David Gravot、Patrick Viry。EURO 2010 (リスボン)
• ミュンスター大学の混合モデル組立ラインの最適化モデルで使用される OptimJ
• 繰り返しゲームにおける近似サブゲーム完全均衡計算手法で使用される OptimJ、ラヴァル大学