バックナンバー ( 2011 Vol.5 ) 2011 年 9 月 28 日 発行
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= 数理システム NUOPT メールマガジン http://www.msi.co.jp/nuopt/ 2011 Vol.5 ( 2011 年 9 月 28 日 発行 ) -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= 数理システム NUOPT メールマガジンでは，数理計画法パッケージ NUOPT に関する様々な情報やご案内を提供していきます． ++++ [目次] ++++++++++++++++++++++++++++++++++++++++++++++++++++++ ■ <トピック> NUOPT V14 新機能のご紹介 ■ <トピック> ユーザーコンファレンスのお知らせ ■ <トピック> 数理計画用語集 用語追加 ■ <トピック> 発表・出展の報告 ■ <トピック> 数理計画問題の豆知識（第 7 回） ■ <セミナー> NUOPT セミナーのご案内 ■ < tips > SIMPLE 記述のテクニック（第 3 回） ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ ****************************************************************** ■ <トピック> NUOPT V14 新機能のご紹介 ****************************************************************** NUOPT は 11 月 18 日に第 14 回目のリリースを予定しております． 本メールマガジンでは，一足早く次期バージョンにて導入される新機能に 関してお伝えします． ■ 非線形計画問題に対する新アルゴリズム 信頼領域を利用した，逐次線形・二次計画法が新たに NUOPT に導入されま す．この方法は「目的関数の最小化」と「制約式の充足化」を交互に行う 事により，メリット関数を利用せずとも収束する事が特徴です． 上述の様に，二種類の目標（「目的関数の最小化」と「制約式の充足化」） を個別に考慮するアルゴリズムとしては，フィルター法が知られています． ですが，二目標の最適化を常に交互に実施する，という点がフィルター法 と異なります．また，フィルター法では過去の探索済点をフィルターとい う形で利用するのに対して，新アルゴリズムではフィルターを明示的には 利用しません． 新アルゴリズムは，制約が込み入った問題に対して NUOPT の既存の非線形 計画問題用アルゴリズムよりも，安定的に動作することが数値実験で確か められています． ■ 混合整数計画問題に対するマルチコア対応 昨今のコンピュータ環境の充実化により，今やマルチコアでないマシンの 方が珍しくなって来ております．NUOPT V14 では，混合整数計画問題を適 用対象とする分枝限定法について，マルチコア対応の機能拡張を行い，さ らなる高速化を実現しました． 我々のベンチマークセットの問題のいくつかでは，最適解導出までに 2 分 所要していた問題が 30 秒台になるなど，速度が 2～3 倍に向上するもの があることが観測されています． ■ GUI NUOPT の GUI が完全に新しくなります．とりわけ，得られた結果を視覚的 に集計・図示・レポートするための，豊富な機能が追加されます．さらに， 弊社のマイニングツール Visual Mining Studio や金融工学支援ツール FIOPT と共通のプラットフォーム上で動作するようになります． （原田 耕平） ****************************************************************** ■ <トピック> ユーザーコンファレンスのお知らせ ****************************************************************** 毎年開催しております数理システムユーザーコンファレンス，今年も六本 木ヒルズのアカデミーヒルズで 2011 年 11 月 18 日開催致します． 10 月上旬より事前申し込みの受け付けを Web で開始する予定ですので， 皆様奮ってご参加ください（参加費は無料）． 最適化関連では今年は 4 つの発表を予定しています． ◆「一般化状態空間モデルを用いた需要予測と広告ポートフォリオの 最適化」 -- 株式会社リクルート 吉永恵一様 ◆「異なる技能スタッフの 2 人組み当直シフト編成ツールの開発」 -- 大阪ガス株式会社 小林宏樹様 ◆「線形計画法を用いたエンジン適合試験の効率化の支援」 -- 株式会社小野測器 村瀬道夫様 ◆「熱源プラント運用へのNUOPTの適用 （省エネ、地球温暖化ガス削減へのチャレンジ）」 -- 株式会社山武 鈴木康央様 マイニングや統計関係の発表も非常に興味深いラインナップとなっていま す．講演タイトルやプログラムは以下をご覧ください． http://www.msi.co.jp/userconf/ 皆様のご参加をお待ちしております． （佐藤 誠） ****************************************************************** ■ <トピック> 数理計画用語集 用語追加 ****************************************************************** 弊社数理計画部では，「数理計画用語集」を公開しています． http://www.msi.co.jp/nuopt/glossary/index.html 今回の新語，改修用語は以下の通りです． ＜新語＞ ・スマートグリッド ・感度分析 ・Benders 分解 ＜改修用語＞ ・ロジスティクス ・ポートフォリオ最適化 ご意見，ご要望等ございましたら，お気軽に用語集編集委員会 nuopt-glossary@ml.msi.co.jp までご連絡ください． （村山 昇） ****************************************************************** ■ <トピック> 発表・出展の報告 ****************************************************************** 9 月 5 日～ 7 日に開催された統計関連学会連合大会にて，出展・ソフト ウェアデモンストレーション発表を致しました．発表では S+NUOPT や RNUOPT を中心にご紹介致しました．統計関連の学会ということもあり， S-PLUS や R のユーザーが多く非常に多くの関心を頂きました． 9 月 15 日・16 日に開催された日本オペレーションズ・リサーチ学会 秋 季研究発表会にて出展を致しました．春季は震災の影響により学会が中止 となってしまったこともあり，発表・参加者の数も多く非常に充実した大 会となりました． 9 月 24 日・25 日に開催されたスケジューリングシンポジウム 2011 にて 出展・ベンダーセッション発表を致しました． （佐藤 誠） ****************************************************************** ■ <トピック> 数理計画問題の豆知識（第 7 回） ****************************************************************** 今回は組合せ最適化問題の一つである，巡回セールスマン問題についてご 紹介します．本コーナーの第 3 回でもちょっと触れていますが，ここでは より掘り下げてご紹介いたします． 皆さんは買い物をする時に，どういう順番でお店を回るか悩んだことはな いですか？近い順のお店から行った方が良いのか，敢えて遠くから行って 近い店は帰り道に寄るか，悩ましいですね．実はこの悩み，巡回セールス マン問題というよく知られている数理計画問題としてとらえることができ ます． 巡回セールスマン問題は，セールスマンがある都市から出発して，全ての 都市を丁度 1 回ずつ通って最初の都市に戻ることが出来るルートのうち， 総移動距離が最小になるルートを求める問題です．都市をお店として見る と，先ほどの問題は巡回セールスマン問題としてとらえることができます． この問題は整数計画問題に分類されます．大規模な整数計画問題は，本コー ナーの第 3 回でも触れましたように，解く事が非常に困難です．巡回セー ルスマン問題も解く事が非常に困難なことで知られています．巡回セール スマン問題の研究の始まった 1950 年代には，42 都市ぐらいの規模でも挑 戦的な問題でした．マシンパワーが現在とは全く異なるとは言え，この規 模はちょっと驚きではないでしょうか． シンプルな問題構造と求解の困難さのギャップから，巡回セールスマン問 題は昔から多くの数理計画法の研究者を魅了してきました．例えば数理計 画法の始祖 Dantzig は Fulkerson ，Johnson と既に 1954 年に巡回セー ルスマン問題についての論文を出しております． また，巡回セールスマン問題の研究が数理計画法全体の発展に寄与した側 面もあります．例えば 1970 年代には Held と Karp が巡回セールスマン 問題の Lagrange 緩和を考えることによって，その下界値の計算を最小木 問題というこれまた有名な組み合わせ問題を解く事に帰着させる，という 仕事をしています．この仕事はその後 Lagrange 緩和を利用して大規模整 数計画問題を解く，Langrange 緩和法という汎用的な解法として発展し， 現在でも広く利用されています． 1980 年代になると，Crowder, Padberg らによって，切除平面法と分枝限 定法を組み合わせたアルゴリズムが巡回セールスマン問題に対して開発さ れ，多くの大規模巡回セールスマン問題が解かれました．この研究は整数 計画問題の汎用解法の研究も刺激しました．Crowder らは切除平面として サブツアー不等式等巡回セールスマン問題特有のものを利用しましたが， Balas らは lift-project カットや Gomory カットなど一般の整数計画問 題にも適用できる切除平面を利用し，整数計画問題の汎用解法の分枝カッ ト法へと発展させました．今ではこのアルゴリズムは NUOPT をはじめ多く の商用ソルバーに組み込まれています． ここまで巡回セールスマン問題の厳密解法について述べてきましたが，求 解困難な問題ですので当然ヒューリスティクス解法（発見的解法）も様々 に研究されています．その研究者の中に，あの C 言語の開発者として著名 な Brian Kernighan の名前もあります（ Lin-Kernighan heuristic ）． C 言語の開発者もひきつける魅力が巡回セールスマン問題にあったという ことでしょうか． いかがでしたでしょうか．素朴に見える巡回セールスマン問題ですが，そ の発展の歴史は数理計画法の発展の歴史と大きく重なるところがあることを 感じていただけたかと思います． そんな巡回セールスマン問題ですが，実務面への応用としては例えばスクー ルバスの巡回経路を決める問題，などがあります．また，巡回セールスマン 問題を発展させた Vehicle Routing Problem （ VRP ）という数理計画問題 ではより応用の幅が広がります．VRP については次回の豆知識でご紹介する 予定ですので，お楽しみに！！ (藤井 浩一) ****************************************************************** ■ <セミナー> NUOPT セミナーのご案内 ****************************************************************** ---- [ NUOPT セミナー開催日程 ] ---------------------------------- ・10 月 4 日 (火) 10:00 ～ 12:00 最適化入門セミナー（大阪開催） ・10 月 12 日 (水) 13:30 ～ 17:00 スキルアップセミナー・実践編 ・10 月 19 日 (水) 13:30 ～ 16:30 スマートグリッドソリューション セミナー << 満席のため受付終了 >> ・10 月 24 日 (月) 13:30 ～ 16:30 スマートグリッドソリューション セミナー ・10 月 26 日 (水) 13:30 ～ 16:30 最適化入門セミナー ・11 月 30 日 (水) 13:30 ～ 16:30 スマートグリッドソリューション セミナー 会場： [ 東京開催 ] （株）数理システム・セミナールーム （東京都新宿区新宿二丁目 3 番 10 号新宿御苑ビル 4 階） [ 大阪開催 ] AP梅田大阪（西梅田） （大阪市北区曽根崎新地 2-3-21 ax ビル 4 階） お申し込み先： （株）数理システム << NUOPT >> 担当 < nuopt-info@ml.msi.co.jp > セミナーの詳細： 下記 URL をご参照ください． http://www.msi.co.jp/nuopt/seminar/index.html ------------------------------------------------------------------ 数理システムでは，皆様のニーズにあわせて各種セミナーを開催しており ます． 9 月 14 日のスマートグリッドソリューションセミナーは大好評につき， ご案内即日に締切とさせていただきました． ご参加いただいた方々からも，興味深いご意見を数多くお寄せいただけま したこと，この場をお借りいたしまして感謝申し上げます． スマートグリッドソリューションセミナーは， 10 月 24 日 (月)・11 月 30 日 (水) の日時で現在もなお空きがありますので，奮ってご参加くださいませ． （多田 明功） ****************************************************************** ■ < tips > SIMPLE 記述のテクニック（第 3 回） ****************************************************************** このコーナーでは，SIMPLE のモデルファイルの記述に際して，知っておく と得をするテクニックや，マニュアルでは紹介していない便利な機能など について，日々 SIMPLE を使用し開発している立場から紹介させて頂けれ ばと思います． 今回は，Parameter などの値を C++ の配列にダンプして高速化する方法 をご紹介いたします． 以下の例をご覧ください． ------------------------------------------------------------------ Set I(name="I");Element i(set=I); I = "1 .. 1000000"; Parameter P(name="P", index=I); P[i] = 1/i; Parameter Q(name="Q"); Q = sum(P[i], i); Q.val.print(); Parameter R(name="R"); R = sum(P[i]*P[i], i); R.val.print(); ------------------------------------------------------------------ この例では，P[i] = 1/i で定義される P を全ての i = 1,2, .. ,1000000 について足し上げて Q に代入し，同様に P[i] の 2 乗和を R に代入して います． SIMPLE はなるべく直観的に記述できるよう設計されていますが，そのトレ ードオフとして，C++ のプリミティブな処理よりも実行速度が劣ります． 今回のように i の属する集合 I のサイズが非常に大きく，しかも P[i] を Q, R の代入で計 2 回使用する場合には，一旦，軽い C++ の配列（ポ インタ）へデータを移行してしまうと，重たい処理が 1 回で済みます． SIMPLE での記述と比べてやや煩雑にはなりますが，やり方は簡単です．論 より証拠，実際の例で確認して頂きましょう． ------------------------------------------------------------------ Set I(name="I");Element i(set=I); I = "1 .. 1000000"; Parameter P(name="P", index=I); P[i] = 1/i; Parameter Q(name="Q"); Parameter R(name="R"); int len = 1000000; // 添字集合のサイズ int *ind = 0; // 添字を指すポインタ double *val = 0; // 値を指すポインタ P.val.dump(len, ind, val); // P の内容を dump // Q と R の値を計算． double q_val = 0; double r_val = 0; for(int j=0; j<len; j++){ q_val += val[j]; r_val += val[j]*val[j]; } Q = q_val; Q.val.print(); R = r_val; R.val.print(); // メモリの解放（必ず必要です） delete ind; delete val; ------------------------------------------------------------------ 上記を見ていただければ分かると思いますが，データ長と添字，値を指す ポインタを用意して，.val.dump するだけです．C++ のプリミティブな配 列処理は非常に高速なため，P.val.dump で 1 回だけ重たい処理をした後 はほとんど一瞬で計算が済みます（私の環境では，改良前では 59.5 秒か かっていましたが，改良後は 21.3 秒で済みました．また，この 21.3 秒 のうちのほぼ全ては dump 処理に要しており，dump 後の処理はコンマ数秒 です）． いかがだったでしょうか．SIMPLE は直観的なインタフェースを備えている だけでなく，必要に応じて C++ の配列へデータをダンプすることも可能な 非常に柔軟なモデリング言語です．SIMPLE の実行速度が気になった場合に は，C++ へデータをダンプする方法も考慮頂ければと思います． なお，今回ご説明しましたダンプ手法については，「NUOPT_SIMPLE_外部接 続マニュアル」により詳しい説明がございますので，合わせてご参照くだ さい． それでは，次回以降もどうぞよろしくお願いいたします． (白川 達也) ================================================================== ※ このメールは，展示会・セミナー等で名刺交換をされた方，過去に NUOPT に関するお問い合わせを頂いたことのある方，および本メール マガジンの配信を希望された方にお送りしています． ※ バックナンバーはこちらから御覧頂けます． http://www.msi.co.jp/nuopt/mailmagazine/index.html ※ 本メールマガジンは等幅フォントでお読みになることを推奨します． ※ 今後このメールマガジンが不要な方は，誠にお手数ですが，「メール マガジン配信停止」という件名のメールを nuopt-ms@ml.msi.co.jp にお送りください． 発行：株式会社 数理システム << NUOPT >> 担当 東京都新宿区新宿二丁目 4 番 3 号 フォーシーズンビル 10 階 tel : 03-3358-6681 e-mail : nuopt-magazine@ml.msi.co.jp ==================================================================