1. C++SIMPLE と PySIMPLE の代表的相違点#

1.1. 背景#

モデリング言語 SIMPLE の実装系には C++SIMPLERSIMPLE があるが, その中でも PySIMPLE は最後発に位置している.

このためこれまでの言語開発の中で培われた様々なノウハウを注意深く検討し, より洗練された記述方式となるよう,一から設計された言語となっている.

C++SIMPLE のユーザが PySIMPLE を初めて手にするとき, 根底では SIMPLE という設計思想を同じにするため, まったく別の言語に移行する場合と比較して学習コストは格段に低い. しかしながら,よく似た相違点であるとか,PySIMPLE 固有の考え方といった点については, C++SIMPLE ユーザを戸惑わせてしまうかもしれない.

そこで以下ではそれらの点に絞って,PySIMPLE の特徴を述べるものである. またこれらの記述は最初から PySIMPLE ユーザとなる方でも, PySIMPLE の習熟のために有益な情報は多く役立つことだろう.

Tip

最新版の PySIMPLE マニュアルは下記 URL にある. https://www.msi.co.jp/solution/nuopt/docs/pysimple/index.html

1.2. 素朴な LP の対比#

言語の違いを大まかに探るには,あまり単純すぎないが,しかし最低限のことが可能なサンプルコードを比較することが重要であろう. 次は二変数の非常に素朴な LP である.各言語の違いを比較してほしい.

 1// LP
 2Variable x;
 3Variable y;
 4Objective costTotal(type = minimize);
 5costTotal = 180*x + 160*y;
 66*x + y >= 12;
 74*x + 6*y >= 24;
 80 <= x <= 5;
 90 <= y <= 5;
10solve();
11
12x.val.print(); // x=1.5
13y.val.print(); // y=3

上記のサンプルコードから,C++SIMPLE と比較して,PySIMPLE には次の特徴があるとわかる.

  • C++SIMPLE と違い,PySIMPLE は Python のモジュールとして直接に実装されているため,各種のオブジェクトは import する必要がある.

  • 変数の上下界を宣言時に lb=0, ub=5 などと指定できる.

  • 目的関数と制約条件は Problem オブジェクトを import し,そのインスタンスへ += によって登録する.

  • 目的関数の最適化の種別は C++SIMPLE と同じく type= で指定するが,値は C++SIMPLE が minimizemaximize であるのに対して,PySIMPLE では minmax である.
    • 指定がない場合は何れの SIMPLE も最小化として解釈される.

  • 変数は Problem オブジェクトに直接登録する必要がない.

  • 解は .val で参照できる.簡易的な print デバッグなどは,Python の組み込み関数 print によって可能である.

1.3. 変数の種類#

Element オブジェクト i が与えられているとき, 各 SIMPLE で変数は次のように宣言する. PySIMPLE では幾つかの等価な書き方が存在する.

1Variable x(index=i);
2IntgerVariable z(index=i);
3IntgerVariable b(index=i, type=binary);

1.4. 添字の扱い#

PySIMPLE では Element オブジェクトの扱いに大きな特徴がある.個性といってもよい. これを自在に扱えるようになることは,PySIMPLE への理解も一層深まったことを意味する.

1.4.1. 集合と添字の関係#

C++SIMPLE では Set オブジェクトがあって,それに紐づく形で Element オブジェクトを宣言することが標準的だった. PySIMPLE でも C++SIMPLE と同様に Set オブジェクトに紐づく形で宣言することができる.

1Set I = "1 2 3";
2Element i(set=I);
3Variable x(index=i);
4Parameter A(index=i);

一方で,C++SIMPLE ではどこにも紐づかない Element オブジェクトを利用することもできるが,どちらかといえば限定的な使用例であった. 場合によっては推奨されていないこともよくある. しかし PySIMPLE では Elementvalue キーワードを用いて,集合を経由せずに直接添字を定義して用いることが多用される. もしくは変数や定数などの添字を司る index キーワードに Set のインスタンスを直接指定することもできる. これは C++SIMPLE の発想でいると,標準的ではないインスタンスの扱いとなるため,C++SIMPLE ユーザの場合にはその違いに慣れる必要がある.

1from pysimple import Element, Variable, Parameter
2
3i = Element(value=[1, 2, 3])
4x = Variable(index=i)
5A = Parameter(index=i)

PySIMPLE では添字から \(.set\) によって集合を参照することもできる. これによって新たな添字の宣言もできる.

1from pysimple import Element
2
3i = Element(value=[1, 2, 3])
4print(i.set) # i.set=Set(value=[1, 2, 3])
5j = Element(set=i.set)
6print(j.set) # j.set=Set(value=[1, 2, 3])

1.4.2. 添字付け#

