最適化計算をＧＡＭＳで行う
この分野について全くのド素人だけど、仕事で使いそうなので備忘録がてら書いていく。
この分野について
オペレーションズ・リサーチ(OR)は名前の通り、第２次世界対戦中に確立されたもので、あるシステムを管理する人に対して、適切な解を求めることを目的とする。最適化計算(数理計画法とも呼ばれる)は、ORの一つという位置づけである。
対象となる研究対象は、第6回 オペレーションズ・リサーチ（OR）---数学モデルを駆使して，経営戦略を立案する：ITproに分かりやすく概要が紹介されている。最適化計算の代表的な例題として、「巡回セールスマン問題」がある。これは複数の都市があった場合、どのような経路でセールスマンが巡回すれば、移動コストを最小化できるのかという解を求めるものである。
こういった問題をどのようにモデル化するか、どのようにそのモデルを解くかというのがこの分野の取り組む課題となる。
GAMSについて
先の最適化問題を解くにあたり、多次元配列をごりごりと計算することが必要になってくる。 幸いにして、いくつか最適化問題に特化したソフトウェアがある。
Mathematicaはもしかしたら大学等で利用していた人もいるかもしれない。競争力のない(金のない)研究室出身の私に取っては、うらやましいかぎり。
GAMS(General Algebraic Modeling System)は、Mathematicaと同様にモデリング言語と、その実行環境を提供するもの。しかし、個人的に利用する分であればライセンスは必要なさそう(扱える配列やソルバーといった機能制限があるみたいだが)。
日本語だとあまり情報見かけないので、 これから参考にしそうな情報のリンクを張っておく。。
- start [GAMS Support Wiki]
- GAMSのページ
- EmacsのGAMS-modeを作成されたお方
GAMSのコードの構造
ユーザマニュアルのP.29にコードの構造が掲載されている。
GAMSのコードは、Data, Model, Solutionの記述に大別できる。 Dataは最適化計算で利用されるパラメータや定数である。Modelは最適化で良く目にする制約条件や他の計算式、最小化(または最大化)の対象式である目的関数が含まれる。最後のSolutionはModelをどのソルバで解くかと、何を結果として出力するかを定義する。
マニュアルに沿って、GAMSの構成要素を解説してみる。 おおよそのGAMSコードの構成は以下のようになっている。
- Set(s) : 配列の添字を定義するブロック識別子
- Data : Prameter(s), Table(s), Scalar(s)といったブロック識別子をまとめた概念で、要は入力値
- Variable(s) : 最適化する際に選択肢となる変数(決定変数または内生変数)を定義するブロック識別子
- Equation(s) : 数式や不等式を定義するブロック識別子。何を最小化(または最大化)するかを評価する式(目的関数)も含まれる
- Model : どの式をモデルに含めるかを定義するブロック識別子
- Solve : どのモデルを解くかと、どう解くか(線形計画法(lp)か、非線形計画法(nlp)か)および解くべき目的関数の識別名、最後に最大化するか、最小化するかを定義するブロック識別子
チュートリアルに掲載されている「輸送問題」を見てみる。
- 農場(供給側)としてSeattle, San Diegoの２拠点がある
- 市場(需要側)としてNew York, Chicago, Topekaの３拠点がある
- 各農場、各市場間の距離が
d(i, j)と決まっている - 供給量、需要量にそれぞれ制限が制約条件として課せられている
- このとき、移動コストを最小限にするには、それぞれの農場からどこの市場に対してどの程度出荷すれば良いかを求める
ちなみに$titleは、モデルのタイトルを記述できる識別子。$ontext … $offtextは間に挟んだ文書がコメント扱いされる識別を表す。とりあえず、今はざっくり構成を把握して、詳細は別途調べとく。
$title Transport.gms
$ontext
This is tutorial model.
$offtext
Sets
i canning plants / seattle, san-diego /
j markets / new-york, chicago, topeka /;
Parameters
a(i) capacity of plant i in cases
/ seattle 350
san-diego 600 /
b(j) demand at market j in cases
/ new-york 325
chicago 300
topeka 275 /;
Table d(i,j) distance in thousands of miles
new-york chicago topeka
seattle 2.5 1.7 1.8
san-diego 2.5 1.8 1.4 ;
Scalar f freight in dollars per case per thousand miles /90/ ;
Parameter c(i, j) transport cost in thousands of dollars per case ;
c(i, j) = f * d(i, j) / 1000 ;
Variables
x(i, j) shipment quantities in cases
z total transportation costs in thousands of dollars ;
Positive Variable x;
Equations
cost define objective function
supply(i) observe supply limit at plant i
demand(j) satisfy demand at market j ;
cost.. z =e= sum((i, j), c(i, j)*x(i, j)) ;
supply(i).. sum(j, x(i, j)) =l= a(i) ;
demand(j).. sum(i, x(i, j)) =g= b(j) ;
Model transport /all/ ;
Solve transport using lp minimizing z ;
Display x.l, x.m ;
GAMSのAPIを利用する
GAMSのAPIとして、Java, Phython, .NETが用意されている(C, C++など他もあるけどドキュメントが足りなそう)。.NETはドキュメントがPDFで提供されていないっぽい。
Javaを使って、上の問題を解くサンプルを動かしてみよう。
GAMSフォルダに移動すると、apifilesというディレクトリがある。
その配下に各言語向けのAPIやそれを利用する実装例が格納されている。
JavaのAPIは[apifiles] > [Java] > [api]配下に格納されている。 また、上の輸送問題(Transport.gmsとする)を解くサンプルとして、[api]と同じ階層に[transport]があり、様々な実装例が紹介されている(それらを補足する説明がチュートリアルとして用意されている)。
それでは、pom.xmlの設定から始める。 GAMSに関係するところだけ。
簡単な輸送問題を解くクラスを作成
<!— GAMSのインストールパスを設定 —> <properties> <gams.path>/Applications/GAMS/gams24.2_osx_x64_64_sfx</gams.path> </properties> <!-- GAMSJavaAPI.jar —> <dependencies> <dependency> <groupId>com.gams.api</groupId> <artifactId>GAMSJavaAPI</artifactId> <version>1.0</version> <scope>system</scope> <systemPath>${gams.path}/apifiles/Java/api/GAMSJavaAPI.jar</systemPath> </dependency> </dependencies> <build> <plugins> <!-- DLLを利用するために必要 --> <plugin> <groupId>org.apache.maven.plugins</groupId> <artifactId>maven-surefire-plugin</artifactId> <configuration> <workingDirectory>target</workingDirectory> <argLine>-Djava.library.path=${gams.path}/apifiles/Java/api</argLine> </configuration> </plugin> </plugins> </build>
上の輸送問題のモデル(transport.gms)を読み込んで、解くクラスは以下のようになる。
public class Transport { /** * Resource Bundle . */ private static final ResourceBundle resource = ResourceBundle.getBundle("GAMSSetting"); /** * GAMSジョブを実行するメソッド. */ public void runJob() { System.out.println("check:" + resource.getString("WORKINGDIR")); System.out.println("check:" + resource.getString("GAMSDIR")); // ユーザの引数を与えて、GAMSWorkspaceインスタンスを生成する // 引数1 : Workingディレクトリを指定 (デフォルトだと, System.getProperty("java.io.tmpdir")で取得されたパス // 引数2 : GAMSのインストールディレクトリを指定 (デフォルトだと、環境変数PATHを見る) // 引数3 ; デバッグレベルを指定 (デフォルトだと、 OFF) GAMSWorkspace ws = new GAMSWorkspace( resource.getString("WORKINGDIR"), resource.getString("GAMSDIR"), GAMSGlobals.DebugLevel.OFF ); // GAMSのモデルライブラリからtrnsportモデル(輸送モデル)を指定し、GAMSJobインスタンスを生成 // TODO フルパスじゃないとダメみたい GAMSJob t1 = ws.addJobFromFile(resource.getString("INPUTGAMSFILE")); // t1ジョブを実行する t1.run(); // ジョブの結果が格納されたデータベース(メモリ上?)からxの結果を取得 System.out.println("Ran with Default:"); GAMSVariable x = t1.OutDB().getVariable("x"); for (GAMSVariableRecord rec : x) { System.out.print("x(" + rec.getKeys()[0] + ", " + rec.getKeys()[1] + "):"); System.out.print(", level = " + rec.getLevel()); System.out.println(", marginal = " + rec.getMarginal()); } // Workディレクトリをクリアする // cleanup(ws.workingDirectory()); } /** * 引数で指定されたWorkディレクトリ内のファイルを削除するメソッド. * @param directory */ static void cleanup(String directory) { File directoryToDelete = new File(directory); String files[] = directoryToDelete.list(); for (String file : files) { File fileToDelete = new File(directoryToDelete, file); try { fileToDelete.delete(); } catch(Exception e){ e.printStackTrace(); } } try { directoryToDelete.delete(); } catch(Exception e) { e.printStackTrace(); } } }
ResourceBundleで読んでいるプロパティファイルは以下。
# GAMSの設定関連のプロパティファイル GAMSDIR=/Applications/GAMS/gams24.2_osx_x64_64_sfx WORKINGDIR=/Users/hermesian/NetBeansProjects/GAMSEJB/work INPUTGAMSFILE=/Users/hermesian/NetBeansProjects/GAMSEJB/src/main/resources/Transport.gms
クラスを記述したらとりあえず単体テストしてみる。
package com.fujitsu.kime.gamsdemo.example; import org.junit.After; import org.junit.Before; import org.junit.Test; public class Transport2Test { /** * テスト対象クラス - Transport2 */ private Transport2 sut2; @Before public void setUp() { sut2 = new Transport2(); } @After public void tearDown() { sut2 = null; } /** * <per> * シミュレーションが動作することを確認する。 * </pre> */ @Test public void testRunJob() { System.out.println("runJob"); sut2.runJob(); } }
結局、環境変数にパスの設定が必要なのか…
上記の単体試験を実行すると、失敗して下記のようなエラーメセッージが現れる。
エラー発生:GAMS system directory [null] not found from environment variable!
環境変数に設定されてないよーというものであるが、 そもそも下記の記述でGAMSのインストールを指定していて、 ここの設定が先に見られるはずなのだが…
GAMSWorkspace ws = new GAMSWorkspace( resource.getString("WORKINGDIR"), resource.getString("GAMSDIR"), GAMSGlobals.DebugLevel.OFF );
単体テスト実行時だからかな…不明。。
環境変数export DYLD_LIBRARY_PATH=/Applications/GAMS/gams24.2_osx_x64_64_sfxを設定して、とりあえず結果がでるか確認する。
runJob check:/Users/hermesian/NetBeansProjects/GAMSEJB/work check:/Applications/GAMS/gams24.2_osx_x64_64_sfx Ran with Default x(seattle,new-york): , level =50.0 , marginal =0.0 x(seattle,chicago): , level =300.0 , marginal =0.0 x(seattle,topeka): , level =0.0 , marginal =0.036000000000000004 x(san-diego,new-york): , level =275.0 , marginal =0.0 x(san-diego,chicago): , level =0.0 , marginal =0.009000000000000008 x(san-diego,topeka): , level =275.0 , marginal =0.0 Tests run: 1, Failures: 0, Errors: 0, Skipped: 0, Time elapsed: 0.143 sec
なんとか動いた。
TODO
もう少しシミュレーションっぽい機能を拡充したい。。
- Jobキューの管理
- データの分離
- 可視化
