-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= 数理システム NUOPT メールマガジン http://www.msi.co.jp/nuopt/ 2008 Vol.1 ( 2008 年 2 月 15 日 発行 ) -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= 数理システム NUOPT メールマガジンでは，数理計画法パッケージ NUOPT に関する様々な情報やご案内を提供していきます． ++++ [目次] +++++++++++++++++++++++++++++++++++++++++++++++++++++ ■ <トピック> NUOPT V10 のリリースにあたって ■ <トピック> WCSP の新機能を用いた例題のご紹介 ■ <トピック> 「NUOPT ソリューションページ」のご紹介 ■ <トピック> 出展・発表案内（日本 OR 学会 2008 年春季研究発表会） ■ <セミナー> NUOPT 無料セミナーのご案内 ■ <セミナー> NUOPT 無料紹介セミナー 金融工学特集 開催中 ■ < tips > SIMPLE よくある間違い（第 4 回） +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ ***************************************************************** ■ <トピック> NUOPT V10 のリリースにあたって ***************************************************************** 日頃数理計画法パッケージ NUOPT に関心をお持ちいただき，まことにあり がとうございます．開発責任者の田辺でございます．この度 V10 がリリー スされる運びとなりました． V10 は非線形半正定値計画問題への対応を始めとして，WCSP の機能強化， GUI の改善など，数理計画の現場のニーズに応える様々な新機能を盛り込 みました．また，例題集には，相関行列の推定やロバストポートフォリオ 最適化への非線形半正定値計画問題の応用，メタヒューリスティクスを用 いたスケジューリング機能 RCPSP を用いた例題など，新機能を含めた実務 的な利用例を増強しております．WCSP の機能強化については，モデリング 言語 SIMPLE に「最大・最小」という関数の近傍取得機能を組み込みまし た．これにより，メタヒューリスティクスの応用に新たな展開がもたらす ことが出来ればと願っています（下のトピックに掲載した例題をご参照く ださい）． （田辺 隆人） ****************************************************************** ■ <トピック> WCSP の新機能を用いた例題のご紹介 ****************************************************************** 年間のピーク需要にあわせて締結しなければならないならない電力基本契 約や，ピーク需要をまかなわねばならない冷暖房機器，どんなに遅くとも 3 分以内に到着しなければならない救急車，想起される様々なシナリオに おいて少なくとも一定以上の利潤を確保したいポートフォリオ，など，数 理計画モデルには，「最大，最小」を扱う定式が数多く現れます． そんな場合に，用いられるのが ------------------------------------------------------------------ Set Case; Element i(set=Case); // i は Case を動く添字 Expression g(index=i); // 関数群 Variable s; // 最大を示す変数 ... g[i] <= s; Objective f(type=minimize); f = s; ------------------------------------------------------------------ といったモデル記述です．上は Case の集合において定義される g[i] と いう関数の最大を最小化する例です．数理計画アルゴリズムの多くはモデ ルに現れる関数の微分可能性を前提としていることから，このような記述 は頻繁に用いられます．しかし，微分可能性を前提としないメタヒューリ スティクスアルゴリズムでは，このような古典的な変形をして制約を増大 させる必要はそもそもないはずです． V10 でメタヒューリスティクスアルゴリズム WCSP を用いる場合には，上 記に類する問題においては，そのまま f = max(g[i],i); と書けばよいのです．g[i] が線形関数である場合には，近傍探索ルーチン が max 関数向けにチューニングされているので，古典的な記述より大幅に 高速です． 以下は，メタヒューリスティクスエンジン wcsp を用いた若干実務的な例 題です（V10 の例題集から抜粋しました）．スポット電力を購入し電力を まかなっている工場が，自家発電用の発電機の導入を計画する問題です． ------------------------------------------------------------------ Set Spot; Element i(set=Spot); // スポット電力 Set Time; Element t(set=Time); // 時刻 Set Dynamo; Element j(set=Dynamo); // 発電機 Parameter spotCost(index=i); // スポット電力の単位時間あたりのコスト Parameter dynamoCost(index=j); // 発電機に対する導入コスト Parameter spotPower(index=i); // スポット電力の単位時間あたりの出力 Parameter dynamoPower(index=j); // 発電機の単位時間あたりの出力 Parameter Demand(index=t); // 各時刻における電力需要 // 各時刻でどのスポット電力を購入するか IntegerVariable u(index=(i,t), type=binary); // 発電機を購入するか否か IntegerVariable x(index=j, type=binary); // 目的関数(総コスト) Objective totalCost(type=minimize); totalCost = sum(spotCost[i]*u[i,t],(i,t))+sum(dynamoCost[j]*x[j],j); // 制約式(任意の時刻においてスポット電力はいずれか一つを選択) selection(u[i,t], i); // 制約式(出力電力が電力需要を上回らないといけない) max(Demand[t] - sum(spotPower[i]*u[i,t], i), t) <= sum(dynamoPower[j]*x[j],j); ------------------------------------------------------------------ 最後の制約式が，すべての時刻で出力電力が電力需要を上回る，という部 分です．古典的な書き方に対して，制約式の数も少なく，また特化された 近傍探索ルーチンが利用される分，高速です． （多田 明功） ***************************************************************** ■ <トピック> 「NUOPT ソリューションページ」のご紹介 ****************************************************************** 弊社 Web サイトでの NUOPT 紹介ページでは，従来 NUOPT の機能説明がメ インでありましたが，今後は，NUOPT の応用事例を中心としたページを充 実させていく予定です． まずは第一弾として，「GIS ソリューション」として施設配置問題や配送 計画問題などの事例を紹介しております．「GIS ＝ 地図情報システム」と NUOPT を融合させ，入出力を地図画面と共に表示させることにより，ビジュ アル性が高く直感的で使いやすいアプリケーションシステムが実現できま す．是非とも，システム構築事例をご覧になってください． 詳細は，http://www.msi.co.jp/nuopt/solution.html を． 今後もメタヒューリスティクスアルゴリズムを活用したシフトスケジュー リングソリューションなどを加え，内容をさらに充実させていく予定です． （坂田 昌一） ****************************************************************** ■ <トピック> 出展・発表案内（日本 OR 学会 2008 年春季研究発表会） ****************************************************************** 3 月 25 日（火）・26 日（水）に京都コンピュータ学院（京都駅前校）で 日本オペレーションズ・リサーチ学会 2008 年春季研究発表会が開催され ます．会場では今回も NUOPT の出展を行っておりますので，ご来場される 方はどうぞお立ち寄りください． また，25 日には「メタヒューリスティクスアルゴリズムの性質を用いた実 務的な 0-1 整数計画問題の高速な解法」という題目で発表を行ないます． 本発表では，上記のトピックでご紹介した，メタヒューリスティクスエン ジン WCSP に搭載される新機能について取り上げます．WCSP は近年重要性 が増している割当問題に対して絶大なる効果を発揮するソルバーです．メ タヒューリスティクスならではの高速化手法を余すことなくお伝えいたし ますので，ご興味のある方は是非ともお聞きいただきたく思います（ちな みに発表者は私です，分かりやすく説明できるよう頑張ります！）． なお，春季研究発表会の詳細につきましては OR 学会の Web ページ http://www.orsj.or.jp/nc2008s/ をご覧ください． （佐藤 誠） ****************************************************************** ■ <セミナー> NUOPT 無料セミナーのご案内 ****************************************************************** ---- [ NUOPT 無料セミナー 開催日程 ]------------------------------ ※ NUOPT 無料紹介セミナー ～ 体感しながら NUOPT 入門 ・ 2 月 25 日（月） 13:30 ～ 16:30 ・ 3 月 6 日（木） 10:30 ～ 17:00 << 金融工学特集 >> ・ 4 月 15 日（火） 13:30 ～ 16:30 ※ NUOPT 無料スキルアップセミナー ～ 実戦に向けての NUOPT 演習 ・ 2 月 27 日（水） 10:30 ～ 17:00 ・ 3 月 31 日（月） 10:30 ～ 17:00 ・ 4 月 25 日（金） 10:30 ～ 17:00 ------------------------------------------------------------------ NUOPT 購入前の検討材料として，そして NUOPT 購入後の操作習得の場とし て，弊社では，2 種類 NUOPT 無料セミナーをご用意しております． ※ NUOPT 無料紹介セミナー ～ 体感しながら NUOPT 入門 （NUOPT の購入を検討中の方にお勧めです） http://www.msi.co.jp/nuopt/seminar.html NUOPT の導入を計画中のお客様のためのセミナーです．本セミナーでは， NUOPT を適用したアプリケーションに実際に触れていただきながら，説明を 致します． 直近の紹介セミナーについては以下のとおりです． ・ 2 月 25 日（月） 13:30 ～ 16:30 ～ ビジネスリテラシーとしての数理計画法 ～ NUOPT が提供する数理計画法という手法は，企業の人員配置計画や工場設 備の最適運転方法など，意外なほどに広範囲なビジネスシーンで活用でき ます．企業内のごく一部の専門家が特殊な問題に適用する手法ではありま せん．これからは数理計画法を使いこなすことにより，ビジネス活動の付 加価値アップをもたらします．NUOPT を使い数理計画法を応用した事例を， 簡単かつ実用的なデモを交えながら紹介いたします． ・ 3 月 6 日（木） 10:30 ～ 17:00 ～ 金融工学特集 ～ 1 月 29 日の金融工学特集は，開催告知後まもなく定員に達してしまいま した．そこで前回と同内容で再度金融工学特集を開催いたします．なお， 今回もすでに多数のお申し込みを頂いておりますため，参加ご希望の方は 早めにお申し込みください． 詳細につきましては弊社 Web ページ http://www.msi.co.jp/nuopt/seminar_finance.html をご覧ください． ・ 4 月 15 日（火） 13:30 ～ 16:30 内容については，鋭意企画中です．近々に弊社 Web ページで告知いたしま す． 会場：（株）数理システム・セミナールーム （東京都新宿区新宿二丁目 3 番 10 号新宿御苑ビル 4 階） お申し込みは，（株）数理システム << NUOPT >> 担当 < nuopt-info@ml.msi.co.jp >まで ※ NUOPT 無料スキルアップセミナー ～ 実戦に向けての NUOPT 演習 （NUOPT の使い方をマスターしたい方にお勧めです） http://www.msi.co.jp/nuopt/skillupseminar.html NUOPT 購入後に操作方法の基礎を素早く習得することが目的のセミナーで す．簡単な例題から始めて，代表的ないくつな例題を演習形式で説明いた します．その際に，例題の制約条件式や目的関数等の一部分を実際に記述 していただき，モデリング言語 SIMPLE の記述に慣れていただくことが出 来るよう配慮しております． また，モデルの定式化のコツやアプリケーション開発のための連携処理に ついても，簡単にお話し差し上げる予定です。 なお，直近の開催日程は次のとおりです． ・ 2 月 27 日（水） 10:30 ～ 17:00 ・ 3 月 31 日（月） 10:30 ～ 17:00 ・ 4 月 25 日（金） 10:30 ～ 17:00 会場：（株）数理システム・セミナールーム （東京都新宿区新宿二丁目 3 番 10 号新宿御苑ビル 4 階） お申し込みは，（株）数理システム << NUOPT >> 担当 < nuopt-info@ml.msi.co.jp >まで （坂田 昌一） ****************************************************************** ■ <セミナー> NUOPT 無料紹介セミナー 金融工学特集 開催中 ****************************************************************** 去る 1 月 29 日（火），金融工学分野に特化した「NUOPT 無料紹介セミ ナー 金融工学特集」を開催いたしました． セミナー当日は，実際の問題を解く上で必須の定式化テクニックや最新の 事例紹介など，基本的な内容だけではなくマニアックな内容も含んでいた にも関わらず，参加者の皆様はメモをとりつつ，熱心に聞き入っており， 講師としても確かな手応えが感じられる一日でした． 今後も定期的に開催し，皆様のお声を反映させる形で研鑽を積む次第でご ざいます．ご興味がある方は是非ご参加ください． ※本セミナーは，実務に数理計画を数理計画を活用されている方から，金 融工学に対して数理計画ができることを知りたい方まで，金融工学に携わ る様々な実務家，研究者の方を対象にしています． ※参加者の皆様には本セミナーのために作成されたデモプログラムをお手 許で体験して頂きます（マシンは会場に準備しております）． （村山 昇） ****************************************************************** ■ < tips > SIMPLE よくある間違い（第 4 回） ****************************************************************** このコーナーでは，SIMPLE の記述に関して，お客様が陥りやすい間違い を少しずつですが紹介していきます． 今回も前回に引き続き，集合，添え字周りのよくある間違いを紹介したい と思います．前回紹介した工場から顧客への配送量を決定する配送問題の モデル ------------------------------------------------------------------ Set Factory; Element f(set=Factory); Set Customer; Element c(set=Customer); Variable x(index=(f,c)); Parameter cost(index=(f,c)), upper(index=f), lower(index=c); Objective cost_total; cost_total = sum(cost[f,c]*x[f,c],(f,c)); sum(x[f,c],c) <= upper[f]; sum(x[f,c],f) >= lower[c]; x[f,c] >= 0; ------------------------------------------------------------------ に以下のデータを入力ファイルとして与えることにします． ------------------------------------------------------------------ upper = [1] 250 [2] 450; lower = [A] 200 [B] 200 [C] 200; cost = [1,A] 3.4 [1,B] 2.2 [1,C] 2.9 [2,A] 3.4 [2,B] 2.4 [2,C] 2.5; ------------------------------------------------------------------ SIMPLE には添え字の自動代入機能があるので，Factory="1 2"， Customer="A B C" と集合の要素が定義され，upper, lower, cost にそれ ぞれ適切な値が代入されます． さて，ここで "工場 2 から顧客 A への配送を行わない" という制約を課 すためにモデルの最後部に x[2,A] == 0; を加えることにします．しかし，この文を追加したモデルをコンパイルす ると「A が定義されていない」というエラーメッセージが出力されてしま います．A という添え字はモデルの中では文字列として扱わなければなら ず， x[2,"A"] == 0; // --- (1) とする必要があるのです．数字の 2 に対しては，2，"2" どちらでも構い ません． では，(1) をモデルに追加するとどうなるでしょうか．実はこの場合，モ デルのコンパイル自体は成功しますが，実行時エラー（SIMPLE 67）となっ てしまいます．これは SIMPLE は文の解釈に C++ のコンパイラを利用して いるという実装上の都合によるものです．このエラーを回避し，意図通り の結果を得るためには， x["2,A"] == 0; とする必要があります． ここでは，紙面の都合上，正しく解釈されるためのルールを詳細に示すこ とはしませんが，Element 以外の添え字（ここでいう 2 や "A"）が連続し て現れる場合は，それらをまとめて "" で括る，と覚えておけば間違いは ありません．ただし，Element は "" で括ってはいけません． x["f,B"] == 0; は意図通り，つまり「全工場から顧客 B への配送量を 0 にする」とは解 釈されません．正しくは x[f,"B"] == 0; です．無論，この場合は顧客 B の需要を満たせないので infeasible に なってしまいます． また，実行時エラー（SIMPLE 67）のもう一つの回避策として， x[f,c] == 0, f == 2, c == "A"; のように，変数 x の添え字には Element を使い，条件式で添え字範囲を 指定するという方法もあります． 今回見てきたように SIMPLE には，文の解釈に C++ のコンパイラを利用し ているが故の文法的なルールというものが存在します（文の解釈に演算子 オーバーロードのメカニズムを利用しているためです）．次回は，このこ とを踏まえて添え字に関する解釈を少し詳細に見ていくことにします． （村山 昇） ================================================================== ※ このメールは，展示会・セミナー等で名刺交換をされた方，過去に NUOPT に関するお問い合わせを頂いたことのある方，および本メール マガジンの配信を希望された方にお送りしています． ※ バックナンバーはこちらから御覧頂けます． http://www.msi.co.jp/nuopt/mailmagazine/index.html ※ 本メールマガジンは等幅フォントでお読みになることを推奨します． ※ 今後このメールマガジンが不要な方は，誠にお手数ですが，「メール マガジン配信停止」という件名のメールを nuopt-magazine@ml.msi.co.jp にお送りください． 発行：株式会社 数理システム << NUOPT >> 担当 東京都新宿区新宿二丁目 4 番 3 号 フォーシーズンビル 10 階 ==================================================================