バックナンバー ( 2014 Vol.5 ) 2014 年 9 月 18 日 発行
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= 数理システム 最適化メールマガジン http://www.msi.co.jp/nuopt/ 2014 Vol.5 ( 2014 年 9 月 18 日 発行 ) -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= 数理システム 最適化メールマガジンでは，数理計画法パッケージ 数理システム Numerical Optimizer をはじめとして，最適化に関する様々 な情報やご案内を提供していきます． ++++ [目次] ++++++++++++++++++++++++++++++++++++++++++++++++++++++ ■ <トピック> 数理システムユーザーコンファレンス 2014 のご案内 ■ <トピック> 金融国際情報技術展での講演のお知らせ ■ <トピック> Numerical Optimizer V17 に向けて ～ 行列を内部に持たない最適化 ～ ■ <セミナー> Numerical Optimizer セミナーのご案内 ■ <トピック> 数理計画問題の豆知識（第 17 回） ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ ****************************************************************** ■ <トピック> 数理システムユーザーコンファレンス 2014 のご案内 ****************************************************************** 11 月 21 日（金）六本木アカデミーヒルズ 49 にて毎年ご好評いただいて おります，数理システムユーザーコンファレンスを開催いたします． 今年の基調講演は，大阪ガス株式会社 情報通信部ビジネスアナリシスセン ター所長 河本薫様にご講演頂きます． また，今年も様々なジャンルから 20 を超える多数のユーザー様にご発表 を頂きます． 参加費用は無料でございます，皆様のご参加をお待ち申しております． << ユーザーコンファレンス Web ページ >> http://www.msi.co.jp/userconf/2014/ ※ お申込み開始は 10 月初旬を予定しております． ※ 近日中に講演プログラムを掲載予定です． （佐藤 誠） ****************************************************************** ■ <トピック> 金融国際情報技術展での講演のお知らせ ****************************************************************** 10 月 10 日(金)，FIT2014（金融国際情報技術展）にて，弊社数理計画部 部長 田辺が講演致します． 金融工学の普遍的かつ未解決なテーマとして，「リスク」の制御がござい ます． 本講演では， ・アセットのリスクを計測するシミュレーション ・信用リスクモデルを構成するマイニング ・リスク最小のポートフォリオを生成する最適化 等の事例に威力を発揮する，NTT データ数理システムのソフトウエア及び 技術をご紹介致します． ---- [ 講演概要 ] ------------------------------------------------ タイトル： 「リスク管理の PDCA ～最適化，マイニング，シミュレーションの基盤 技術によるアプローチ」 日程： 2014 年 10 月 10 日（金） 16:30 ～ 17:30 場所： 東京国際フォーラム・展示ホール（東京・有楽町） お申込み方法： 下記 URL にございます，セミナー申込フォームにてお申込みください． http://www.nikkin.co.jp/fit2014/seminar.html ------------------------------------------------------------------ なお，FIT2014 は金融機関・金融系列以外の一般企業の方は入場券が必要 になります．ご希望の方には無料招待状を送付致しますので， sales@ml.msi.co.jp までご連絡くださいませ． （亀川 佳美） ****************************************************************** ■ <トピック> Numerical Optimizer V17 に向けて ～ 行列を内部に持たない最適化 ～ ****************************************************************** 制約付きレコメンドなど，超大規模問題に対する数理計画法のニーズは高 まっているのですが，アルゴリズム実行に必要となる大規模な行列演算が 計算機資源上のボトルネックになっています． これをブレークスルーできるかもしれない技術が開発され，我々も Numerical Optimizer V17 でのリリースに向けて実装を始めました．制約 式行列をソルバー内部に持たず，制約式行列とベクトルの積のみをインタ フェースとして，アルゴリズムを実装するのです． 行列をソルバー内部に持たないので，大規模問題において所要する計算機 資源のオーダーを大幅に減らす効果が期待できます．ただ，行列解法とし て用いることができるのは反復法に限られることになりますので，KKT 条 件から現れる行列の悪条件の解消が必須要件となります．ここ 10 年あま り，偏微分方程式制約付きの最適化という分野に関連して理解が進み，新 しい手法が提案されています．我々の実装の今後にご期待ください． （田辺 隆人） ****************************************************************** ■ <セミナー> Numerical Optimizer セミナーのご案内 ****************************************************************** ---- [ Numerical Optimizer 定例セミナー開催日程 ] ---------------- ・ 9 月 24 日 (水) 13:30 ～ 17:00 スキルアップセミナー・実践編 ・ 10 月 8 日 (水) 13:30 ～ 16:30 最適化入門セミナー ・ 10 月 9 日 (木) 13:30 ～ 17:00 スキルアップセミナー・基礎編 ・ 10 月 10 日 (金) 13:30 ～ 17:00 スキルアップセミナー・実践編 ・ 11 月 5 日 (水) 13:30 ～ 17:00 スキルアップセミナー・基礎編 ・ 11 月 6 日 (木) 13:30 ～ 16:00 金融工学セミナー 会場 : (株) NTT データ数理システム セミナールーム （東京都新宿区信濃町 35 信濃町煉瓦館 1F） アクセスマップ http://www.msi.co.jp/msi/location.html ------------------------------------------------------------------ 最適化入門セミナーでは，様々なデモを通して，最適化・数理計画を利用 したソリューションのご紹介をしています． スキルアップセミナー・基礎編では，簡単な演習を通して Numerical Optimizer の使用方法を説明しています．Numerical Optimizer の導入を 計画中のお客様にもお勧めの内容となっております． セミナー終了後に，個別相談の時間も設けております．「最適化を利用し て，こんなことできたらいいなぁ」とお悩みの方は，是非セミナーにお越 しください． --- [ 大阪セミナーを開催いたします ] ----------------------------- 10 月 21 日から 24 日の 4 日間にわたって，大阪にてセミナーを開催い たします．最適化入門セミナーの他，Big Data やシミュレーションなど， 弊社の様々なソリューションをご紹介いたします． ご興味のお持ちの方は是非ご参加ください． ・ 10 月 24 日 (水) 10:00 ～ 12:00 最適化入門セミナー 会場: AP 梅田大阪（西梅田） （旧 ax-nets 大阪梅田） 大阪市北区曽根崎新地 2-3-21 axビル 4F アクセスマップ その他のセミナーについては http://www.msi.co.jp/event/ をご覧ください． ------------------------------------------------------------------ お申込み・詳細は下記をご覧ください． http://www.msi.co.jp/nuopt/seminar/index.html （中野 雄介） ****************************************************************** ■ <トピック> 数理計画問題の豆知識（第 17 回） ****************************************************************** 第 17 回目となる今回は，実行不可能な問題例が発生する場合に，問題の 緩和列を事前に定義することで対応する方法をご紹介します． << 1. 農場管理者から植え付けコンサルタントへ >> 今回は，農場管理者を主人公とする次の問題を取り上げます． ---- [ 問題 ] ---------------------------------------------------- エヌ氏は 3 つに区分けされた農場を所有している．彼の管理する農場では A ～ C の 3 種類の作物を用い，1 年を 4 期に分けて 4 毛作を実施して いる． A ～ C のそれぞれの作物を育てるには，1 期・1 農地にそれぞれ 3, 2, 1 だけの水が必要である． また A ～ C のそれぞれの作物は，1 期・1 農地で育てるごとにそれぞれ 5, 3, 1 の利益をもたらす． エヌ氏の用いている 4 毛作の方式では， 制約(1) 同一の農地では，どの種類の作物も，3 期以上連続して育てない というルールを守らないと土地が使い物にならなくなってしまう． また，エヌ氏の農場がある地域は取水制限が厳しく， 制約(2) どの期においても，取水量の和が 7 以下になる ように育てる作物を選ばなければならない． さらに，エヌ氏はノウハウの蓄積のため，また病害ですべての作物が壊滅 するのを防ぐため， 制約(3) どの作物も，4 期に一度はいずれかの農地で育てる 制約(4) どの期においても，2 種類以上の作物を育てる ことにしている． エヌ氏は，利益を最大化するように，12 期の植え付け計画を立てたい． ------------------------------------------------------------------ この問題には様々なパラメタが登場しますが，特に「4 期に一度」 と「2 種類以上」が，エヌ氏によって決められた制約であるということに注目し てください． エヌ氏は上記の問題を市販の MIP ソルバーを用いて解くことにしました． 上記問題の整数計画問題としての定式化は実行不可能（全ての制約を満た す解が一つも存在しない）になることもなく，エヌ氏は大きな利益を上げ ました． 彼はやがて，植え付け計画のコンサルタントとしてビジネスを始めます． エヌ氏は，同種の制約の下で利益を最大化したい農家を顧客として，ビジ ネスを始めることに成功しました．彼のモデルは取水制限の厳しい地域で は実行不可能となることもありましたが，個別に制約(3)のパラメタを「 5 期に一度」としたり，制約(4)のパラメタを「1 種類以上」としたりする ことで対処できました． しかし，エヌ氏の顧客が増えるごとに，手作業でのパラメタ調整の負担は 大きくなっていきます．このままでは，作業量が限界を迎えることは明白 です．エヌ氏はどのような手を打つべきでしょうか． << 2. 緩和問題列の事前定義 >> 数理計画問題の制約条件を（部分的に）緩めたものは，緩和問題と呼ばれ ます． 今回の問題の制約(3)や制約(4)を緩和すると，「ノウハウが溜まりにくい 解」や「病害のリスクの高い解」が得られ，喜ばしくない解であっても， 実際に実行できる結果が得られます．このような制約を緩めた緩和問題は， 元の問題が実行不可能の場合，大きな意味を持ちます． 手作業でのパラメタ調整に限界を感じたエヌ氏は，緩和問題の列を事前に 定義し，下記のフローを自動化しました． ---- [ 緩和フロー ] ---------------------------------------------- 植え付け問題 P を解く → 解けた場合，その最適解を計画とする ↓ 解けなかった場合 P の緩和問題(5 期に一度) を解く → 解けた場合，その最適解を計画と する ↓ 解けなかった場合 P の緩和問題(1 種類以上の作物) を解く → 解けた場合，その最適解を 計画とする ↓ 解けなかった場合 …（十分に長く定義） ------------------------------------------------------------------ このフローでは，パラメタを少しずつ変更し，問題を少しずつ，実行可能 になりやすいようにしています． エヌ氏はこのような緩和問題の列を事前に定義することで，手作業でパラ メタを書き換えることなく，多くの案件をこなせるようになりました． また，パラメタの変更を最小限に留めることで，エヌ氏の考えぬいた良い パラメタの性質を残すこともでき質の良い答えを得続けることができまし た． << 3. まとめ >> エヌ氏の例のように，問題なく稼働している最適化モデルに低頻度で実行 不可能な問題例が現れる場合は，事前に緩和問題列を定義しておく手法が 有用です． 実行不可能な問題に対処する方法として，WCSP（重み付き制約充足問題） による再定式化という手法があります．2 つの手法それぞれに得意分野が あります． 今回ご紹介した事前に緩和問題列を定義する手法は，制約の種類が少なく， 実行不可能の原因を人間が特定できる場合を得意とします． 今回ご紹介した緩和フローは，数理システム Numerical Optimizer V16 を 用いて，簡単に実現することができます．緩和問題列を使った現実問題の 解決にご関心をお持ちの方は，お気軽にご相談ください． （石原 響太） ================================================================== ※ このメールは，展示会・セミナー等で名刺交換をされた方，過去に 数理システム Numerical Optimizer に関するお問い合わせを頂いたこ とのある方，および本メールマガジンの配信を希望された方にお送り しています． ※ バックナンバーはこちらから御覧頂けます． http://www.msi.co.jp/nuopt/mailmagazine/index.html ※ 本メールマガジンは等幅フォントでお読みになることを推奨します． ※ 今後このメールマガジンが不要な方は，誠にお手数ですが，「メール マガジン配信停止」という件名のメールを nuopt-ms@ml.msi.co.jp にお送りください．なお，反映作業の都合上，数日間は旧情報にてメー ルが届く場合がございます．なにとぞご容赦ください． 発行：株式会社 NTT データ数理システム << 数理システム Numerical Optimizer >> 担当 東京都新宿区信濃町 35 番地 信濃町煉瓦館 1 階 tel : 03-3358-6681 e-mail : nuopt-info@ml.msi.co.jp ==================================================================