Nuorium 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）の表現など簡潔にモデルが記述できます。

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

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

モデルを自分で書くことに不安を感じる方は、まずは Nuorium Optimizer の使い方を学ぶために毎月開催している無料のセミナーにご参加ください。こちらでモデリング言語 SIMPLE の基本的な使い方や Nuorium に慣れ親しみ、典型的な問題に対する定式化を学ぶことができます。

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

もし定式化にお困りの際は無料個別相談会や有償コンサルティングの利用をご検討ください。有償にはなりますが、貴社向けに分野や業界に特化した数理最適化の特別セミナーを開催することも可能です。nuopt-support@msi.co.jp までお気軽にご連絡ください。

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

製品のご利用方法については無料セミナーへの参加を推奨いたします。 SIMPLE の記述方法を実際に例題を通して記述しながら習得できるコースを用意しております。一通りの基本的な文法を学べるため、大変オススメです。

既に製品を購入されている場合は以下の段階に分けて習得するのが効率的です。

数理モデルの定式化に不慣れである。
ナップサック問題のような簡単な数理モデルを定式化できる。
様々な数理モデルを知っている、もしくは定式化できる。

それぞれの場合で習得方法について述べます。

数理モデルの定式化に不慣れ

SIMPLE チュートリアルを用意しております。こちらをご参照ください。

SIMPLE チュートリアルでは数理計画問題とはそもそもどういうものか、といった基本から紐解きながらソフトウェアの利用方法についても、簡単な例題を通しながら同時に理解できるよう解説しています。

簡単な数理モデルを定式化可能

既に記述したい数理モデルが具体的であれば、「変数」「制約条件」「目的関数」などの数式をほとんどそのまま記述することで、 SIMPLE が記述できるため、SIMPLE マニュアルや Nuorium スタートガイドを参考に比較的容易に学習をスタートできます。

様々な数理モデルについての知識がある

SIMPLE 例題集には、豊富な例題が問題文と記述例およびデータとともに掲載されており、いろいろな具体例を通して SIMPLE の実際の記述方法を学べます。

またスキルアップセミナーと題して、実務の導入も意識したより高度な利用方法について無料で受講できます。併せてご検討ください。

整数変数を使いたい。

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

IntegerVariable x;

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

IntegerVariable x(type=binary);

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

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

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

集合 S に含まれる添字 i のみで変数 x[i] の和をとる場合

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

パラメータ a[i] が 0 の添字 i のみで変数 x[i] の和をとる場合

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

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

集合 S に i が含まれる場合のみ変数 x[i] を 1 に等しくさせたい場合

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

パラメータ a[i] が 0 の場合のみ変数 x[i] を 1 に等しくさせたい場合

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

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

変数 y[i] を条件式部分に含める

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

a <= x <= b or c <= x <= d のように制約式の or は表現可能ですか？

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

IntegerVariable y(type=binary);
a * (1 - y) + c * y <= x <= b * (1 - y) + d * y;

こう書くと、y=0 のときは a<=x<=b となり、y=1 の時は c<=x<=d となります。

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

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

options.noDefaultSolout = 1;

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

また、一般に解ファイル（モデル名.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;

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

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

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

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

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

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

LP 用アルゴリズム

LP 専用内点法

options.method = "higher";

単体法(整数計画問題にも対応)

options.method = "simplex";

QP (凸) 用アルゴリズム

有効制約法(整数計画問題にも対応)

options.method = "asqp";

SDP 用アルゴリズム

線形半正定値計画問題に対する主双対内点法

options.method = "lsdp";

信頼領域法を用いた非線形半正定値計画問題に対する主双対内点法

options.method = "trsdp";

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

一般の非線形計画問題用内点法

options.method = "tipm";

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

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

a[orange] = 5; // 誤り

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

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

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

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

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

変数を定数として扱いたい場合は、下記のように変数 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 の値を変更して何度も求解したい場合があります。このような場合 Nuorium 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 が設定されます。

初期値の設定は、内点法、分枝限定法、wcsp タブーサーチ及び rcpsp タブーサーチにおいて有効で他のアルゴリズムでは設定された初期値は探索に利用されません。

分枝限定法ではユーザが設定した初期値が制約式を満たす場合に限り採用されます。

wcsp タブーサーチではオプション wcspInitialValueActivation を "on" に設定した場合、ユーザの設定した値を初期値として探索が始まります。

rcpsp タブーサーチでは探索における Activity の初期値を指定することができます。

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

初期値の設定は、内点法、分枝限定法、wcsp タブーサーチ及び rcpsp タブーサーチにおいて有効です。

内点法では設定された初期値を探索の出発点として採用します。特に非線形計画問題においては以下のようなケースで有効である可能性があります。

局所解が大域最適解とは保証されないケース
実行可能領域が連結でないケース
探索点によっては関数評価で浮動小数点エラーが発生する可能性がある場合

分枝限定法では枝刈りに用いられ、実行可能解が見つかりづらいが別のロジックでは見つけやすい場合などに有効です。

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

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

options.iisDetect="off";

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

param:iis=off

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

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

OrderedSet S = "1 .. 10";

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

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

OrderedSet の詳細につきましては「Nuorium Optimizer/SIMPLE マニュアル」や「Nuorium Optimizer/SIMPLE 例題集」等を参考にしてください。

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

考えられる原因の 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 があるため、マニュアルや例題集などを見て記述方法がわかりにくい点については、お気軽に Nuorium Optimizer サポート担当までご連絡ください。

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

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

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

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

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