数理最適化セミナーのご案内

6.9 最小（大）値取得関数min，max

　wcsp使用時には，最小値取得関数min及び最大値取得関数maxは，第一引数を定数式ではなく式にすることもできます． 

// 添字の範囲にわたる最小値
Expression   min(式, 範囲指定並び)       // 戻り値は一般の式
// 添字の範囲にわたる最大値
Expression   max(式, 範囲指定並び)       // 戻り値は一般の式

　ここでいう「範囲指定並び」は，関数の適用範囲となる添字の範囲です．添字そのもの，あるいは条件づけられた添字が入ります．

　第一引数が式の場合には，内部でwcsp専用の特別な処理を行うため良好なパフォーマンスが期待されます．

　次の例では施設配置問題の「最寄りの施設に収容される」という制約をmin関数を用いて表現しています． 

Set Mesh;// メッシュ集合
Element i(set = Mesh);
Set Facility;// 施設集合
Element j(set = Facility);

// メッシュiが施設jに収容されるならば1そうでないならば0
IntegerVariable x(type = binary, index = (i, j));
// 施設jが建設されるならば1されないならば0
IntegerVariable y(type = binary, index = j);
// メッシュiから施設jまでの距離
Parameter dist(index = (i, j));

// 制約，各メッシュは1つの施設に対応される
selection(x[i, j], j);

// メッシュiから収容される施設までの距離
Expression res_dist(index = i);
res_dist[i] = sum(x[i, j] * dist[i, j], j);

// メッシュから収容される施設は，建設された施設の中では
// 最寄のものとする
Parameter M;// 十分大きい数
M = 1000000;
res_dist[i] <= min((1 - y[j]) * M + dist[i, j], j);

// 以下はmin関数を用いないで定式化する場合の記述方法
// res_dist[i] <= (1 - y[j]) * M + dist[i, j];

　wcsp以外のアルゴリズム選択時で，式に対しmin関数やmax関数を用いるような定式化を行いたい場合には，上記の例題記述においてコメントで示されているように非線形な記述を用いない等価な書き換えが存在します．min/max関数の定式化や求解について，より詳細にはnuopt-support@ml.msi.co.jpまでお問い合わせください．

6.8 ブール関数Boolean
6.10 カウント関数count

 

 

上に戻る