\(A_{i,j,k}\) という定数 (変数も同じ) があったとき,これらの添字がとりうる値に数値と文字列値の複数がある場合に, 例えば \(A_{1,'p','q'}\) を指定したいことがあったとしよう. これを C++SIMPLE で表現するには悪い意味で難解な構文規則を理解する必要があった.

https://www.msi.co.jp/solution/nuopt/docs/SIMPLE/html/12-03-00.html

しかし PySIMPLE では次のように,単に個別に文字列について区切って,それそのまま指定した記述とすればよい.

1A[1,'p','q']

1.4.3. 条件式を用いた添字の定義#

PySIMPLE では新たな Element を, 既に定義した Element のインスタンスが満たすべき条件式を用いて定義できる. 同様のことを C++SIMPLE で行うには,その条件式を反映した Set を作るところから始める必要があった. この違いは大きく,PySIMPLE のコードにはその特徴が随所で表れることになる.

例えば偶数だけをとりうる添字 \(ieven\) はそれぞれの SIMPLE で次のように記述される.

1Set I = "1 .. 6";
2Element i(set=I);
3Set I_EVEN = setOf(i, i%2==0);
4Element ieven(set=I_EVEN);

この他,漸化不等式 \(x_i\leq x_{i+1}\) を定義するのに,境界条件の取り扱いがそれぞれ次のようになる.

1Set I = "1 .. 4";
2Element i(set=I);
3Variable x(index=i);
4x[i] <= x[i+1], i!=4;

C++SIMPLE では制約条件式に続けて,カンマ演算子 , で区切ってあたかも数式のように条件式を記述できる. しかしこのカンマ演算子の構文はしばしばテストが必要になる箇所であり,用心すべき記述である. 対して PySIMPLE はそのような不安からいくらか解放される記述を提供してくれる.

バイナリ変数 \(x\) について求解値が \(1\) の場合のみ標準出力したい場合ことがよくあるだろう. この場合にも PySIMPLE では条件式から添字を生成して記述する.

1Set I = "1 .. 4";
2Element i(set=I);
3IntegerVariable x(index=i, type=binary);
4sum(x[i], i) == 1;
5options.outputMode = "silent";
6solve();
7simple_printf("x[%d] = %d\n", i, x[i].val, x[i].val==1);

上記の PySIMPLE のサンプルコードで,添字 i1 を使い回さないのであれば, 出力を次のように書き換えてもよい.

1print(x[x[i].val==1].val)

注釈

PySIMPLE では get メソッドを使った書き方も提供されている. https://www.msi.co.jp/solution/nuopt/docs/pysimple/guide/get.html

頻出する式構造 の一つである SOS2 のような特徴を持った式を書きたい場合に,適切な添字を指定する必要がある. この種の記述は out of range の温床になりえる. get メソッドはこの手の記述を簡潔にし,より制御しやすいコーディングを提供する.

1.5. 式の添字扱い#

1.5.1. C++SIMPLE との基本的な対応#

PySIMPLE では C++SIMPLE と違い,式 (Expression) の定義にあたって添字の指定が必要ない. また添字位置の指定は C++SIMPLE が 1 始まりに対して,PySIMPLE は 0 始まりと一貫している.

1// Dense Case
2Expression foo(index=(i, j));
3foo[i, j] = a[i, j] * x[j];
4
5// Sparse Case
6Set IJ(dim=2); Element ij(set=IJ);
7Expression foo(index=ij);
8foo[ij] = a[ij] * x[ij.at(2)];
9foo[i, j] = a[i, j] * x[j], (i, j) < IJ;

1.5.2. C++SIMPLE との注意すべき対応#

1.5.2.1. 添字の位置順序#

PySIMPLE では添字位置を指定することなく式を定義できるため,簡便ではあるものの, 添字の位置順序という概念はあるので,どのように内部的に順序が決定しているのか知っておく必要がある.

その規則は単純で右辺値にある定義式について,添字が記述された順序に従う,というものである.

例えば foobar が次で定義されたならば, foo[i,j] であり bar[j,i] である. 左から早い順に添字順序が決定する.

1foo = a[i, j] * x[j]
2bar = x[j] * a[i, j]

それ故に PySIMPLE のコーディングでは上記を意識した式の整理が暗黙に行われる.

1.6. 集合の扱い#

1.6.1. 集合の順序構造#

C++SIMPLE では順序構造を持つ集合を定義する場合には,OrderedSet のように専用のクラスを宣言する必要があった.

PySIMPLE では Set がオブジェクト生成時点での value の並びを順序として生成されるため, すべての Set が順序構造を持っている. そして PySIMPLE の Set は C++SIMPLE の集合オブジェクトと違い生成後には値を変更できないため,生成時に決定した順序は完全に保存される.

1.6.2. 集合の自動代入#

