バックナンバー ( 2009 Vol.4 ) 2009 年 11 月 5 日 発行
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= 数理システム NUOPT メールマガジン http://www.msi.co.jp/nuopt/ 2009 Vol.4 ( 2009 年 11 月 5 日 発行 ) -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= 数理システム NUOPT メールマガジンでは，数理計画法パッケージ NUOPT に関する様々な情報やご案内を提供していきます． ++++ [目次] ++++++++++++++++++++++++++++++++++++++++++++++++++++++ ■ <トピック> S+NUOPT V2 リリースのお知らせ ■ <トピック> 数理システムユーザーコンファレンスのお知らせ ■ <トピック> KSMAP 若手研究者交流会 参加報告 ■ <トピック> 出展・発表報告（スケジューリング・シンポジウム 2009） ■ <トピック> 数理計画用語集 用語追加 ■ <トピック> 数理計画法の誕生と発展（その 7） ■ <セミナー> NUOPT セミナーのご案内 ■ < tips > SIMPLE よくある間違い（第 11 回） ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ ****************************************************************** ■ <トピック> S+NUOPT V2 リリースのお知らせ ****************************************************************** 統計解析パッケージ S-PLUS に NUOPT を接続したアドオンパッケージ S+NUOPT がリニューアルされ，S+NUOPT V2 としてこのたび 11 月にリリー スされます．S-PLUS のインタプリタから NUOPT をお使いになれる簡便さ はそのままに，半正定値計画法（SDP）アルゴリズム，本号の「数理計画法 の誕生と発展」で紹介されているメタヒューリスティクスアルゴリズム WCSP を起動することができるようになります． 金融系の応用としては，ロバストポートフォリオ最適化やより高度な二次 モデルによる判別分析，ユーザーが入力した行列に最も近い正定値な相関 行列への変換，銘柄のグルーピング，端株処理，などが可能となります． これらは NUOPT Windows 版でこれまでも実行可能でしたが，S-PLUS のデー タをそのまま受け渡しできる環境で実行できるようになりました．これに より，さらに用途が広がるでしょう．パッケージには典型的なコード例や データセットも含まれています． 12 月 3 日（木）の金融工学セミナーは S+NUOPT 特集と銘打ってこのパッ ケージを用いたデモンストレーションを予定しています． 年度末まで，価格据置きで発売します．また，旧版の S+NUOPT ユーザーの 方には特別価格にてご提供いたします． 詳細は nuopt-info@mlmsi.co.jp までお問いあわせください． （田辺 隆人） ****************************************************************** ■ <トピック> 数理システムユーザーコンファレンスのお知らせ ****************************************************************** 恒例の弊社主催「数理システムユーザーコンファレンス」が今年も開催さ れます．弊社製品の先進的な導入事例について，多方面にわたる方々から 講演がございます． 今年の開催日は 11 月 20 日（金），場所は六本木アカデミーヒルズ（六 本木ヒルズ 49 階）となっております． なお，参加費用は無料ですが，事前のお申込みが必要となります． 詳細内容とお申込みについては弊社 Web ページ http://www.msi.co.jp/userconf/09/ をご覧になってください． 今年は NUOPT に関する講演が 4 本ございます． [ 財団法人 鉄道総合技術研究所 三和 雅史 氏 ] NUOPT を活用した鉄道線路保守計画の最適化システム [ 株式会社 ニュージェック 安野 貴人 氏] 土木の長期修繕費の平準化をめざした対策時期の割当て問題 [ 株式会社 リクルート 石山 洸 氏，松本 健 氏 ] Web レコメンデーションモデルのご紹介 ～データマイニングと最適化ソリューションの融合～ [ 千葉大学 貞広 斎子 氏，東京大学 貞広 幸雄 氏 ] 都市施設再配置支援システムの開発 ～公立小中学校の「準」最適案群導出～ 上記 NUOPT 以外にも VMS，TMS 等の講演がございます． また，展示ルームでは NUOPT のデモも行っております．NUOPT 紹介 CD （NUOPT 試用版も付属）の配布も予定しております． 是非ともお立ち寄りください． （佐藤 誠） ****************************************************************** ■ <トピック> KSMAP 若手研究者交流会 参加報告 ****************************************************************** 10 月 10 日(土) ～ 12 日(月)に行なわれた KSMAP 合宿 in 明日香村に弊 社より原田，藤井，岩永の 3 名が参加いたしました．KSMAP (若手による OR 横断研究)は日本オペレーションズ・リサーチ学会の研究部会の一つで， OR に関わる若手研究者の分野を超えた交流と育成を目的としています． 合宿イベントは昨年より企画，実施されており，様々な分野の先生からコ メントをいただける場として，また，優秀な発表をした学生を表彰するこ とでも好評です． 多分野の研究者が集まるため丁寧な発表が多く，知らない分野の人間が聞 いても，「なるほど」と思わせるような優しい配慮が印象的でした． ポスターセッションでは発表者と聴衆との距離がグッと縮まり，非常に濃 い議論が行われます．私自身も学生さんと有用なディスカッションをさせ ていただきました．セッションが１時間を過ぎたあたりから，ビール片手 に議論をする人が増え，夜遅くまで繰り広げられるこの時間は醍醐味の一 つでしょう． また，私(岩永)より「論理学的・代数学的な概念を基礎とした数理計画法 の可能性」と題しまして発表をさせていただきました．問題構造の分析を 行うために論理学の概念を導入するという内容で，いくつかの結果を紹介 いたしました．実務の最前線では現実問題を数理モデル化する時点で，“ 解ける問題”か“解けない問題”なのか，それとも“際どい問題”なのか を正確に判定する必要があります．そのためにも問題構造の特性を整理す る必要があり，このような研究をすすめております． 自称「若手」として来年の KSMAP 合宿を楽しみにすると共に今後の発展 を期待しております． （岩永 二郎） ***************************************************************** ■ <トピック> 出展・発表報告（スケジューリング・シンポジウム 2009） ****************************************************************** 2009 年 9 月 17 日(木) ～ 18 日(金)に岡山大学にて，スケジューリン グ・シンポジウム 2009 が開催されました．シンポジウム内で，弊社田辺 が“「納得」を生み出すスケジューリングアルゴリズムとソフトウエア - 制約充足を超えて：実行可能領域の直観的把握”と題しまして発表させて いただきました．なお，本発表に関して成蹊大学の池上敦子先生に多くの ご助言をいただきました．この場を借りてお礼申し上げます． 本発表では，シフトスケジューリング問題について得られた解(シフト表) に関して， ・シフトを恣意的に壊して再計算したときに「誰が誰に影響を与えるか」 ・得られた解の「バランス」はとれているか といった情報をマイニングによって抽出，および視覚化(重み付きのグラフ 化)するという試みをしまして，実行可能空間の把握や解の選択に役立てよ うという提案をさせていただきました．最適化にデータマイニングと視覚 化が絡んだということもあり，最近の研究傾向に一味加えた内容をお伝え できたのではないかと思っております． また，成蹊大学の池上先生のオーガナイズドセッションでは，全体的に“ 最適解”に固執することなく，如何に“現場で使ってもらえる解”を得る か，という実務よりの話が多いという印象を受けました．近いうちに研究 の成果が社会に役に立つようになるのでは・・・という期待を密かに胸に 抱き，研究を続けていきたいと思っております． 最後になりますが，弊社の出展ブースに数多くの皆様がお立ち寄りいただ きましたこと，ここに感謝申し上げます． （岩永 二郎） ****************************************************************** ■ <トピック> 数理計画用語集 用語追加 ****************************************************************** 弊社数理計画部では，「数理計画用語集」を公開しています． http://www.msi.co.jp/nuopt/glossary/index.html 早いもので，この「数理計画用語集」も公開から約 1 年 4 ヶ月が経ちま した．各用語の解説は執筆時点での執筆者の考えが反映されておりますが， 言葉というのは生き物，時が経てば語の捕らえ方も変わります．そこで， 今回は新語の追加のほかに既存用語の改修もしました．新語，改修用語は 以下の通りです． ＜新語＞ ・集合被覆問題 ・双対単体法 ・制約想定 ・勾配ベクトル ＜改修用語＞ ・巡回セールスマン問題 ・UNIX ・ロング／ショートモデル ご興味がある用語がありましたら，是非ご一読いただければと思います． ご意見，ご要望等ございましたら，お気軽に用語集編集委員会 nuopt-glossary@ml.msi.co.jp までご連絡ください． （村山 昇） ****************************************************************** ■ <トピック> 数理計画法の誕生と発展（その 7） ****************************************************************** 今回は「さらなる大規模問題への挑戦」と題しまして，離散最適化問題に おけるメタヒューリスティクス解法についてご紹介いたします． メタヒューリスティクス解法と対を成す厳密解法というのは，出てきた答 えが最も良い答えであるということが保証された解法のことを指します． コンピュータの性能やアルゴリズムの向上によって厳密解法でも解ける問 題の規模は飛躍的に増大してはいるものの，NP 困難に属する離散最適化問 題に対しては解くのが非常に困難なケースも多く存在します． それを打破するために生まれた手法の一つがメタヒューリスティクス解法 と言えるでしょう．この解法は算出した解に対して「それが最もよい解」 という保証を得ることは出来ません．しかし厳密性を捨てた分，厳密解法 よりも高速に探索することに長けています． 川柳でたとえると以下のような感じになります． ＜厳密解法＞ これこそが 本当に本当の 最適解 ＜メタヒューリスティクス解法＞ そのへんに 良い解あったり しないかな 脱線はこれくらいにいたしまして，メタヒューリスティクス解法には種類 がいくつかあり有名なものでは，遺伝的アルゴリズム・焼きなまし法・タ ブーサーチ等があります．数多くあるアルゴリズムの中で「どれが優れて いるか」という点で評価すると問題やデータに依存する非常に難しい問題 になります．突き詰めて「あらゆる問題に対する平均」という観点からす るとどれも変わらないという結論（ノーフリーランチ定理）に至ったりし てしまいます．現実的には実務で解かれる問題にはある種の性質があり， そこに強いアルゴリズムが優れていると言えなくもないと思います． 我々の NUOPT には茨木俊秀先生を中心とする「京都大学・問題解決エン ジンプロジェクト」により生み出されたアルゴリズム WCSP が搭載されて います．WCSP はタブーサーチを採用しており，実務家サイドで取り扱う問 題の多くに力を発揮しています． また厳密解法においても，ヒューリスティックな探索を導入しより高速に 最適解を出すということも近年では主流になってきております．NUOPT の 次期バージョン（ V12 ）でもヒューリスティック部分の大幅なパワーアッ プを計画中でありますので，ご期待ください． 最後に書籍を紹介いたします． 柳浦睦憲／茨木俊秀 著 「組合せ最適化 - メタ戦略を中心として - 」（朝倉書店） さて，本企画「数理計画法の誕生と発展」は今回で最終回となります．学 会等で多くの方からご声援を頂き，それを励みとして取り組んでおります． 今後も何か新しいトピックを考え皆様に楽しんで頂ければと考えておりま す． 長い間ご愛読頂き誠にありがとうございました． （佐藤 誠） ****************************************************************** ■ <セミナー> NUOPT セミナーのご案内 ****************************************************************** ---- [ NUOPT セミナー開催日程 ] ---------------------------------- ・11 月 25 日（水） 13:30 ～ 16:30 最適化入門セミナー ・11 月 27 日（金） 13:30 ～ 16:30 スケジューリングセミナー ・12 月 3 日 (木) 10:30 ～ 17:00 金融工学セミナー S+NUOPT 特集 ・12 月 9 日 (水) 13:30 ～ 17:00 スキルアップセミナー・基礎編 ・ 1 月 27 日 (水) 13:30 ～ 16:30 最適化入門セミナー ・ 1 月 28 日 (木) 13:30 ～ 17:00 スキルアップセミナー・実践編 会場： （株）数理システム・セミナールーム （東京都新宿区新宿二丁目 3 番 10 号新宿御苑ビル 4 階） お申し込み先： （株）数理システム << NUOPT >> 担当 < nuopt-info@ml.msi.co.jp > セミナーの詳細： 下記 URL をご参照ください． http://www.msi.co.jp/nuopt/seminar/index.html ------------------------------------------------------------------ 10 月より新しいセミナー企画が始まりました．今回はセミナー講師である 私，家富が「NUOPT スキルアップセミナー・基礎編」の内容について紹介 したいと思います． 本セミナーは以前「スキルアップセミナー」として開催していたセミナーを 「基礎編」と「実践編」に分けたもののうち，SIMPLE の書き方と基礎的な 定式化の部分についてコンパクトにまとめた内容となっております． NUOPT の使い勝手を知りたい方や数理計画法自体に馴染みのない方にとっ て，数理計画法と NUOPT を理解する「最短コース」であると自負しており ます． NUOPT のユーザー様はもちろんのこと，これから数理計画法という考え自 体を自社に導入しようとしている方や NUOPT 導入を検討している方も， ぜひ奮って御参加ください． よろしくお願いします． （家富 淳） ****************************************************************** ■ < tips > SIMPLE よくある間違い（第 11 回） ****************************************************************** このコーナーでは，SIMPLE の記述に関してお客様が陥りやすい間違いを紹 介していきます． 今回は，2 次元の添字が付けられた Parameter を for 文をつかって参照 したい！という時のよくある間違いをご紹介します． まず，以下のように集合を二つ用意します． ------------------------------------------------------------------ Set I = "1 ... 5"; Set J = "1 ... 10"; ------------------------------------------------------------------ さらに，2 次元の添字が付けられた Parameter を用意します． ------------------------------------------------------------------ Parameter a(name="a", index=(I,J)); ------------------------------------------------------------------ いま，集合 I および J が数列なので，for 文を回してパラメータ a を標 準出力してみます．例えば以下のように書いたとしましょう． ------------------------------------------------------------------ int n, m; for ( n = 1; n <= 5; n++){ for ( m = 1; m <= 10; m++){ simple_printf("%d\n" ,a[n,m]); } } ------------------------------------------------------------------ するとエラーになり，以下のようなエラーメッセージが表示されます． <<SIMPLE 67>> 参照オブジェクト "a" の添字付けに誤りがあります. 次元 2 の添字を付けるべきですが、次元 1 の添字が付けられています. 実は，2 次元の添字が付けられた Parameter を (int 型,int 型) で参照 することはできません．この場合，色々な解決法がありますが，今回は最 初の変数を Element 型にキャストしましょう． ------------------------------------------------------------------ int n, m; for ( n = 1; n <= 5; n++){ for ( m = 1; m <= 10; m++){ simple_printf("%d\n" ,a[Element(n),m]); } } ------------------------------------------------------------------ これでエラーは解消され，パラメータ a がばっちり出力されるはずです． 以前にもこの「SIMPLE よくある間違い」で言及しましたが， SIMPLE では， 多次元 Parameter の [] の中をカンマ "," で区切ったときの各要素につ いて，最初の 2 つの要素のどちらかに Element 型か Parameter 型の要素 がないと添字を正しく解釈できないのです．ですので，(int 型,int 型) だとエラーになり，Element にキャストするとうまくいったのです． 少々マニアックな修正の仕方でしたが，いかがだったでしょうか． SIMPLE の中で for 文を用いると，意外とこのように間違いにはまる場合がありま す．皆様も「こんな for 文の使い方をして困った！！」というようなこと があれば，どしどし弊社までご連絡ください． （藤井 浩一） ================================================================== ※ このメールは，展示会・セミナー等で名刺交換をされた方，過去に 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 ==================================================================