トップ > ユーザーサポート > Numerical Optimizer FAQ > SIMPLE(モデルの書き方)

Numerical Optimizer FAQ

SIMPLE(モデルの書き方)

SIMPLE の記述はどんなものですか?

SIMPLE は C++ のクラスライブラリとして実装されていますので、C/C++ に非常に似通った外観を持ちます。下記は記述例です。

Variable x;    
Variable y;
Objective cost(type=minimize);    
cost = 180*x + 160*y; 
6*x + y >= 12;   
3*x + y >= 8;    
4*x + 6*y >= 24; 
0 <= x <= 5;
0 <= y <= 5; 

変数と目的関数に当たるのは Variable、Objective として宣言し、変数同士の演算によって式そのものを表現します。使う演算子は C/C++ のものと同じです。モデルを抽象化してデータを外から与える場合には、定数データ(Parameter)、集合(Set)、添字(Element)という概念が必要となりますが、その場合には次のような記述となります。

Set N,P;
Element j(set=N),i(set=P);
Variable x(index=j);
Parameter c(index=j),d(index=i);
Parameter a(index=(i,j));
Objective cost(type=minimize);
cost = sum(x[j],j);
sum(a[i,j]*x[j],j) >= d[i];
5 >= x[j] >= 0;

添字を使った和(sum)の表現など簡潔にモデルが記述できます。

モデルは自分で書くのですか?

はい。Numerical Optimizer を使うには適用する問題を数式の形で表現して与える必要があります。しかし、数理計画法の定式化には明らかなパターンがあり、ほとんどの応用は既存の例題の一部を組み合わせたり、書き換えるのみで記述可能ですので、最初から式を起こさなければならないということは、ほとんどありません。

Numerical Optimizer には典型的な例題が多数付属してますし、(株)NTT データ数理システムはお考えの問題が Numerical Optimizer を使って定式化可能かどうかを判定したり、実際に定式化を行って Numerical Optimizer で解いてみるサービスを無償で提供しておりますので、どうぞご利用ください(問題の複雑さ・規模により、場合によっては有償とさせて頂く場合もございますので予めご了承ください。質問を頂くことに対しては大歓迎です)。定式化一般についてのセミナーも随時開催しています。

また、Numerical Optimizer V13 より Numerical Optimizer のマニュアルの中に「Numerical Optimizer/SIMPLE 例題集」が新たに追加されました。初歩的なものから実際に使える例まで Numerical Optimizer を使った数多くの例題が収録されています。Numerical Optimizer をお持ちの方はサンプルコードをコピー&ペーストするだけで実行することができます。こちらからマニュアルをダウンロードすることができますので、ご興味がある方は是非ご覧ください。

具体的な問題をお持ちの方は nuopt-support@msi.co.jp までお気軽にご連絡ください。

どうすれば SIMPLE を習得できますか?

まずは実際にモデルを書いて Numerical Optimizer を動かしてみることをお勧めします。また、以下を参考にしてみてください。

SIMPLE チュートリアル
モデルファイルの記述方法から実行までをわかりやすく解説しています(オンラインマニュアルは こちら)。
SIMPLE 例題集
豊富な例題集が掲載されています(オンラインマニュアルは こちら)。
Numerical Optimizer 無料セミナー
まずは Numerical Optimizer 体験セミナー をご検討ください。実際にモデルファイルを書きながら SIMPLE を習得できます。既に Numerical Optimizer 体験セミナー を受講された方、または普段から Numerical Optimizer に慣れ親しんでいる方を対象にした Numerical Optimizer スキルアップセミナー もございます。

整数変数を使いたい。

SIMPLE整数変数を定義するには

 IntegerVariable x;

のように変数を宣言します。さらに、値として 0 と 1 のみをとる 0-1 整数変数を定義する場合は、

 IntegerVariable x(type=binary);

として変数の type 属性を binary とします。

添字の範囲に条件を付けたい。

和の場合は sum 関数中の添字に続けて条件式を書くことによって実現できます。

     sum(x[i], (i, i < S)) == 0;
     sum(x[i], (i, a[i] == 0)) == 0;