データファイルが与えられることで,その情報から定数の添字範囲が決定するため, C++SIMPLE では宣言されている集合オブジェクトの要素がそれらデータファイルの読み込みに応じて決定するという, 集合の自動代入機能があった.

しかしこの機能は PySIMPLE にはない. PySIMPLE では C++SIMPLE のように Parameter 宣言に沿ったデータの読み込み順序で集合要素が変化することはない. PySIMPLE の Set は値が変更できないからである.

1.6.3. 集合要素の参照#

集合の要素へのアクセスは [] で行う.

1from pysimple import Set
2
3S = Set(value=[(1, 10), (2, 20), (3, 30), (4, 40)])
4print(S[0]) # (1, 10)
5print(S[-1]) # (4, 40)
6print(S[0::2]) # [(1, 10), (2, 20)]

注釈

PySIMPLE では空集合の場合を除いて,dim の明示的な指定は不要である. つまり S = Set(dim=2, value=[(1, 10), (2, 20), (3, 30), (4, 40)]) というように, dim=2 を書く必要はない.

多次元集合の抽出は () で行う 1抽出については定式化技法集の 射影と抽出 を参照せよ.

1from pysimple import Set
2
3S = Set(value=[(1, 10), (2, 20), (3, 30), (4, 40)])
4print(S(0)) # Set(name='S(0)', value=[1, 2, 3, 4])
5print(S(0)[2]) # 3
6print(S(0, 1, 0)) # Set(name='S(0,1,0)', dim=3, value=[(1, 10, 1), (2, 20, 2), (3, 30, 3), (4, 40, 4)])
7print(S(0, 1, 0)[2]) # (3, 30, 3)

集合の要素数は len で行う.

1from pysimple import Set
2
3S = Set(value=[(1, 10), (2, 20), (3, 30), (4, 40)])
4print(len(S)) # 4

1.7. 疎な記述#

PySIMPLE での疎な記述は,疎な多次元集合に属する添字を宣言するか,直接に疎な添字を宣言して用いて記述する.

1sum(x[i, j], (j, (i, j) < IJ)) == 1;

1.8. 定数の扱い#

C++SIMPLE ではデータファイルで読み込まれなかった添字に関する Parameter の値は 0 として評価された. このことは PySIMPLE に至っても全く同様である.

PySIMPLE の値の設定方法は以下の何れかである.

  • 何も設定しない.
    • 0 が設定される.

  • value 属性にスカラー値を設定する.
    • すべての添字について一律に設定したスカラー値が設定される.

  • value 属性に辞書を設定する.辞書のキーを添字として,辞書の値が設定される.

  • 後で代入する.
    • 代入した値が設定される.

1.9. 定式化要素の確認#

C++SIMPLE では定式化に要した目的関数や制約条件が確かに記述できているか, showSystem 関数を用いて確認できた.

PySIMPLEでは Problem オブジェクトに紐づく objective プロパティと constraints プロパティに, それらの情報が格納されている. C++SIMPLE では目的関数だけを確認することができなかったが,PySIMPLE ではそれが可能である.

 1Set I = "1 .. 3";
 2Element i(set=I);
 3Variable x(index=i);
 4Parameter A(index=i);
 5A[i] = i;
 6
 7Objective f(type = minimize);
 8f = sum(A[i]*x[i], i);
 9
10Objective g(type = maximize);
11g = -sum(A[i]*x[i], i);
12
13Constraint Co1;
14Co1 = sum(x[i], i) >= 10;
15Constraint Co2(index=i);
16Co2[i] = x[i] >= 0;
17
18options.noDefaultSolve = 1;
19
20// すべての目的関数およびすべての制約条件式を出力する.
21// [Expand Constraints and Objectives] に続けて出力されうる.
22printf("\n=== showSystem(); ===\n");
23showSystem();
24
25// 目的関数だけが対象とはならず,出力はすべての目的関数とすべての制約条件式を含んだ全体になってしまう.
26printf("\n=== showSystem(f); ===\n");
27showSystem(f);
28
29// 制約条件式 Co1 を出力する.
30printf("\n=== showSystem(Co1); ===\n");
31showSystem(Co1);
32
33// 制約条件式 Co2 のすべてを出力する.
34printf("\n=== showSystem(Co2); ===\n");
35showSystem(Co2);
36
37// 制約条件式 Co2 のうち,直接指定した場合を出力する.
38printf("\n=== showSystem(Co2[3]); ===\n");
39showSystem(Co2[3]);
40
41// 制約条件式 Co2[i] のうち条件を満たす場合を出力する.
42printf("\n=== showSystem(Co2[i], i <= 2); ===\n");
43showSystem(Co2[i], i <= 2);

技法集

用語集

引用書式

BibTeX