バックナンバー ( 2010 Vol.4 ) 2010 年 11 月 9 日 発行
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= 数理システム NUOPT メールマガジン http://www.msi.co.jp/nuopt/ 2010 Vol.4 ( 2010 年 11 月 9 日 発行 ) -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= 数理システム NUOPT メールマガジンでは，数理計画法パッケージ NUOPT に関する様々な情報やご案内を提供していきます． ++++ [目次] ++++++++++++++++++++++++++++++++++++++++++++++++++++++ ■ <トピック> NUOPT V13 のリリースにあたって ■ <トピック> NUOPT V13 の新機能に関するお知らせ ■ <トピック> 数理システムユーザーコンファレンスのお知らせ ■ <トピック> 数理計画用語集 用語追加 ■ <トピック> 発表・出展の報告およびご案内 ■ <トピック> 数理計画問題の豆知識（第 3 回） ■ <セミナー> NUOPT セミナーのご案内 ■ < tips > SIMPLE よくある間違い（第 15 回） ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ ****************************************************************** ■ <トピック> NUOPT V13 のリリースにあたって ****************************************************************** 計算機の容量が増大したのはパッケージ製品の作り手としては大きな追い 風．10 年前ならばコストがかかりすぎて導入できなかった手法を今なら 具体的に検討することができるのです． ただ，ユーザ側も相応にタフになってきて，以前では考えられない規模の 問題の解を短かい時間で求めたりします．実務的なアプリケーションの受 託開発を受け負う我々は，ユーザーとして，日々 NUOPT を「いじめる」側 に回ってもいます． このたび 12 月 1 日にリリースする新バージョン，V13 もそのような「せ めぎあい」の中から生まれました．ベンダー/ユーザーの二つの顔を持ち， 新しいアイディアやニーズをアルゴリズム開発と実際の応用の両面から導 いて反映させているというのは，NUOPT の一つの特色ではないかと考えて おります． モデリング言語 SIMPLE で行列やベクトルを直接扱いたいというのは，双 対問題などを簡便に記述したいというアカデミックな目的から発していま すが（お待たせしました!），格付け推移行列の扱いなど，実務的な問題に も貢献しそうです． MIP 高速化の取り組みも継続し，V12 に比べてさらに高速化しました． MKL などで実現されている高速な BLAS の実装が利用できる，というのは マルチコアな環境への対処の第一歩． 好評頂いている例題集も行列やベクトルの記述を含めて増補し，オンライン で引けるようにしています． 新機能の詳細は次の記事をご覧くださいませ． 新バージョンが皆さまのご期待に添えることを願ってやみません． （田辺 隆人） ****************************************************************** ■ <トピック> NUOPT V13 の新機能に関するお知らせ ****************************************************************** NUOPT は 12 月に 13 回目のリリースを迎えます． NUOPT V13 では，以下のような新機能を予定しています． ■ Matrix/Vector クラスの導入 モデリング言語 SIMPLE のクラスとして行列・ベクトルを直接記述するた めの Matrix/Vector クラスを導入します．半正定値計画問題が書きやすく なった他，線形計画問題の標準形とその双対形をコンパクトに記述，操作 することが可能になります． ■ SIMPLE の速度向上 モデリング言語 SIMPLE の一部実装の刷新により，大規模な数式の解釈の 速度が飛躍的に向上します． ■ マニュアルの充実 Excel 連係に関連するマニュアルを，「NUOPT/Excel 連係マニュアル」と して一本化し，解説を充実します． また，好評をいただいております NUOPT/SIMPLE チュートリアル内の「例 題集」部分を独立させ，新たに「NUOPT_SIMPLE_例題集」と致します．新た な数理計画問題の例題として「包絡分析法(DEA)モデル」，「巡回セールス マン問題」，「ロジスティック回帰モデル」，さらに NUOPT V13 より新た に導入される Vector/Matrix クラスを利用した「MAX-CUT 問題」，「二次 割当問題」を追加致します． ■ GUI ヘルプからのマニュアル参照 NUOPT V13 では，各マニュアルの内容を NUOPT GUI のヘルプコマンドから 参照する事が可能になります．用語をキーワード検索する事も可能です． ■ 外部 CLAPACK のリンク機能 ユーザー様がお持ちの CLAPACK を NUOPT ライブラリへリンクすることが できるようになります．これにより，大規模な線形計画問題において内点 法を用いる場合の求解速度が速くなる場合があります． 新機能のさらなる詳細については Web でも公開しています． 是非ご覧ください． http://www.msi.co.jp/nuopt/products/whatsnew/index.html （中野 雄介） ****************************************************************** ■ <トピック> 数理システムユーザーコンファレンスのお知らせ ****************************************************************** 「数理システムユーザーコンファレンス」が今年も開催されます． 弊社製品の先進的な導入事例について，多方面にわたる方々から講演が ございます． 今年の開催日は 11 月 19 日（金），場所は六本木アカデミーヒルズ（六 本木ヒルズ 49 階）となっております． なお，参加費用は無料ですが，事前のお申込みが必要となります． 詳細内容とお申込み方法については弊社 Web ページをご覧ください． http://www.msi.co.jp/userconf/2010/ 今年は NUOPT に関する講演が 4 本ございます． [ ソネット・メディア・ネットワークス株式会社 磯崎 直樹 氏 ] アドネットワーク広告におけるオプティマイズ戦略 ～ツールを活用した柔軟なアプローチのご紹介～ [ 独立行政法人水産総合研究センター遠洋水産研究所 庄野 宏 氏] 水産資源データ解析における NUOPT および VMStudio の利用 [ 株式会社ビデオリサーチ 田村 玄 氏 ] 独立した調査データの融合 ～汎用的データフュージョンシステムの開発～ [ 防衛大学校 宝崎 隆祐 氏 ] ゲーム理論で使う NUOPT ～施設警備問題に対する提案～ 上記 NUOPT 以外にも VMS，TMS，S-PLUS 等の講演がございます． プログラム詳細は以下をご覧ください． http://www.msi.co.jp/userconf/2010/ （佐藤 誠） ****************************************************************** ■ <トピック> 数理計画用語集 用語追加 ****************************************************************** 弊社数理計画部では，「数理計画用語集」を公開しています． http://www.msi.co.jp/nuopt/glossary/index.html 今回の新語，改修用語は以下の通りです． ＜新語＞ ・局所探索 ・厳密解法 ・数理計画問題，数理計画法 ・数理計画ソルバー ・制約充足問題 ＜改修用語＞ ・非線形計画問題 ・Excel ソルバー ご意見，ご要望等ございましたら，お気軽に用語集編集委員会 nuopt-glossary@ml.msi.co.jp までご連絡ください． （村山 昇） ****************************************************************** ■ <トピック> 発表・出展の報告およびご案内 ****************************************************************** 10 月 23 日（土）～ 24 日（日）に立命館大学にて，地理情報システム 学会の第 19 回研究発表大会が開催されました．NUOPT を始め弊社のツール の出展を行いました． お立ち寄り頂いた方々どうもありがとうございました． 11 月 4 日（木）に日本オペレーションズ・リサーチ学会中部支部ワーク ショップにて講演をさせて頂きました．最適化ソルバーの使いどころや， 他ソリューションとの融合について多くの方にご興味を持って頂けたこと 嬉しく思っています． http://www.orsj.or.jp/chubu/?p=879 11 月 5 日（金）に日本オペレーションズ・リサーチ学会 2010 年度第 1 回 OR セミナーで「半正定値計画問題の実務への応用」という題目で弊社 原田耕平が発表致しました． 半正定値計画問題は理論面での発展に対して，実務への普及は十分とは 言い難い状態であると感じており，少しでも普及のきっかけになればと 考えています． http://www.orsj.or.jp/activity/seminar.html 11 月 27 日（土）に大阪府立大学（中之島サテライト）にて日本オペレー ションズ・リサーチ学会産学研究者交流会が開催されます． この中で，「実務的な意思決定問題への数理計画法を用いたアプローチ」 という題目で弊社取締役田辺隆人が発表を致します． http://www.orsj.or.jp/kansai/seminar.html#20101127 （佐藤 誠） ****************************************************************** ■ <トピック> 数理計画問題の豆知識（第 3 回） ****************************************************************** 第 3 回を迎えました「数理計画問題の豆知識」，今回は「ネットワーク 問題」について紹介させていただきます． 現在「ネットワーク」に関する問題は様々な応用が期待されています． 電話やインターネットなどの通信事業ではもちろんのこと，最近ではスマー トグリッドと関連して電気の配給に対しても「ネットワーク」問題が応用 されてきています．これからさらに応用が広がるのではないかと実感して おり，トピックとしてとりあげることにいたしました． メイントピックとして，「ネットワーク問題を現実問題に対して適用し数 理計画問題として扱う」ことがなぜ有効なのか 3 点ほどあげたいと思い ます． まず 1 点目ですが「点と線からなるグラフ構造」というものが現実の問題 構造を表現するのに向いているという点があります． 有名な問題として「巡回セールスマン問題」，「ビークルルーティング」， 「配送問題」などがありますがどれも直観的でとても理解しやすいものと なっています． 例として「巡回セールスマン問題」について紹介しましょう． 巡回セールスマン問題とは，例えばアメリカ 50 州をすべて訪れることを 考えたときに「どの順番で各州を回れば，一番短い距離ですべての州を 訪れることができるか？」という問題です． これだけでも「新聞配達の巡回路」などに使えそうだといったことが想像 できます． 次に 2 点目として，図を利用して直観的に数式を理解できるという点が あります． 例として「配送問題」を考えましょう． 簡単なシチュエーションとして A,B という二つの工場から C という倉庫 へ製品を配送することを考えます． A から C への配送量を x(kg)，B から C への配送量を y(kg) として， 「C へは 180(kg) 以上配送しなければならない」という条件を数式で表す と x + y >= 180 となります． x A ----- C | | y | B 上記のグラフのように辺に配送量を割り当てることで，配送のシチュエー ションを直観で理解して数式を組み立てるということが可能となります． 最後の 3 点目としては「ネットワーク」を用いて定式化した問題に対して， 今日までに様々な解法が研究されており，また実際に利用されているとい う点です． 「巡回セールスマン問題」は一般には「NP 困難」な問題とされており， 非常に難しい問題とされてきました．そのことが数十年前まで実際に応用 されなかった理由でした． しかし「巡回セールスマン問題」に対する有効なアルゴリズムとして「ラ グランジュ緩和法」や「切除平面法」が以前よりも深く研究され，また コンピュータ全般の処理性能が格段に向上したこともあり今日では広く 利用されるようになりました．また，今現在においてもまだまだ進歩し 続けています． 「ネットワーク問題」について紹介してまいりましたがいかがでしたでしょ うか．ここで紹介した以外にも様々な応用があり，また我々の知らない活用 の仕方があるだろうと感じております． なにか自分の携わっている分野において「ネットワーク問題」として取り 扱えるのではないかと感じている方は遠慮なく nuopt-support@ml.msi.co.jp にご相談ください． 以上，御拝読ありがとうございました．次回もご期待ください． （家富 淳） ****************************************************************** ■ <セミナー> NUOPT セミナーのご案内 ****************************************************************** ---- [ NUOPT セミナー開催日程 ] ---------------------------------- ・ 11 月 25 日（木） 13:30 ～ 16:30 最適化入門セミナー ・ 12 月 1 日（水） 10:30 ～ 17:00 金融工学セミナー ・ 12 月 8 日（水） 13:30 ～ 17:00 スキルアップセミナー・基礎編 ・ 1 月 18 日（火） 13:30 ～ 16:30 最適化入門セミナー ・ 1 月 20 日（木） 13:30 ～ 16:30 生産スケジューリングセミナー 会場： （株）数理システム・セミナールーム （東京都新宿区新宿二丁目 3 番 10 号新宿御苑ビル 4 階） お申し込み先： （株）数理システム << NUOPT >> 担当 < nuopt-info@ml.msi.co.jp > セミナーの詳細： 下記 URL をご参照ください． http://www.msi.co.jp/nuopt/seminar/index.html ------------------------------------------------------------------ 各種セミナーともに，好評をいただいております．奮ってご参加ください ませ． なお，1 月 20 日の生産スケジューリングセミナーは，弊社開発の汎用 シミュレーションシステム S3（エスキューブ）との合同セミナーとなり ます． 本セミナーは従来のセミナー同様，生産スケジューリング問題を数理計画 問題として捉えることにより解決するアプローチをご紹介いたします． あわせまして，製造工程スケジューリングを例として，NUOPT で導出した 複数のスケジュール結果に対して，S3 の検証用シミュレーションモデル による評価を行う予定でございます． NUOPT と S3 の組み合わせにより，ロバスト（頑健）なスケジュール立案を 本セミナーでご提案いたします． 詳細につきましては， http://www.msi.co.jp/nuopt/seminar/scheduling.html にてご確認ください． （多田 明功） ****************************************************************** ■ < tips > SIMPLE よくある間違い（第 15 回） ****************************************************************** このコーナーでは，SIMPLE の記述に関してお客様が陥りやすい間違いを 紹介していきます． 今回は NUOPT に組み込みのメタヒューリスティクス WCSP を最大化問題に 対して適用する場合の注意点についてご紹介します． 以下のモデルとデータをご覧ください． -- [model.smp] ---------------------------------------------- options.method = "wcsp"; options.maxtim = 5; Set S(name = "S");Element i(set = S); Parameter p(name = "p",index = S); IntegerVariable x(name = "x",index = S,type=binary); Objective obj(name = "obj",type= maximize); obj = sum(p[i]*x[i],i); solve(); obj.val.print(); x.val.print(); ------------------------------------------------------------- -- [data.dat] ----------------------------------------------- p = [1] 1 [2] -1 [3] 5 [4] -3 [5] 6; ------------------------------------------------------------- 少し考えると，このモデルは p[i] のうち正の値を持つものの和を求める ことに対応している事がわかります． 手計算すると，目的関数 obj の最大値は obj = 1+5+6 = 12 となるはずです． しかし，試しに実行してみますと, -- [結果] --------------------------------------------------- obj=4 x[1]=1 x[2]=0 x[3]=0 x[4]=1 x[5]=1 ------------------------------------------------------------- 等となってしまいます．p[4] が負なのに x[4] が 1 となるのは期待して いた結果ではありません．なぜこんなことになってしまったのでしょうか． NUOPT の実行出力を良く見てみると -- [出力] --------------------------------------------------- TERMINATE_REASON All_constraints_satisfied ------------------------------------------------------------- という箇所があるかと思います．この All_contraints_satisfied という のがポイントです． 実は，WCSP においては，目的関数を最大化する場合には，そのままでは 「制約充足問題」として認識されてしまいますので制約式が全て満たされ てしまえば，そこで求解を終えてしまいます． このモデルの場合は制約式がありませんので，x[i] がどんな値であろう と，「制約を充足」しているため，WCSP 内でランダムに選ばれた初期値を 答えとして返してしまうのです． 「最大値」を求めたい場合には，十分大きな数（ここでは 10000 とします ）を用いて Objective の宣言を以下のように書き換えます． ------------------------------------------------------------- Objective obj(name="obj",type=maximize,target=10000); ------------------------------------------------------------- こうすると，WCSP アルゴリズムは目的関数が 10000 を超えるまで解の改 良を続けますので，結果として最大値を指向することになります． 実を言うと，type=maximize で target を無指定の場合には，自動的に target=0 と認識される仕組みになっているのです． いかがだったでしょうか．WCSP は特殊なアルゴリズムのため，やや癖は あるものの，厳密解法では求解困難な問題に対して精度の良い解を高速に 得られる可能性のある，非常に便利なアルゴリズムです． 必ずしも最適解でなくてもよいがそこそこの答えは欲しい，高速に求解し たい等というときには，是非 WCSP の使用をご検討ください． それでは次回もよろしくお願いします． (白川 達也) ================================================================== ※ このメールは，展示会・セミナー等で名刺交換をされた方，過去に NUOPT に関するお問い合わせを頂いたことのある方，および本メール マガジンの配信を希望された方にお送りしています． ※ バックナンバーはこちらから御覧頂けます． http://www.msi.co.jp/nuopt/mailmagazine/index.html ※ 本メールマガジンは等幅フォントでお読みになることを推奨します． ※ 今後このメールマガジンが不要な方は，誠にお手数ですが，「メール マガジン配信停止」という件名のメールを nuopt-ms@ml.msi.co.jp にお送りください． 発行：株式会社 数理システム << NUOPT >> 担当 東京都新宿区新宿二丁目 4 番 3 号 フォーシーズンビル 10 階 e-mail : nuopt-magazine@ml.msi.co.jp ==================================================================
<< 記事の内容に関するお知らせ >> 「数理システムユーザーコンファレンスのお知らせ」の記事内で ご紹介している詳細内容につきまして、アドレスの変更等のため 本ページからのリンクを修正いたしました。