バックナンバー ( 2013 Vol.2 ) 2013 年 3 月 21 日 発行
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= 数理システム NUOPT メールマガジン http://www.msi.co.jp/nuopt/ 2013 Vol.2 ( 2013 年 3 月 21 日 発行 ) -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= 数理システム NUOPT メールマガジンでは，数理計画法パッケージ NUOPT に関する様々な情報やご案内を提供していきます． ++++ [目次] ++++++++++++++++++++++++++++++++++++++++++++++++++++++ ■ <トピック> OR 学会 データ解析コンペティション（殊勲賞受賞） ■ <トピック> pynuopt のご紹介 ■ <トピック> 出展のご報告 ■ <トピック> 数理計画用語集 用語追加 ■ <セミナー> NUOPT セミナーのご案内 ■ <トピック> 数理計画問題の豆知識（第 16 回） ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ ****************************************************************** ■ <トピック> OR 学会 データ解析コンペティション（殊勲賞受賞） ****************************************************************** 先日，2 月 23 日に平成 24 年度日本オペレーションズ・リサーチ学会， データ解析コンペティション課題設定部門の最終発表会がありました． 数理システムより 岩永 二郎 （データマイニング部） 鍋谷 昴一 （ビジネスインテリジェンス推進センタ） 梶原 悠 （データマイニング部） 五十嵐 健太（データマイニング部） の 4 名で参加し，最優秀チームに贈られる殊勲賞を受賞しました！ 今年のコンペの課題はリクルート社の住宅ポータルサイト SUUMO を題材 にユーザのページビュー／資料請求を予測するというものでした． 解析には決定木分析・ロジスティック回帰分析・アソシエーション分析を 用いたのですが，データの情報量を補う要の部分に NUOPT，すなわち数理 計画法を用いて精度向上を実現したことが審査員に新規性の点でも高く評 価されました． 需要予測や反応確率など，データ分析の結果を所与として活用されること の多い数理計画法ですが，マイニング・データ分析の根幹であるモデル作 りにも重要な役割を果たすことを実地に示すことができました． 詳しくは，3 月 25 日に NTTデータ豊洲センタービルにて開催される 「データ解析コンペティション成果報告会」で詳細をお話いたしますので， お時間がありましたら是非ともご参加ください． （田辺 隆人） ****************************************************************** ■ <トピック> pynuopt のご紹介 ****************************************************************** NUOPT V15 の新機能である Python 接続機能である pynuopt のご紹介をし ます． Python というプログラミング言語をご存知でしょうか？ Python を一言で説明するのは難しいのですが，フリーなオブジェクト指向 のインタープリタ言語です．インタープリタ言語であるため手軽に，そし て，サポートされている環境，ライブラリが充実しているため本格的なプ ログラムを作成することができるため人気のある言語です． 前置きが長くなってしまいましたが，NUOPT でモデルを作成する際の壁の 一つが - モデルの作成 - モデルのビルド - コンパイルエラーがあった場合に，それを修正して，再びビルド - ... というように，ビルドが成功するようなモデルを作成するところではない でしょうか． 私も，未だにこのコンパイルエラーに苦しめられることが多々あります． NUOPT のユーザ様は日頃プログラミングに慣れ親しんでおられる方ばかり ではなく，普段はプログラミングとは無縁という方も多数おられます． NUOPT をインタープリタ言語で使用できれば，普段プログラミングとは無 縁という方にも，よりお手軽に使用していただけるのではないかと考えて おります． そこで，pynuopt です．Python という使いやすいインタープリタ言語を ユーザインタフェースとすることで，データの生成部分を Python に， 最適化を NUOPT にというように役割を分担しながら，そしてシームレス に最適化を実行することができるようになります． # 同じコンセプトの製品として S-PLUS，R をインタフェースとする # S+NUOPT，RNUOPT というものもあります． ただ，pynuopt はまだまだ発展途上の機能です．より使いやすい機能とす るためには，まず，多くのユーザ様にご利用いただくことが必須であると 考えております． V15 をお使いの際は，是非 pynuopt もご利用いただき，ご意見，ご感想を いただければ幸いでございます． （新田 利博） ****************************************************************** ■ <トピック> 出展のご報告 ****************************************************************** 3 月 5 日～ 6 日に日本オペレーションズ・リサーチ学会 2013 年春季研 究発表会にて展示を致しました．展示ブースに多数ご来場いただき，誠に ありがとうございました．また 6 日には CS 進出ナンバー導出プログラム に関する発表を致しました．ご清聴誠にありがとうございました． 3 月 12 日 ～ 15 日に言語処理学会にて展示を致しました．展示ブース に多数ご来場いただき，誠にありがとうございました． （佐藤 誠） ****************************************************************** ■ <トピック> 数理計画用語集 用語追加 ****************************************************************** 弊社数理計画部では「数理計画用語集」を公開しています． http://www.msi.co.jp/nuopt/glossary/index.html 今回の新語は以下の通りです． ＜新語＞ ・最大カット問題 ・LU 分解 ＜改修用語＞ ・SIMPLE ご意見，ご要望等ございましたら，お気軽に用語集編集委員会 nuopt-glossary@ml.msi.co.jp までご連絡ください． （村山 昇） ****************************************************************** ■ <セミナー> NUOPT セミナーのご案内 ****************************************************************** ---- [ NUOPT セミナー開催日程 ] ---------------------------------- ・ 4 月 11 日 (木) 13:30 ～ 16:30 最適化入門セミナー ・ 4 月 17 日 (水) 13:30 ～ 17:30 NUOPT 金融工学セミナー ・ 5 月 28 日 (火) 13:30 ～ 16:30 最適化入門セミナー ・ 5 月 30 日 (木) 13:30 ～ 17:00 スキルアップセミナー・基礎編 ------------------------------------------------------------------ 会場： （株）数理システム・セミナールーム （東京都新宿区新宿二丁目 3 番 10 号新宿御苑ビル 4 階） アクセスマップ: http://www.msi.co.jp/msi/location.html お申し込み方法： 「（株）数理システム << NUOPT >> セミナー申込み」 上記のタイトルで以下のメールアドレスにメールをお願いします． nuopt-info@ml.msi.co.jp メールの内容としましては, ・参加者のお名前 ・ご所属 ・何日のセミナーに参加を希望されるか をお書きください. セミナーの詳細： 内容については下記 URL をご参照ください． http://www.msi.co.jp/nuopt/seminar/index.html また弊社開催の他のセミナーの詳細な日程については下記 URL をご参照 ください． http://www.msi.co.jp/packages/seminar_list.html （佐藤 誠） ****************************************************************** ■ <トピック> 数理計画問題の豆知識（第 16 回） ****************************************************************** このコーナーでは数理計画に関連する豆知識をご紹介していきます．第 16 回目となる今回は，最小カット・最大カット問題をテーマに紹介いたしま す． まず最小カット問題からとりあげたいと思います． 有向グラフを考え，各エッジに非負の容量があるとします．また始点ノー ド s 及び終点ノード t を指定します．このときカットとは，グラフのノー ドの分割のことです．ただし一方の分割には s が，もう一方の分割には t が含まれるようにします．カットの容量とは，ネットワークを分断してい るカットと交わっている辺の容量の合計になります． 最小カット問題とは，容量の総和が最小となるカットを見つける問題です． ちなみに，ここで各エッジの容量が「非負」というのはとても大事なポイン トです． さて，この最小カット問題ですが，一見各エッジの組み合わせを調べあげ なければいけないような，面倒な組み合わせ問題に見えます．しかし実は この問題は s を始点とし，t を終点とするグラフ上の最大フローを見つけ るという解きやすい問題と等価であることが知られています！これが有名 な「最大フロー最小カット定理」です．なお最小カット問題の応用として は，通信網の信頼性検証などがあります． ではエッジの容量が最大となる問題を考えるとどうなるでしょうか？実は これは「最大カット問題」と呼ばれ，最小カット問題のようには簡単に解 けないということが知られています． しかしながら最小カット問題に負けないくらい魅力的な理論があります． 最大カット問題に対しては，1990 年代に Goemans と Williamson によっ てその半正定値緩和問題が考えられています．この半正定値緩和問題自体 は緩和問題なので，まず最大カット問題の上界を与えることができます． 加えて，乱数を用いて緩和問題の解から実行可能解を生成することができ ます．驚くべきことに，この期待値が元問題の目的関数値の 0.87856 倍以 上になっていることが知られています． この問題を端緒として，半正定値緩和問題の組み合わせ最適化への応用が 広がりました．ちなみにこの「0.87856」という不思議な数字がどこから出 てくるかを知りたい方は，松井知己先生の書かれた [1] を是非お勧めしま す．平易に書かれており，専門家でない方も気軽に読めるのではないかと 思います． なおこの最大カット問題の実行可能解を得るためには，半正定値緩和問題を 解いて得られる対称行列を使って，それを分散共分散行列とした多次元正 規分布を発生させる必要があります． でも半正定値緩和問題の結果を乱数発生のプログラムに入力して計算する のが面倒．．．そんなふうにお悩みではないですか？弊社開発の RNUOPT では R 上で NUOPT を動作させることにより，最適化計算と統計機能を シームレスに使うことができます．是非使ってみて，RNUOPT の威力， Goemans と Williamson の結果の強力さを体感してください！ [1] 松井知己「半正定値計画を用いた最大カット問題の .878 近似解法」, オペレーションズ・リサーチ 経営の科学 vol.45 no.3 (2000) （藤井 浩一） ================================================================== ※ このメールは，展示会・セミナー等で名刺交換をされた方，過去に 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-info@ml.msi.co.jp ==================================================================