バックナンバー ( 2011 Vol.6 ) 2011 年 11 月 29 日 発行
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= 数理システム NUOPT メールマガジン http://www.msi.co.jp/nuopt/ 2011 Vol.6 ( 2011 年 11 月 29 日 発行 ) -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= 数理システム NUOPT メールマガジンでは，数理計画法パッケージ NUOPT に関する様々な情報やご案内を提供していきます． ++++ [目次] ++++++++++++++++++++++++++++++++++++++++++++++++++++++ ■ <トピック> NUOPT V14 のリリースにあたって ■ <トピック> 発表・出展・ユーザーコンファレンスの報告と案内 ■ <トピック> 数理計画問題の豆知識（第 8 回） ■ <セミナー> NUOPT セミナーのご案内 ■ < tips > SIMPLE 記述のテクニック（第 4 回） ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ ****************************************************************** ■ <トピック> NUOPT V14 のリリースにあたって ****************************************************************** エネルギーの有効活用が社会的な話題になったり，Web マーケティングが 我々の日常に浸透する中，「選択」と「配分」を行うツールとして数理計 画に対する期待が高まってきているのを感じます． NUOPT V14 では昨今の計算機環境や数理計画を用いたアプリケーションの 方向付けを念頭に置き，次の機能追加を行いました．ぜひお試しください． * マルチコア環境を利用した並列化 インテル社の Threading Building Blocks を用いて，コア数に応じて，混 合整数計画問題に対する分枝限定法の並列化が可能となりました．現代の 分枝限定法の実装は，probing など高度な前処理，ヒューリスティクス， 切除平面法を含めた関連技術のいわば「総力戦」であることから，コア数を 増やして並列化したとしても，線形なスピードアップをもたらすとは限り ません． しかし，最適解導出までに 278 秒所要していた工場の冷暖房設備運転計画 問題（#変数 14544，#バイナリ変数 8304，#制約 8304）が，4 コアの並列 化で 124 秒に高速化できるなど，具体的な成果を確認しました． * NLP の新手法の実装 SLP-SQP（逐次線形二次計画）法という新アルゴリズムが実装されました． ペナルティ関数を用いずに大域的収束性を保証する部分が内点法とは全く 異なります． もちろん大規模な問題にも対応，例えば双線形な制約を含む 15985 変数， 12696 制約の問題を 70 秒で解くことができます．同じ問題を 15 秒で解 く内点法には速度の点では及びませんが，KKT 条件の充足度合（精度）は 一般に内点法よりも良好で，特に出発する点の周囲の実行可能領域が狭い 問題など，内点法が苦手とする状況で威力を発揮することが確認されてい ます． * GUI の刷新 GUI の実装を刷新しました．VAP(Visual Analytics Platform) という， 弊社パッケージが共通のデータフォーマットを介して共存できるプラット フォームに移行しました．全体的な操作感や Excel 連係機能はほぼそのま ま．例えばデータマイニング(VMS)手法と直接 NUOPT を連携する処理の流 れをそのままビジュアルに表現することができます． * SIMPLE の機能拡張と高速化 これまで実装上の制約によって表現できなかった，定数に関する漸化式を 次のような構文で直接表現することができるようになりました．SIMPLE の定式解釈の実装も実際の使われ方に即して，特に定数値の評価部分がよ り効率化・高速化されています． --- [漸化式の記述例] --------------------------------------------- startRecurrenceRelation(); a[1] = 1; a[2] = 1; a[i+2] = a[i] + a[i+1], i+2 < I; // フィボナッチ数列 endRecurrenceRelation(); ------------------------------------------------------------------ （田辺 隆人） ****************************************************************** ■ <トピック> 出展・発表・ユーザーコンファレンスの報告と案内 ****************************************************************** 10 月 15 日・16 日に鹿児島大学で開催された地理情報システム学会第 20 回研究発表大会にて出展を致しました． 11 月 18 日に数理システムユーザーコンファレンス 2011 を開催致しまし た．今年度も沢山の方にご来場頂き，誠にありがとうございました． 12 月 6 日開催のリッキーマーケットソリューションズ株式会社主催の RISK Conference 2011 にて出展および以下の講演を致します． 「統計・シミュレーション・最適化・マイニングによるリスク管理高度化 手法（数理システム 田辺 隆人）」 NUOPT や金融工学ツール FIOPT，統計解析パッケージ S-PLUS を用いた， 金融向けソリューションの紹介を致します． （佐藤 誠） ****************************************************************** ■ <トピック> 数理計画問題の豆知識（第 8 回） ****************************************************************** 前回の本コーナの予告通り，今回は Vehicle Routing Problem (VRP) に ついてご紹介します． VRP は次のような問題であり，配車計画問題，配送計画問題，運搬経路問 題と呼ばれることもあります． 複数の運搬車（vehicle）がスタート地点（デポ:depot）から需要の ある地点（顧客:customer）の巡回を行い再びスタート地点へ戻る． この時，全ての需要を満たし，総経路コストを最小化することを考える 問題 前回の巡回セールスマン問題は問題の設定が比較的単純で明確であるにも 関わらず，求解が困難な点で多数の研究者の方々の研究対象となっていま した．一方，VRP は問題の設定が現実社会に沿ったものが多く，より複雑 であり，しかも実務的な応用範囲が広いところに特徴があります． そのため，求解が困難であることは当然のこと，VRP の定式化を行うこと 自体が非常に難しい問題であります． 例えば，VRP の現実社会に沿った制約を思いつくままに並べると，以下の ようなものがあります． - デポが単一/複数 - 中継地点がある/ない - 運搬車の種類が複数（積載量，運べるものの種類，燃費）ある/ない - 顧客によって運搬車の種類が決まっている/決まっていない - 顧客への到着時間，または到着時間帯が決まっている/決まっていない - 顧客上での作業がある/ない (*) 作業としては，積み込みのみ，積み降ろしのみ，両方など - 分割納入をしてよい/してはいけない - 運搬車の稼働時間，移動距離制約がある/ない - 1つの運搬車が巡回できる顧客の数に制限がある/ない いかがでしょうか．このように VRP の問題設定には多くのバリエーション があり，しかも，教科書によくある数理計画問題のような単純な問題（た だ，簡単に求解できるとは限らないですが）に比べ，より実務的な問題を 対象にしていることが分かっていただけると思います． 実際，VRP はロジスティクスの配送に関する意思決定問題の 1 つととらえ ることができ，ロジスティクスのその他の意思決定の土台となっているよ うです． また，解法も様々なものが提案されています．主なアプローチを列挙する だけでも次のようなものがあります． << 近似解法によるもの >> - セービング法 - ルート先・クラスター後法 - クラスター先・ルート後法 - メタヒューリスティクス（タブ・サーチ，GA，焼きなまし法） << 厳密解法を取り入れた解法 >> - 集合分割アプローチ - Lagrange 緩和を用いた方法 - 分枝限定法，切除平面法を用いた方法 - 動的計画を用いた方法 例えば，弊社のホームページにある事例紹介 http://www.msi.co.jp/nuopt/solution/gis/case_delivery.html では集合分割のアプローチにて取り組みました．集合分割のアプローチは， 1. 可能な巡回路を列挙する 2. 列挙した巡回路の中から，全ての顧客をちょうど 1 回ずつ訪問し， かつ総費用が最小になるように（複数の）巡回路を選択する という 2 段階で表すことができます．2 段階目が集合分割問題に相当し， 汎用ソルバーで解を求めることが可能です．そのため，本アプローチの重 要な部分は 1 段階目のどのようにして巡回路を列挙するのかという点に なります． 実は，巡回路に対する制約が多ければ多いほど列挙が容易に（列挙数が少 なく）なる場合があります．事例の問題では，全ての制約を守る巡回路を 全て列挙することができましたので，それを元に集合分割問題を解くこと で最終的な解を求めることができました． なお，問題によっては可能な巡回路を全て列挙できないほど多数になる場 合があります．その場合は，列生成法を使用し，重要であろう巡回路を列 挙しながら集合分割のアプローチを適用することができます． さて，今回の VRP についていかがでしたでしょうか． VRP 自体身近な問題ですが，その身近さ故に話題が多く，駆け足となって しまいました．本稿をご覧になられて少しでも VRP という問題にご興味を 持っていただければ幸いでございます． (新田 利博) ****************************************************************** ■ <セミナー> NUOPT セミナーのご案内 ****************************************************************** ---- [ NUOPT セミナー開催日程 ] ---------------------------------- ・11 月 30 日 (水) 13:30 ～ 16:30 スマートグリッドソリューション セミナー ・12 月 1 日 (木) 13:30 ～ 16:30 最適化入門セミナー ・12 月 7 日 (水) 13:30 ～ 17:30 NUOPT 金融工学セミナー ・ 1 月 18 日 (水) 13:30 ～ 16:30 生産スケジューリング・自動作成 支援セミナー ・ 1 月 26 日 (木) 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 月に開催した大阪セミナーでは多数の方にご参加頂きました．半年に 1 度大阪セミナーは開催しておりますので，大阪近郊の方はお見逃しなく． 大阪開催，次回は 6 月頃の開催を予定しています． （佐藤 誠） ****************************************************************** ■ < tips > SIMPLE 記述のテクニック（第 4 回） ****************************************************************** このコーナーでは，SIMPLE のモデルファイルの記述に際して，知っておく と得をするテクニックや，マニュアルでは紹介していない便利な機能など について，日々 SIMPLE を使用し開発している立場から紹介させて頂けれ ばと思います． 今回は，主に繰り返し処理中において，目的関数を取り換えるテクニック についてご紹介いたします． SIMPLE の仕様では，目的関数( Objective )に対する代入は 1 度限りと約 束されています．ですので，次のようなモデルはランタイムエラーとなり ます． --- [モデル 1] --------------------------------------------------- OrderedSet I(name="I"); I = "1 .. 10"; Element i(name="i", set=I); Variable x(name="x", index=I); x[i] >= i*i; Objective f(name="f", type=minimize); Element itr; for(itr = I.first(); itr < I; itr = I.next(itr)){ f = x[itr]; solve(); } ------------------------------------------------------------------ --- [モデル 1 の実行結果] ---------------------------------------- ... (略) ... <<SIMPLE 168>> 目的関数(Objective)に対する代入は一度のみ可能です. ------------------------------------------------------------------ しかしながら，問題によっては繰り返し求解が本質的なこともあり，求解 のたびに目的関数を取り換えなければならないかもしれません．そのよう な場合，すぐに思いつくのは，モデル自体を何回も起動させる方法です． たとえば，次の繰り返し処理をもたない小さなモデルを P の値を変えなが ら何度も起動すれば，[モデル 1]で求めようとしていた結果を得ることが できます． --- [モデル 2] --------------------------------------------------- Parameter P(name="P"); // i*i に対応するパラメータ Variable x(name="x"); x >= P; Objective f(name="f", type=minimize); f = x; solve(); ------------------------------------------------------------------ 今回ご紹介したいのは，1 つのモデルの中で目的関数を取り換えるテクニッ クです．カギとなるのは，目的関数の変数化と，制約式の削除/復元です． 制約式に対して， deleteCo( 制約式オブジェクト名 ); restoreCo( 制約式オブジェクト名 ); とすることで，動的に削除/復元ができます．これを踏まえて，以下のよう にモデルを書きなおしてみます． --- [モデル 3] --------------------------------------------------- OrderedSet I(name="I"); I = "1 .. 10"; Element i(set=I); Variable x(name="x", index=I); x[i] >= i*i; Variable Var_f(name="Var_f"); // 目的関数を表現する変数 Objective f(name="f", type=minimize); f = Var_f; // 目的関数の変数化 // 目的関数の取り換えを表現する制約 Constraint cons(name="cons", index=I); cons[i] = Var_f == x[i]; // 初期化（一旦目的関数の取り換えを表現する制約を全て削除） deleteCo(cons[i]); Element itr; for(itr = I.first(); itr < I; itr = I.next(itr)){ // cons[itr] だけ復元 restoreCo(cons[itr]); solve(); // cons[itr] を再削除 deleteCo(cons[itr]); } ------------------------------------------------------------------ 目的関数 f を変数 Var_f に肩代わりさせ，目的関数の取り換えを，制約 式の deleteCo/restoreCo によって表現しました．これにより，目的関数 への代入は，1 度切りで済んでいます． いかがだったでしょうか．目的関数の変数化は，やや複雑ではありますが， 理解してしまえば，応用の効く，便利な方法です． それでは，次回以降もどうぞよろしくお願いいたします． (白川 達也) ================================================================== ※ このメールは，展示会・セミナー等で名刺交換をされた方，過去に 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 ==================================================================