また、制約式の場合は、制約式の後にカンマで続けて書くことによって実現できます。

     x[i] == 1, i < S;
     x[i] == 1, a[i] == 0;

ただし、条件式部分に変数を含めることはできません。

     sum(x[i], (i, y[i] == 0)) == 0;  // 誤り

0 <= x <= 1 or 2 <= x <= 3 のように制約式の or は表現可能ですか?

0-1 整数変数 y と十分大きな数 M を用いることによって表現可能です。

 IntegerVariable y(type=binary); 
 0 - M*y <= x <= 1 + M*y
 2 - M*(1-y) <= x <= 3 + M*(1-y);

こう書くと、y=0 のときは 0<=x<=1 となり、y=1 の時は 2<=x<=3 となります。M は x のとりうる範囲より大きくとれば十分です。この例では M=3 となります。

とりうる範囲が明らかでない場合、通常 M を十分大きくとりますが、M が大きすぎるとモデルが解きづらくなるので注意してください。

計算の後処理にすごく時間がかかっています。

もし Numerical Optimizer GUI を使われているのであれば、以下のコマンドで実行時間を短縮できます。

 options.noDefaultSolout = 1; 

このコマンドで Numerical Optimizer GUI が使う結果ファイルを出力しないようにできます。

また、一般に解ファイル(モデル名.sol)の出力には問題規模に応じた時間を必要としますが、解ファイルを必要としない場合は以下のコマンドで解ファイルの出力を抑制することができます。これにより計算の後処理時間が短縮されます。

 options.outfilename = "_NULL_";

目的関数はなく、とにかく全ての制約を満たす解が欲しいです。

もし問題が全て 0-1 整数変数のみを使って記述できるのであれば、アルゴリズム WCSP が適しています。WCSP は、

 options.method = "wcsp";

とモデルに記述することにより適用されます。

min または max を使いたい。

min 関数, max 関数は SIMPLE で記述可能ですが、通常これらを用いることはお勧めしません。これらの関数を使うことによって問題が非線形になってしまい求解が難しくなってしまうことと、整数変数を用いた問題に適用できなくなってしまうからです。

ここでは最大値の最小化、最小値の最大化といったタイプの定式化を紹介します。まず、目的関数

 minimize max(a,b) 

のような最大値の最小化の場合は、以下のように新たに変数を導入して定式化します。

 Variable v;
 a <= v;
 b <= v;
 Objective obj(type = minimize);
 obj = v;

最小値の最大化に関しても同様のアプローチで行うことができます。

しかしながら、この方法では最大値の最大化や最小値の最小化を行うことができません。このような場合でも、問題によって定式化可能なケースもありますので、お気軽にNumerical Optimizer サポート担当 までご連絡ください。

また、Numerical Optimizer V10 より WCSP では min/max 関数の機能が強化されました。具体的には min/max 関数の中で最小(大)値が線形式で定義された場合には非常に高速に処理することができます。

詳細は 最適化メールマガジン バックナンバー ( 2008 Vol.1 ) をご覧ください。

最適化のアルゴリズムを切りかえる方法を教えてください。

モデルファイルに以下のように記述します。指定がないと Numerical Optimizer は問題の性質によって自動で設定します。solve 関数を呼ぶ場合は solve(); の前にアルゴリズムを指定します。

LP 用アルゴリズム

    options.method = "higher";
    options.method = "simplex";

QP (凸) 用アルゴリズム

    options.method = "asqp";
    options.method = "line";

SDP 用アルゴリズム

    options.method = "lsdp";
    options.method = "trsdp";

その他一般の非線形計画問題用アルゴリズム

    options.method = "tipm";
    options.method = "trust";

制約充足アルゴリズム

    options.method = "wcsp";
    options.method = "rcpsp";

アドオンモジュール Numerical Optimizer/Global

    options.method = "global";

ここではよく使われるアルゴリズムを挙げましたが、Numerical Optimizer に備わっている全てのアルゴリズムについては Numerical Optimizer/SIMPLE マニュアルをご参照ください。

