バックナンバー ( 2009 Vol.3 ) 2009 年 8 月 25 日 発行
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= 数理システム NUOPT メールマガジン http://www.msi.co.jp/nuopt/ 2009 Vol.3 ( 2009 年 8 月 25 日 発行 ) -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= 数理システム NUOPT メールマガジンでは，数理計画法パッケージ NUOPT に関する様々な情報やご案内を提供していきます． ++++ [目次] ++++++++++++++++++++++++++++++++++++++++++++++++++++++ ■ <セミナー> NUOPT セミナーのご案内 ■ <トピック> 最新パッチリリースのお知らせ ■ <トピック> 出展・発表案内（スケジューリング・シンポジウム 2009） ■ <トピック> 数理計画用語集 用語追加 ■ <トピック> 数理計画法の誕生と発展（その 6） ■ < tips > SIMPLE よくある間違い（第 10 回） ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ ****************************************************************** ■ <セミナー> NUOPT セミナーのご案内 ****************************************************************** ---- [ NUOPT セミナー 開催日程 ] --------------------------------- ・ 9 月 29 日（火） 10:30 ～ 17:00 金融工学セミナー ・ 9 月 30 日（水） 13:30 ～ 16:30 最適化入門セミナー ・10 月 1 日（木） 13:30 ～ 16:30 事例紹介セミナー ・10 月 15 日（木） 13:30 ～ 17:00 スキルアップセミナー・基礎編 ・10 月 28 日（水） 10:00 ～ 12:00 （大阪会場）最適化入門セミナー ・10 月 29 日（木） 13:30 ～ 17:00 スキルアップセミナー・実践編 ・11 月 27 日（金） 13:30 ～ 16:30 スケジューリングセミナー 会場： << 東京会場 >> （株）数理システム・セミナールーム （東京都新宿区新宿二丁目 3 番 10 号新宿御苑ビル 4 階） << 大阪会場（10 月 28 日開催分） >> アクスネッツ梅田 （大阪府大阪市北区曽根崎新地二丁目 3 番 21 号 ax ビル 4 階） お申し込み先： （株）数理システム << NUOPT >> 担当 < nuopt-info@ml.msi.co.jp > ------------------------------------------------------------------ ＜ 特別セミナー ＞ ・株式会社リクルート様 事例紹介セミナー ＜リコメンド特集＞ 最適化とデータマイニングが融合した事例について紹介致します． 特別講師： 株式会社リクルート 街の生活情報カンパニー 領域戦略部 石山 洸 様 共同発表者： 株式会社リクルート MIT United マーケティングプラットフォーム推進室 松本 健 様 ＜ 定例セミナー ＞ 2009 年 9 月より，セミナーの体系が新しくなります．従来のセミナーに 加えて新しく「NUOPT スキルアップセミナー・実践編」が加わりました． 以下各セミナーを簡単にご紹介します． ・最適化入門セミナー 従来の NUOPT 無料紹介セミナーを基調としています． ・NUOPT スキルアップセミナー・基礎編 従来の NUOPT 無料スキルアップセミナーの基礎部分を強化したものに なります． ・（新）NUOPT スキルアップセミナー・実践編 従来の NUOPT 無料スキルアップセミナーの応用編となっております． ・NUOPT スケジューリングセミナー 従来の NUOPT 無料紹介セミナー・スケジューリング特集を基調とし， 開催時間を変更致しました． ・NUOPT 金融工学セミナー 従来の NUOPT 無料紹介セミナー・金融工学特集を基調としています． セミナーの詳細につきましては下記 URL をご参照ください． http://www.msi.co.jp/nuopt/seminar/index.html また，セミナーのお申し込みは，nuopt-info@ml.msi.co.jp までご連絡ください． （佐藤 誠） ****************************************************************** ■ <トピック> 最新パッチリリースのお知らせ ****************************************************************** 3 月に NUOPT V11 がリリースされて 5 ヶ月が経ちましたが，最新の NUOPT をご利用いただいておりますでしょうか．ソルバーとしての新機能・ チューニングだけでなく，最新の開発環境への対応などかねてからのユー ザ様のご要望に対応させていただいております． さて，今回はリリース後に発見された不具合を修正するパッチをリリース する運びとなりました．主な修正点は，以下の 7 点です． 1. Windows 環境で Excel あるいは GUI を通じた実行時，大規模なデータ の読み込みあるいは式を展開する場合に速度が大幅に低下する不具合 2. 線形制約の係数行列の非零要素の分布が偏っている場合にまれにスタッ クオーバーフローを起こして停止する不具合 3. 内点法の局所的振舞いの修正による高速化 4. mknuopt.bat の実行時に，「VC++ のインストールに問題があります．」 というメッセージが出力され，コンパイルに失敗する場合がある 5. MIP に対する若干の高速化 6. SIMPLE モデル解釈上の不具合 7. 内点法・外点法の実装変更 なお，パッチについての詳細は以下の URL からご覧ください． http://www.msi.co.jp/nuopt/support/nuopt_to_11_1_9_patch.html 不具合・パッチについてのご不明な点につきましては弊社サポート （ nuopt-support@ml.msi.co.jp ）宛てにお問い合わせください． （新田 利博） ****************************************************************** ■ <トピック> 出展・発表案内（スケジューリング・シンポジウム 2009） ****************************************************************** 2009 年 9 月 17 日（木）～ 18 日（金）に岡山大学津島キャンパスにて， スケジューリング・シンポジウム 2009 が開催されます． 9 月 17 日には成蹊大学池上敦子先生によるオーガナイズドセッションに て，“「納得」を生み出すスケジューリングアルゴリズムとソフトウエア - 制約充足を超えて：実行可能領域の直観的把握”と題しまして，発表を いたします．発表内容は以下の通りです． 近年，数理モデル化と最適化ソルバの発展は目覚ましく，多くの問題が解 かれてきたが，実用的なシステムにはまだまだ発展の余地がある．我々は， “最適化・マイニング・視覚化”というキーワードを元に“実行可能領域 の広さ”を意識しながらシフト表を段階的に作成するという手法を提案す る． この手法の要はシフト表の評価方法にあり， ☆ どの順序でシフトを決定すれば実行可能領域を保つことができるのか ☆ 与えられたシフト表はバランスの良いものであるのか という 2 つの評価に重点をおく． 前者はこの方法論自体を可能にし，後者はシフト表作成者を支援すること で人間の直感とバランス感覚をシフト表作成に反映させるという狙いがあ る． なお，シンポジウムにおいて出展ブースを設けさせていただきますので， 興味のある方はどうぞお立ちよりください．弊社研究員が対応いたします． （岩永 二郎） ***************************************************************** ■ <トピック> 数理計画用語集 用語追加 ****************************************************************** 弊社数理計画部では，「数理計画用語集」を公開しています． http://www.msi.co.jp/nuopt/glossary/index.html 今回は，数理計画部で流行の以下の用語を追加しております． ・ランタイムライセンス ・モデリング言語 ・反復回数 ・実験計画法 ・端株処理 ・動的計画法 ご興味がある用語がありましたら，是非ご一読いただければと思います． ご意見，ご要望等ございましたら，お気軽に用語集編集委員会 nuopt-glossary@ml.msi.co.jp までご連絡ください． （村山 昇） ****************************************************************** ■ <トピック> 数理計画法の誕生と発展（その 6） ****************************************************************** 「非線形計画問題の表現技法 自動微分法を中心に」 非線形最適化のアルゴリズムは，目的関数や制約式を局所的に線形あるい は二次関数で近似するための情報，すなわち微係数を必要とします． 目的関数や制約式の次数が高々二次であるなら，微係数は定数の行列です． その行列をデータとして保持すれば，アルゴリズムは微係数の情報を自由 に取得できます．しかし非線形関数ではそうは行きません．ソルバーが変 数値を更新する度に微係数が変化するのですから． 前回までは逐次二次計画法，内点法という非線形最適化アルゴリズムの成 立と発展に触れましたが，今回はそれらの動作を支える，微係数の計算技 術について述べます． ユーザーに微係数を供給させる，というのは研究者相手ならばいざ知らず， まず現実的ではありません（私，NUOPT のテスト用に Hock&Schittkowski という非線形計画法の小規模問題集のうち 30 問程度の微係数を手計算し てコードにしたことがありますがもう繰り返したくない経験です）． 古くから知られているのは，微分を取りたい変数をわずか振らして，それ に対する関数値の変化分を観測する，有限差分と呼ばれる方法です．しか し，この方法は精度（「わずか」を小さく設定しすぎると 0 を 0 で割っ た答を微係数として返すことになる），速度（すべての変数について同じ 操作を繰り返す必要がある）ともに難のある方法です． そこで 80 - 90 年代に確立された自動微分という方法が注目されます．こ の手法は四則演算や初等関数など，要素的な演算の列として実現された， 非線形関数の計算手順をグラフ（計算グラフ）の形で表現し，計算グラフを 辿ることによって微係数を得る方法です．複雑な非線形関数も，中間変数を 用いた四則演算と初等関数の演算の列として表現できることに着眼してい ます．ユーザは手続き的に関数の計算を表現するだけ．有限差分のような 精度の問題も生じないという点で汎用ソフトに向く手法と言えます． 例えば NUOPT に接続している SIMPLE というモデリング言語はこの方法に 基いて微係数を計算することで，ユーザに余計な手間をかけることなく， 汎用性と安定性を確保しています．ただ，非線形最適化アルゴリズムが結 果を出せるかは，微係数を供給する手法に大きく依存してしまうというの も事実．微係数が有限差分法で計算されている場合には，アルゴリズムの 振舞いも不安定になりますし，自動微分にメモリを喰いすぎると（実は自 動微分は計算手順に比例したメモリを所要する，という欠点があります）， 小さい問題なはずなのになんだか重たい，ということになります．問題の 表現と微係数の計算手法は非線形最適化を成功させる重要なファクターと 言えるでしょう． 本質的に解析的に表現が不可能な非線形関数（例えばシミュレーションプ ログラムの応答，など）も数多く存在し，そのような関数を含む最適化技 法が DFO（Derivative Free Optimization）として生み出され，NUOPT V11 にもアドオンとして組み込まれました．その話はまた別の機会とします． 次回は，整数計画問題に関するブレークスルーであるメタヒューリスティ クスについてです． （田辺 隆人） ****************************************************************** ■ < tips > SIMPLE よくある間違い（第 10 回） ****************************************************************** このコーナーでは，SIMPLE の記述に関してお客様が陥りやすい間違いを紹 介していきます． 今回は，SIMPLE エラー 82 についてご説明します．皆さんは NUOPT を使 う中でこんなエラーメッセージに出会ったことはないでしょうか． <<SIMPLE 82>> x の添字が定義域外である "51" となりました. この SIMPLE エラー 82 は，変数などの添字が定義域外の場合出力されま す．具体例で見ていきましょう．今，以下のような集合 T と変数 x を用 意します． ------------------------------------------------------------------ Set T; Element t(set=T); T = "1 ... 50"; Variable x(index=t); ------------------------------------------------------------------ 上記変数に対して，以下のような制約式を書く場合があると思います．例 えば時系列の問題などでしょうか． ------------------------------------------------------------------ x[t + 1] == x[t] + 1; ------------------------------------------------------------------ こう書くと，最初に書いたエラーメッセージに見舞われます．上の制約式 が t に関して展開された時，t = 50 の場合に t + 1 = 51 となり，これ は x の添字の定義域（ 1 から 50 まで）に入っていないため，エラーと なります． 以下のように修正することによって，正常な動作をします． ------------------------------------------------------------------ x[t + 1] == x[t] + 1, t + 1 < T; ------------------------------------------------------------------ 上記修正によって 常に t + 1 は x の添字の定義域である T の要素とな るので，エラーに見舞われることはなくなります． モデルが複雑になるにつれ，変数と添字の関係が曖昧になり，SIMPLE エラー 82 に見舞われてしまうことがしばしばあります．このエラーに出会ったら， 落ち着いて添字が定義域におさまっているかどうかを確認しましょう． （藤井 浩一） ================================================================== ※ このメールは，展示会・セミナー等で名刺交換をされた方，過去に 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 ==================================================================