バックナンバー ( 2010 Vol.2 ) 2010 年 5 月 25 日 発行
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= 数理システム NUOPT メールマガジン http://www.msi.co.jp/nuopt/ 2010 Vol.2 ( 2010 年 5 月 25 日 発行 ) -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= 数理システム NUOPT メールマガジンでは，数理計画法パッケージ NUOPT に関する様々な情報やご案内を提供していきます． ++++ [目次] ++++++++++++++++++++++++++++++++++++++++++++++++++++++ ■ <トピック> NUOPT V12 における分枝限定法新機能のご紹介 ■ <トピック> VS2010 対応・最新パッチリリースのお知らせ ■ <トピック> 発表・出展の報告およびご案内 ■ <トピック> 数理計画用語集 用語追加 ＆ NUOPT FAQ 更新 ■ <トピック> 数理計画問題の豆知識（第 1 回） ■ <セミナー> NUOPT セミナーのご案内 ■ < tips > SIMPLE よくある間違い（第 13 回） ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ ****************************************************************** ■ <トピック> NUOPT V12 における分枝限定法新機能のご紹介 ****************************************************************** NUOPT V12 では様々な新機能を提供しておりますが，ここではその中から 分枝限定法の改善・新機能についてご紹介します． NUOPT V12 では，整数計画問題を解くアルゴリズム分枝限定法の計算速度 が，当方のベンチマーク試験において大幅に向上しました．この計算速度 向上は，「切除平面」及び「ヒューリスティクス」の改善によるものです． この二つについて，ユーザ側でチューニングを行うことも可能です． 「切除平面」は，緩和問題の解を元問題の解に近づけるのに有効です． NUOPT V12 は切除平面を用いて計算速度を改善していますが，ユーザで追 加する切除平面の数を調整することも可能です． 具体的には，モデル内に options.clevel=2; と記述することによって，追加する切除平面の数をさらに増やすことがで きます． もし扱っている問題の規模が小さく，なおかつ上界値と下界値のギャップ が大きくなかなか分枝限定法が収束しないようでしたら，このオプションを 使うのは有効です． 「ヒューリスティクス」は，厳密解ではなく，実行可能解（制約式を満た す解）が早く欲しい場合に有効です．NUOPT V12 ではデフォルトで数種類 のヒューリスティクスが入っておりますが，ユーザ側で調整することもで きます． 例えば，モデル内に options.feasPump=1; と記述することにより，ヒューリスティクス feasibility pump を有効に でき（デフォルトではオフ），より実行可能解を早く見つけ出すことが出 来ます． この feasibility pump は，当方の実験では特に 0-1 多品種流ネットワー クに帰着されるような構造を持つ問題において，良質な実行可能解を発見 する傾向が見られました． 上記オプションに関するより詳細は NUOPT V12 マニュアルをご参照ください． また，「切除平面」「ヒューリスティクス」等の用語について不明な点が ありましたら，以下の「数理計画用語集」をご参考ください． http://www.msi.co.jp/nuopt/glossary/index.html 今後もより多くの皆様がお持ちの問題に対応できるよう更なる性能改善・ 機能拡張に取り組んでまいります． （藤井 浩一） ****************************************************************** ■ <トピック> VS2010 対応・最新パッチリリースのお知らせ ****************************************************************** 3 月に NUOPT V12 がリリースされて 2 ヶ月が経ちましたが，最新の NUOPT をご利用いただいておりますでしょうか．ソルバーのパフォーマン スの向上だけでなく，最新の開発環境への対応，および Mac OS X への対 応等かねてからのユーザ様のご要望に対応させていただいております． さて，今回は Visual Studio 2010 への対応，およびリリース後に発見さ れた不具合を修正するパッチをリリースする運びとなりました． Visual Studio 2010 にて NUOPT V12 をご利用になられる方は，Visual Studio 2010 に対応済みのインストーラが必須となりますので， nuopt-info@ml.msi.co.jp まで NUOPT のシリアル番号とインストーラの送付を 希望する旨をご連絡ください．インストーラを送付させていただきます． また，NUOPT V12 の不具合を修正するパッチは，次の URL よりダウンロー ドが可能となっております． http://www.msi.co.jp/nuopt/support/nuopt_to_12_1_5_patch.html 今回リリースするパッチの主な修正点は，以下の 6 点になります． 1. 求解途中の下界値の表示が上界値を上まわるケースが確認されました． 数値的な丸め誤差が原因と判明し，修正されています． 2. 混合整数線形計画問題に対応する feasibility pump を実行した場合 (options.feasPump = 1 と設定した場合)に，大規模問題で NUOPT が 整数解を返さず， <<NUOPT 14>> integrality is violated. というエラーになるケースがあり，修正いたしました． 3. 混合整数計画問題において，目的関数の係数が計算によって零となる 変数が存在する場合，実行時エラーで終了するという不具合を解消し ました． 4. 非線形な半正定値計画問題を一回の実行で複数回連続して解くような 場合，計算が途中で終了してしまう不具合を解消しました． 5. WCSP の起動時に実行可能解発見までの時間を制約するパラメータ (wcspPhaseOneMaxtime) を設定した際の挙動が旧版と異なり，実行が 途中終了してしまう問題を解消しました． 6. Windows のユーザ名に特定の文字を使用している場合に，NUOPT GUI 上でモデルのビルドに失敗するという不具合があり，修正しました． 不具合・パッチについてのご不明な点につきましては弊社サポート （ nuopt-support@ml.msi.co.jp ）宛てにお問い合わせください． （岩永 二郎） ****************************************************************** ■ <トピック> 発表・出展の報告およびご案内 ****************************************************************** << 日本計算機統計学会・第 24 回大会 >> 5 月 14 ～ 15 日に日本計算機統計学会（JSCS）の第 24 回大会が統計数 理研究所で開催されました．出展及び以下のソフトウェア発表を行いまし た． ■ 汎用数理計画法パッケージ NUOPT －統計解析への応用－ 原田 耕平，佐藤 誠 ■ pLSI 手法 ＋ 多目的決定木によるレコメンド手法紹介 中園 美香，澤辺 剛 << 日本経営工学会 春季大会 >> 5 月 15 ～ 16 日に日本経営工学会春季大会が日本大学で開催され，展示を 行いました． << 経営情報学会 2010 年春季全国研究発表大会 >> 6 月 5 ～ 6 日に東京工業大学で開催される，経営情報学会 2010 年春季 全国研究発表大会で出展を行います． << 第 6 回日本・中国・韓国 構造および機械システムの最適化シンポジウム >> 6 月 22 ～ 25 日に京都ガーデンパレスホテルで開催される，第 6 回 日 本・中国・韓国 構造および機械システムの最適化シンポジウムで出展を行 います． 最適化が使われるシーンはますます広がっており，今後様々なジャンルの 学会への露出を考えています．どこかの会場で数理システムをお見かけに なることがありましたら是非ともお声掛けください． （佐藤 誠） ***************************************************************** ■ <トピック> 数理計画用語集 用語追加 ＆ NUOPT FAQ 更新 ****************************************************************** 弊社数理計画部では，「数理計画用語集」を公開しています． http://www.msi.co.jp/nuopt/glossary/index.html 今回の新語，改修用語は以下の通りです． ＜新語＞ ・RESIDUAL ・確率計画法 ・DEA ・判別分析 ・SCHOpt ・C 言語 ＜改修用語＞ ・S+NUOPT ・イールドカーブ推定問題 ご意見，ご要望等ございましたら，お気軽に用語集編集委員会 nuopt-glossary@ml.msi.co.jp までご連絡ください． また，「NUOPT FAQ」も適宜更新してます． http://www.msi.co.jp/nuopt/support/faq.html NUOPT でお困りの方も，そうでない方もご一読いただければ幸いです． （村山 昇） ****************************************************************** ■ <トピック> 数理計画問題の豆知識（第 1 回） ****************************************************************** 以前「数理計画法の誕生と発展」というテーマの記事を全 7 回に渡り紹介 してまいりましたが，この度は新しく「数理計画問題の豆知識」と題した 連載を始めることになりました． タイトルからして少し抽象的ですが，数理計画法を生業としている我々が よく出会う話として「実はこの金融のモデルはあの"農業"のモデルと同じ 問題だね！」といったことがあります．ようするにジャンルは全く異なる 対象に対して，数理計画問題としては同等のものが適用されているという ことです． 「ダイエット問題」「ナップサック問題」「p メディアン問題」「集合被 覆問題」．．．等様々な問題種別がありますが，このコーナーでは毎回一 つの問題を取り上げてその適用事例や，問題を解く際のコツ等をご紹介し ていこうと思います．たまに「双対問題」等話題が脱線しかかることもあ るかと思いますが，お付き合い頂ければと思います． 今回は第 1 回ということで，非常に簡単な豆知識を．たまに「この問題は LP だね！」と，ついつい言ってしまうことがあります． 勘違いしがちなのですが LP というのは "linear programming" の省略で 「線形計画法」を意味するものです． ですので「この問題は LP で解けるね」というのが正解なわけです．どう も "linear problem" と勘違いしがちです．数理計画法というのは問題と 手法をワンセットで考えるというのが歴史的にあったので余計にごちゃ混 ぜになってしまいます． さらに NUOPT に入っている WCSP というのは重み付き制約充足問題 "weighted constraint satisfaction problem" のことで，実は「問題」を 指します．ややこしいですね． ただ，日常会話で「この問題は LP だね！」といっても通じますので(!?) そこまで気にする必要はないのですが． 次回からはためになるトピックをピックアップする予定ですので，ご期待 ください． （佐藤 誠） ****************************************************************** ■ <セミナー> NUOPT セミナーのご案内 ****************************************************************** ---- [ NUOPT セミナー開催日程 ] ---------------------------------- ・ 6 月 3 日（木） 10:00 ～ 12:00 (大阪開催)最適化入門セミナー ・ 6 月 23 日（水） 13:30 ～ 17:00 スキルアップセミナー・基礎編 ・ 6 月 24 日（木） 13:30 ～ 16:30 生産スケジューリング・ 自動作成支援セミナー ・ 7 月 14 日（水） 13:30 ～ 16:30 最適化入門セミナー ・ 7 月 15 日（木） 13:30 ～ 17:00 スキルアップセミナー・実践編 ・ 8 月 25 日（水） 10:30 ～ 17:00 金融工学セミナー 会場： < 東京会場 > （株）数理システム・セミナールーム （東京都新宿区新宿二丁目 3 番 10 号新宿御苑ビル 4 階） < 大阪会場（6 月 3 日開催分） > アクスネッツ梅田 （大阪府大阪市北区曽根崎新地二丁目 3 番 21 号 ax ビル 4 階） お申し込み先： （株）数理システム << NUOPT >> 担当 < nuopt-info@ml.msi.co.jp > セミナーの詳細： 下記 URL をご参照ください． http://www.msi.co.jp/nuopt/seminar/index.html ------------------------------------------------------------------ 大阪での最適化入門セミナーを 6 月 3 日に開催致します．このセミナー は，東京で定期的に開催している最適化入門セミナーの内容をコンパクト にまとめたものとなります． 関西地方にて NUOPT に触れることが出来る貴重な機会となっております． ご興味をお持ちの方はぜひご参加ください． なお，5 月 31 日から 6 月 4 日にかけて弊社製品に関する様々なセミナー が大阪で開催されます．こちらにも奮ってご参加ください．なお，弊社主催 のセミナーの日程につきましては下記 URL をご参照ください． http://www.msi.co.jp/packages/seminar_list.html 最後に，東京で開催しておりますセミナーに関しまして適宜内容を充実さ せております．この度，NUOPT スケジューリングセミナーをリニューアル いたします． 具体的には， 『生産スケジューリング・自動作成支援セミナー ～プラント運転計画・工場での製造工程管理は NUOPT にお任せ！～』 という名称のセミナーとなります． セミナーの内容に関しましては，下記 URL をご覧ください． http://www.msi.co.jp/nuopt/seminar/seminar_scheduling.html ご期待くださいませ． （島田 直樹） ****************************************************************** ■ < tips > SIMPLE よくある間違い（第 13 回） ****************************************************************** 今回から白川が本稿の担当となります． これからどうぞよろしくお願いいたします． さて，今回は SIMPLE での漸化式の取り扱いに関してよくある間違いをご 紹介します． 5 の階乗 5! を求める場合を考えてみます． B[1] = 1, B[2] = 2, .. , B[5] = 5 として漸化式 C[1] = B[1] C[a+1] = B[a+1] * C[a] (a = 1, .. , 4) で C[a] を定義すれば，C[5] が 5! になりますね． これをそのまま SIMPLE で書いてみたのが以下のモデルです． ------------------------------------------------------------------ options.noDefaultSolve = 1; Set A; A = "1 .. 5"; Element a(set = A); Parameter B(index = A); B[a] = a; Parameter C(index = A); C[1] = B[1]; C[a+1] = B[a+1] * C[a],a+1<A; C.val.print(); ------------------------------------------------------------------ options.noDefaultSolve = 1 というのは，（上記のモデルは数理計画問題を 記述したものではないので）solve() で明示しない限り最適化計算を行な う必要がないということを NUOPT へ教えるためのおまじないです． これを実行した結果は以下の通りです． ------------------------------------------------------------------ C[1]=1 C[2]=2 C[3]=0 C[4]=0 C[5]=0 ------------------------------------------------------------------ C[3] 以降が 0 になってしまいました． これは添え字の自動展開機能が働いたことが原因です．添え字の展開順は 添え字集合を定義した順番通りとは限りません．C[a+1] の値を定義するに は C[a] に値が設定されていないといけないのですが，この関係が保たれ なかったのですね． これを解決するためには，以下のように A を OrderedSet で定義して， 意図的に C[a] の値が順々に設定されていくように書けば OK です． ------------------------------------------------------------------ options.noDefaultSolve = 1; OrderedSet A; A = "1 .. 5"; Element a(set = A); Parameter B(index = A); B[a] = a; Parameter C(index = A); for(a = A.first();a < A;a= A.next(a)){ if(a == A.first()){ C[a] = B[a]; }else{ C[a] = B[a] * C[A.prev(a)]; } } C.val.print(); ------------------------------------------------------------------ 出力結果は以下のように，ちゃんと C が階乗の値になっていますね． ------------------------------------------------------------------ C[1]=1 C[2]=2 C[3]=6 C[4]=24 C[5]=120 ------------------------------------------------------------------ いかがだったでしょうか．漸化式的に定義すべきものは，SIMPLE では逐次 的に定義する必要があるのでご注意ください． それでは次回以降もよろしくお付き合いくださいませ． (白川 達也) ================================================================== ※ このメールは，展示会・セミナー等で名刺交換をされた方，過去に 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 ==================================================================