文字列を添字とする定数にモデルの中から直接値を与えたい。

 a[orange] = 5; // 誤り

のようにすると、コンパイルエラーになります。

 a["orange"] = 5; // 正しい

のように引用符(") で囲ってください。日本語や添字の組みあわせを使うこともできます。

 b["みかん"] = 5;
 c["みかん,個数"] = 5;

モデルファイル内で使用できない文字などはありますか?

Numerical Optimizer GUI では name 属性で入出力 csv ファイルを作るため、Windows のファイル名として許可されていない文字を使うことはできません。具体的には「\/:*?"<>|」が使用できません。半角 / を全角/にするなど、代わりの文字をお使いください。mknuopt.bat を用いてコマンドラインから Numerical Optimizer を用いる場合は、この限りではありません。

式で表現できない問題を扱いたい。

回路解析、プラントエンジニアリングなどでは、素子や機器の特性値は式ではなく何らかの言語で書かれたコードとして表現されることが多いようです。そのような場合に Numerical Optimizer を利用するには以下の方法があります。

上記のうちどの方法が良いかは問題(コード)の複雑さや規模にも依存しますので一概に判断することはできませんが、具体的な問題をお持ちの方は是非 nuopt-info@msi.co.jp までご連絡ください。

変数を定数として扱いたい。

変数を定数として扱いたい場合は、下記のように変数 x に対して等式制約を追加します。

x == 1; 

変数 x が添字付けられており一部の要素についてのみ定数として扱いたい場合は、下記のように記述します。

x[2] == 1;

計算に用いるデータによって定数としたい要素が異なる場合は、モデルファイルに

Set S, Fix(superSet=S); 
Element i(set=S), fix_i(set=Fix); 
Parameter a(index=fix_i); 
Variable x(index=i); 
x[fix_i]==a[fix_i]; 

のように記述し、データファイルに

a = [2] 1; 

のように、定数として扱いたい要素の成分のみを定義します。

定数の値を変更したい。

モデルファイルの中で Parameter の値を変更して何度も求解したい場合があります。このような場合 Numerical Optimizer では VariableParameter を使用します。下記は VariableParameter vp を x の下限として利用する場合の例です。

VariableParameter vp;
...
x >= vp;
...
for(i = 0; i < n; i++){
  vp = p[i];
  solve();
}

Parameter 型の値を double 型として扱いたいのですが。

Parameter 型の値は

(Parameter型).val.asDouble()

と記述することで double 型として扱うことができます。

変数の初期値はどのようにして与えますか。

パラメータ Parameter と同様に変数 Variable に値を設定することにより初期値を設定できます。モデルファイル内で設定する場合は、以下のように記述します。

Variable x(name = "x"); 
x = 1.0; 

上記の記述により変数 x には初期値 1.0 が設定されます。

初期値を明示的に設定しない場合、Numerical Optimizer 内部では初期値が 0 と設定されます。 ただし、変数の上限または下限を設定している場合には、 上下限制約を守るように初期値を変更する場合があります。

ただし、アルゴリズムとして分枝限定法を用いる場合は、初期値を設定することはできません(設定しても無視されます)。

変数の初期値の設定はどのようなケースで有効なのでしょうか。

初期値の設定は、内点法をアルゴリズムとして使用する場合のみ有効です。非線形計画問題で局所解のあるケース、実行可能領域が連結でないケース等においては初期値の設定が有効な可能性があります。

実行不可能なケースにおいてすごく時間がかかっています。

問題が実行不可能な場合 IIS 機能において時間を要する可能性があります。いくつかの方法で IIS 機能をオフにすることが可能です。一つはモデルファイルの solve() 前に下記を追加する方法です。

options.iisDetect="off"; 

もう一つはパラメータファイル nuopt.prm に下記を追加する方法です。

param:iis=off 

集合の和、差の演算を行いたい。

Numerical Optimizer では「|」、「-」演算子によりそれぞれ集合の和、差の演算を行うことができます。また、setOf を使用することによる差集合を取得することも可能です。以下は SIMPLE による和集合と差集合の記述例です。

Set A = "a b c";
Set B = "a d e";
Set S = A | B;
S.val.print();//S=("a" "b" "c" "d" "e")
Set C = "a b c d";
Set D = "a c";
Element i(set=C);
Set T = C - D;
Set U = setOf(i, !(i<D));
T.val.print();//T=("b" "d")
U.val.print();//U=("b" "d")

詳細は Numerical Optimizer/SIMPLE マニュアル(V8) をご覧ください。Numerical Optimizer/SIMPLE マニュアル(V8)はこちらから入手することが可能です。

Element をイテレータとして利用したい

以下のように Element に付随する集合を OrderedSet として宣言します。

OrderedSet S = "1 .. 10"; 

上記のように記述しますと、Element をイテレータとして利用できます。以下記述例です。

Element i; 
for(i=S.first();i<S;i=S.next(i)){ 
   ..... 
}

OrderedSet の詳細につきましては「Numerical Optimizer/SIMPLE マニュアル」や「Numerical Optimizer/SIMPLE 例題集」等を参考にしてください。Numerical Optimizer のマニュアルは こちら からダウンロードできます。

モデルのビルドにすごく時間がかかります。

考えられる原因の1つに以下が挙げられます。

モデリング言語 SIMPLE は大規模な問題に対応するため、構造だけをモデルファイル(.smp ファイル)に書いて、係数の値に相当する部分は全てデータファイル(.dat ファイルや .csv ファイル)に記述する思想で実装されています。

例えば線形制約であれば、モデルファイルに

Set Row,Col;
Element j(set=Col);
Element i(set=Row);
Parameter A(index=(i,j));
Parameter b(index=i);
Variable x(index=j);
sum(A[i,j]*x[j],j) >= b[i];

showSystem();

といった記述をし(モデルの構造を示します)、データファイルにおいて

A = [1 1] 1.5 [1 2] 7.2 
    [2 1] 3.5 [2 2] 1.2
;
b = [1] 8 [2] 2 ;

と記述してデータを与えます。実行すると showSystem() 命令に対応して以下のように解釈されている様子が伺えます。

1-1 (model.smp:8[1]): 1.5*x[1]+7.2*x[2] >= 8
1-2 (model.smp:8[2]): 3.5*x[1]+1.2*x[2] >= 2

もちろん、この程度の規模であれば

1.5*x[1]+7.2*x[2] >= 8;
3.5*x[1]+1.2*x[2] >= 2;

のようにモデルファイルへ定式を直接書いても時間を要することはありません。

ただ、「式の構造を定義して係数はデータで」という使い方に対応するように、SIMPLE の記述は大きな計算負荷を計算機に(特にコンパイラに)強いてしまうため、記述が数万行のレベルになると式の解釈に非常に時間がかかってしまいます。したがって、大規模問題においては問題の構造のみをモデルファイルに記載し、係数データをデータファイルから分離して与えなければ実用的ではないことになってしまいます。

一般的な MILP 問題をモデルとデータを分離した格好で記述した例が milp.zip にあります。このような方法であれば、数万変数程度の大規模問題でもソルバー起動までに大きな時間を所要することはありません。

SIMPLE のモデル記述には定式の構造を簡便に記述するための道具や tips があるため、マニュアルや例題集などを見て記述方法がわかりにくい点については、お気軽に Numerical Optimizer サポート担当 までご連絡ください。

異なるバージョンの SIMPLE モデルに互換性はありますか?

モデリング言語 SIMPLE は後方互換性を保ち続けているため、バージョンアップを行っても SIMPLE モデルはそのまま使えます。

しかしながら、定式化が同一でも数理計画アルゴリズムを実行する部分の実装は更新を続けているため、数値計算であるという性質上、旧バージョンと新バージョンで完全に同一の結果を与えることは保証できません。

ただ、総体的に考えてプログラムの安定性と精度、速度は、バージョンアップを行うごとに確実に向上していることを確認しております。

もし、旧バージョンと比べて問題など生じた場合は、お気軽に Numerical Optimizer サポート担当 までご相談ください。