バックナンバー ( 2007 Vol.2 ) 2007 年 8 月 28 日 発行
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= 数理システム NUOPT メールマガジン http://www.msi.co.jp/nuopt/ 2007 Vol.2 ( 2007 年 8 月 28 日 発行 ) -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= 数理システム NUOPT メールマガジンでは，数理計画法パッケージ NUOPT に関する様々な情報やご案内を提供していきます． ++++ [目次] +++++++++++++++++++++++++++++++++++++++++++++++++++++ ■ <トピック> Windows Vista への対応状況 ■ <トピック> 出展案内（日本 OR 学会・2007 年秋季研究発表会） ■ <トピック> 研究集会等での講演報告 ■ < tips > SIMPLE よくある間違い（第 2 回） ■ < tips > 疎形式でデータを与える方法 ■ < tips > Expression を Variable に ■ <セミナー> NUOPT 無料セミナーの御案内 ■ <セミナー> NUOPT 無料紹介セミナーが新しくなりました +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ ****************************************************************** ■ <トピック> Windows Vista への対応状況 ****************************************************************** NUOPT の Windows Vista (下記では単に Vista とします)対応について説 明をさせていただきます． メールマガジン 2007 Vol.1 にて，Vista 対応の近況についてご報告しま した．ユーザの方には大変ご不便をおかけしておりましたが，このたび， Vista 対応版の NUOPT のリリースについてご報告いたします． 2007 年 9 月 18 日に Vista 対応の NUOPT Ver.9 のリリースを開始しま す．9 月 18 日以降に NUOPT Ver.9 をご購入の方には，この Vista 対応 版をお納めさせていただきます． 9 月 17 日以前に NUOPT Ver.9 をご購入いただいた方は，弊社 Web ペー ジからダウンロードできるよう準備をしております．具体的な方法は弊社 サポート( nuopt-support@ml.msi.co.jp ) 宛てにお問い合わせください． （新田 利博） ****************************************************************** ■ <トピック> 出展案内（日本 OR 学会・2007 年秋季研究発表会） ****************************************************************** 恒例の日本 OR 学会・2007 年秋期研究発表会において，弊社では企業展示 で NUOPT を出展いたします．このメールマガジンを購読されている方々の 中でも多くの方々が参加されるかと思います．休憩時間の合間に，是非と も弊社コーナーにお立ち寄りください． 日本 OR 学会・2007 年秋季研究発表会 （http://www.orsj.or.jp/activity/anmeet.htm） 日時：2007 年 9 月 27 日（木），28 日（金） 場所：政策研究大学院大学（六本木キャンパス） ※研究発表会への参加は有料です．詳細は上記 URL をご参照ください． （坂田 昌一） ****************************************************************** ■ <トピック> 研究集会等での講演報告 ****************************************************************** 7 月 7 日に日本 OR 学会「計算と最適化」研究部会(S@CO)の第 6 回研究 部会で以下の講演を行いました． 「実務における数理計画アルゴリズムとその実装」(田辺 隆人) 大規模数理計画問題解法の実装上のボトルネック，数理計画モデルのデザ インパターンとモデル化のコツ，モデリング支援ツールの実装，大規模組 合せ問題に関するモデル化と strongness，メタヒューリスティクスと下界 値導出方法など，数理計画法と実務の接点に現れる数理計画アルゴリズム について現状を述べ，また会場の方々から様々な示唆を頂きました． また，8 月 13 日～ 16 日にカナダの McMaster University で行われた Mathematical Programming Society 主催の International Conference on Continuous Optimization (ICCOPT II & MOPTA-07) における semi-plenary talkとして以下の招待講演を行いました． 「Primal-dual methods for NLP and NLSDP」 (山下 浩) 海外での講演なので NUOPT の若干の解説を初めに行い，我々の過去の研究 と最新の研究をまとめて解説しました．非線形の半正定値計画問題に対す る主双対内点法は，我々のアルゴリズムが世界でも初めてのものなので， インパクトがあったと思います．それから，外点法によるパラメトリック 最適化も興味を惹いたようです． （山下 浩） ****************************************************************** ■ < tips > SIMPLE よくある間違い（第 2 回） ****************************************************************** このコーナーでは，SIMPLE の記述に関して，お客様が陥りやすい間違いを 少しずつですが紹介していきます． さて，前回は等式，不等式制約の書き方の間違いを紹介しました．今回は， その他お客様が陥りやすい間違いを一気に紹介したいと思います． 下のモデルを御覧ください．モデルの内容は前回と同じ単純なものですが， このモデルの中には文法的な誤りが全部で四つあります．皆様お分かりで しょうか． ------------------------------------------------------------------ Variable x y; x + y == 10 x >= 0; y >= 0; Objective obj(type=minimize); obj = x + 2y; ------------------------------------------------------------------ まず，一つ目の誤りです．1 行目は変数 x と y の宣言を意図したもので すが，複数の変数を一文で宣言する場合は変数名の間に "," が必要です． (誤) Variable x y; -> (正) Variable x,y; この "," は，Variable や Parameter 等の宣言文で属性を 2 つ以上設定 する場合，例えば，下記のような場合にも必要です． (誤) Variable x(name="weight" index=i); -> (正) Variable x(name="weight",index=i); 二つ目の誤りですが，2 行目は文末に ";" がありません．基本中の基本で すが，SIMPLE に慣れている方でも，時々この記述ミスに引っかかり，頭を 抱える場合があります． (誤) x + y == 10 -> (正) x + y == 10; 次に，三つ目です．最終行（6 行目）は一見正しそうですが，SIMPLE では， 積の演算子 "*" を省略することはできません．従って 2 と y の積を表す ためには，"2*y" としなければなりません． (誤) obj = x + 2y; -> (正) obj = x + 2*y; さて，最後四つ目の間違いは何処でしょうか．この間違いは上記のモデル を眺めているだけでは，見つけにくいかもしれません． 実は 4 行目の ";" の後ろに全角のスペースが入っているのです．この全 角スペースは非常にくせ者です．文字通り見えない文字が入っているわけ ですから，慣れないと発見するのにとても苦労します． このような間違いにいち早く気付くことが出来るように，NUOPT 無料セミ ナーでは TeraPad というエディタを使っており，全角スペースが見えるよ うに設定してあります．ご希望の方には TeraPad の設定ファイルをお渡し することも可能です．弊社サポート( nuopt-support@ml.msi.co.jp ) 宛てに お問い合わせください． （村山 昇） ****************************************************************** ■ < tips > 疎形式でデータを与える方法 ****************************************************************** 多くの成分の値が 0 であるような定数 Parameter をデータとして与える 場合，値が 0 となるような成分はデータファイルに明示的に記述する必要 はありません． 例えば，次の行列 A 3 2 0 1 0 -1 0 1 4 は， dat 形式ファイルで次のように記述できます． A = [1,1] 3 [1,2] 2 [2,1] 1 [2,3] -1 [3,2] 1 [3,3] 4 ; これは，明示的に値を指定しない Parameter の値は 0 に設定されるとい う SIMPLE の性質を利用したテクニックで，特に大規模な問題で威力を発 揮します． （原田 耕平） ****************************************************************** ■ < tips > Expression を Variable に ****************************************************************** ------------------------------------------------------------------ Set V; Set C; Element j(set=V),i(set=C); Variable x(index=j); // 変数ベクトル(例えば長さ 3000) Parameter A(index=(i,j)); // 比較的大規模な行列(例えば 50×3000) Expression s(index=i); s[i] = sum(A[i,j]*x[j],j); // s は A と x の積に等価な Expression Objective f(type=minimize); f = sum(s[i]*s[i],i); sum(x[j],j) == 1; // コンポーネントの合計が 1 x[j] >= 0; options.method = "asqp"; // 二次計画法に有効な有効制約法を選択 solve(); ------------------------------------------------------------------ 上記は， x を非負でコンポーネントの合計が 1 の変数ベクトル(長さ 3000)，A を比較的大規模な横長行列(サイズ 50 × 3000)としたときのベ クトル Ax の 2 ノルムを最小化するモデルです．このモデルは文法的には 全く問題はありませんし x の長さが 100 程度の場合にはほぼノータイム で答が返されますが，x が 3000 程度の長さとなると簡素な記述にもかか わらず，現在の標準的な PC でも 1 ～ 2 分程度の応答時間と数百メガバ イトのメモリを所要してしまいます． ここで上記の s を Expression ではなく Variable と宣言し，s の定義を 制約に置き換える，すなわち Variable s(index=i); s[i] == sum(A[i,j]*x[j],j); とすると，応答時刻は 10 秒程度，所要メモリは 50 メガバイト強と改善 されます．元の記述のように Expression とすると，s が数理計画法アル ゴリズムに入力される前に消去されるのに対して，Variable では s の現 れる式の情報がそのまま数理計画法アルゴリズムに渡るのが直接の理由で す．アルゴリズムの適用前に余計な中間変数を消去する方が効率的な気も しますが，これは典型的な反例となっており，s を消去した形の式では， 目的関数のヘッセ行列がサイズ 3000 × 3000 の行列となってしまうこと から，問題の表現に所要するメモリが大きく，アルゴリズムの実行には大 きな負荷となってしまいます．この tips の適用例は金融ポートフォリオ 問題のファクターモデルや，漸化式的な表現が現れるモデルなど，様々な 箇所で現れます． 一般に中間変数を消去するのが有利かどうかはケース依存ですが，経験的 に Expression の多用(中間変数の消去) は，非線形な定式の次数を上げる 結果にもなるため，内点法などの反復的な数値解法を想定されている場合 には，あえて中間変数を残した記述が有利のようです． 大規模で効率上の問題が生じ得る場合，または非線形性の強い場合につい ては，本 tips の適用をご検討頂ければ幸いでございます． （田辺 隆人） ****************************************************************** ■ <セミナー> NUOPT 無料セミナーの御案内 ****************************************************************** 皆様に NUOPT を知っていただき，更に使いこなしていただくために，弊社 では，NUOPT 無料セミナーを開催しております．セミナーのコースは 2 種 類用意しております．それぞれのセミナーについて説明をいたします． ※ NUOPT 無料紹介セミナー ～ 体感しながら NUOPT 入門 （NUOPT の購入を検討中の方にお勧めです） http://www.msi.co.jp/nuopt/seminar.html NUOPT の導入を計画中のお客様に最適なセミナーです．NUOPT を業務に導 入したいが，本当に役に立つのか？ どんな事例で使われているのか？ そ もそも数理計画法なる手法は本当に役にたつのか？ 半日という短い時間ながら，弊社の NUOPT 開発担当者が，直接に皆様にお 話しさしあげます．本セミナーでは， NUOPT を適用したアプリケーション に実際に触れていただきながら，説明を致します．操作を体感していただ くことで，NUOPT の導入効果を少なからず体験できる筈です．セミナー終 了後の個別相談も歓迎です． 9 月 21 日（金） 13：30 ～ 16：30 10 月 18 日（木） 13：30 ～ 16：30 11 月 13 日（火） 13：30 ～ 16：30 12 月 12 日（水） 13：30 ～ 16：30 会場：（株）数理システム・セミナールーム （東京都新宿区新宿二丁目 3 番 10 号新宿御苑ビル 4 階） お申し込みは，（株）数理システム << NUOPT >> 担当 < nuopt-info@ml.msi.co.jp >まで ※ NUOPT 無料スキルアップセミナー ～ 実戦に向けての NUOPT 演習 （NUOPT の使い方をマスターしたい方にお勧めです） http://www.msi.co.jp/nuopt/skillupseminar.html NUOPT を購入された後に，使い方の基礎を素早く習得したいお客様に最適 なセミナーです．NUOPT は汎用的に様々な分野に適用できる有用かつ強力 なツールであると自負しておりますが，それがゆえに初めて使う場合に少 しばかり戸惑うことがあるかもしれません．でも御安心を．最初の一歩を 越えれば，あとは自然と使いこなしていけます．このセミナーでは，実際 に NUOPT を操作しながら NUOPT の基礎を習得していただけます．テスト 版 NUOPT をお使いのお客様の参加も歓迎します． 9 月 10 日（月） 10：30 ～ 17：00 10 月 10 日（水） 10：30 ～ 17：00 11 月 16 日（金） 10：30 ～ 17：00 12 月 13 日（木） 10：30 ～ 17：00 会場：（株）数理システム・セミナールーム （東京都新宿区新宿二丁目 3 番 10 号新宿御苑ビル 4 階） お申し込みは，（株）数理システム << NUOPT >> 担当 < nuopt-info@ml.msi.co.jp >まで （坂田 昌一） ****************************************************************** ■ <セミナー> NUOPT 無料紹介セミナーが新しくなりました ****************************************************************** 「NUOPT に実際に触れてみたい」という，かねてから頂いている参加者の 方々の要望にお応えする形で，8 月より無料紹介セミナーの内容を一新い たします．これまでは複数の「デモ」を紹介しておりましたが，参加者の 皆様は「見ているだけ」という形でした．今後は，NUOPT を用いて動作す るシステムをより身近に感じていただけるよう，「実際に触れて頂く」と いうことをセミナーの中に取り入れていきます． 本セミナーでは「完成品を操作して頂く」という形式になりますので，ス キルアップセミナーのように詳しい定式化・記述方法に関する説明・作成 方法等の説明はございません．しかしながら，本セミナーに来て頂いたお 客様には，「数理計画はどのような問題を解決できるのか」「実際にシス テムとして作成したときにどのようなものになるのか」を実際の操作を通 しイメージして頂くことができると考えています．なお，セミナーで取り 扱う予定のデモは弊社 Web ページ http://www.msi.co.jp/nuopt/seminar_sample.html で紹介しています．マシンは会場に準備しておりますのでお気軽にご参加 頂ければと思います． （佐藤 誠） ================================================================== ※ このメールは，展示会・セミナー等で名刺交換をされた方，過去に NUOPT に関するお問い合わせを頂いたことのある方，および本メール マガジンの配信を希望された方にお送りしています． ※ バックナンバーはこちらから御覧頂けます． http://www.msi.co.jp/nuopt/mailmagazine/index.html ※ 本メールマガジンは等幅フォントでお読みになることを推奨します． ※ 今後このメールマガジンが不要な方は，誠にお手数ですが，「メール マガジン配信停止」という件名のメールを nuopt-magazine@ml.msi.co.jp にお送りください． 発行：株式会社 数理システム << NUOPT >> 担当 東京都新宿区新宿二丁目 4 番 3 号 フォーシーズンビル 10 階 ==================================================================