バックナンバー ( 2009 Vol.1 ) 2009 年 2 月 18 日 発行
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= 数理システム NUOPT メールマガジン http://www.msi.co.jp/nuopt/ 2009 Vol.1 ( 2009 年 2 月 18 日 発行 ) -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= 数理システム NUOPT メールマガジンでは，数理計画法パッケージ NUOPT に関する様々な情報やご案内を提供していきます． ++++ [目次] +++++++++++++++++++++++++++++++++++++++++++++++++++++ ■ <トピック> NUOPT V11 のリリースにあたって ■ <トピック> NUOPT V11 の新機能に関するお知らせ ■ <トピック> 出展・発表案内（日本 OR 学会 2009 年春季研究発表会） ■ <トピック> 発表報告（自動制御連合講演会） ■ <トピック> 数理計画用語集 用語追加 ■ <トピック> 数理計画法の誕生と発展（その 4） ■ <セミナー> NUOPT 無料セミナーのご案内 ■ < tips > SIMPLE よくある間違い（第 8 回） +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ ***************************************************************** ■ <トピック> NUOPT V11 のリリースにあたって ***************************************************************** 日頃数理計画法パッケージ NUOPT に関心をお持ちいただき，まことにあり がとうございます．開発責任者の田辺でございます．この 3 月に V11 が リリースされる運びとなり，数理計画法の現場のニーズに応える新機能を 盛り込みました． まず，V11 ではアドオン機能として，解析的な表現が得られず，微係数が 取れない関数を目的関数とするような問題に関する最適化機能を組み込み ます．この手法は NUOPT の適用範囲を一気に広げる可能性を秘めており， このような関数を，通常の（非）線形制約と合せて用いることができる点 が我々の方法の一つの強みとなっております． また，内点法による非線形計画アルゴリズムのさらなる安定化を計り，ベン チマーク問題 CUTEr ([注]リンクを削除) から一部を抽出 した我々内生のテスト問題セットでは，20% 以上の問題についてパフォー マンスの改善を得ました．また，モデリング言語の新機能としてメタヒュー リスティクス解法 WCSP を用いる場合に，線形制約の充足している「数」を カウントする count 関数，「最大・最小」となっている線形制約のインデ クスを表現する argmin,argmax 関数が利用可能となります． この NUOPT の新バージョンが皆さまのお役に立つことを切に願っておりま す． （田辺 隆人） ****************************************************************** ■ <トピック> NUOPT V11 の新機能に関するお知らせ ****************************************************************** 早いもので，NUOPT もいよいよ 11 回目のリリースを迎える事になりまし た．3 月リリースの NUOPT V11 では，以下のような新機能を予定しており ます． ■ DFO による求解アルゴリズムの導入（アドオン機能） DFO（derivative free optimization）の手法を用いた求解アルゴリズムを 導入致します．このアルゴリズムはシミュレーション等によって求まるよ うな，数式では記述できないシステムに対して最適化計算を行うことが出 来るようになります． ■ 内点法/外点法機能増強 NUOPT の内点法/外点法アルゴリズムはメリット関数を用いた大域的収束の 保証，二階微係数の情報を活かした優れた局所的収束性を備えています． V11 では大規模な非線形計画問題で特に数値的な性質の悪い問題に対する 頑健性を増す方策を実装しました．ベンチマークの結果から見ても，安定 性・高速性は世界最高レベルです． ■ 制約充足アルゴリズム（WCSP）用の関数のさらなる追加 新たに argmax/argmin，count 関数を追加します．最大値をとる式番号を 取得したり，線形の制約式を充足している個数を取ったりするような定式 化困難な問題に対し，簡便なモデル記述と性能の大幅な向上を可能にしま す．今回導入された関数は設備計画・エネルギー問題・金融・広告配信等 様々なジャンルに対して威力を発揮できるものです． ■ 最新の開発環境への対応 Windows 版において最新の開発環境である Microsoft Visual Studio 2008 に対応します．Microsoft より無償で提供されている Express Edition に も対応しているため安価に最新のコンパイラの性能を享受することができ ます． 開発者一同，より高機能・高性能なソフトウェアを目指し，日々奮闘して おります． （岩永 二郎） ***************************************************************** ■ <トピック> 出展・発表案内（日本 OR 学会 2009 年春季研究発表会） ****************************************************************** 2008 年 11 月 14 日（金）に六本木ヒルズにて，数理システムユーザー コンファレンス 2008 を行いました．沢山の方々にご来場頂きました，誠 にありがとうございました． 2009 年 3 月 17 日(火)・18 日(水)に筑波大学（筑波キャンパス春日地区） にて行われます日本オペレーションズ・リサーチ学会 2009 年春季研究発 表会にて，弊社から発表・出展を致します．出展ブースではデモやムービー の配布を計画しておりますので，空き時間に是非ともお立ち寄りください． なお，春季研究発表会の詳細につきましては OR 学会の Web ページ http://www.orsj.or.jp/nc2009s/ をご覧ください． ここでは，弊社からの発表をご紹介します． ○ 半正定値計画問題に対する内点法における逐次正定値判定の利用 （*原田耕平） 半正定値計画問題を内点法で解く場合，ステップサイズの計算に要するコ ストを考慮しなければならない．この計算には一般化固有値問題の解を利 用する方法が一般的であるが，コレスキー分解を用いて逐次正定値判定を 行う方法を提案し，計算時間の比較を行った． ○ 数式表現によらない関数の制約付き最適化 （*島田直樹，田辺隆人，山下浩） 制約なしの問題に対する DFO の手法の一種を制約付きの問題に拡張し，実 装を行なった．数値実験の結果等を交えて今後の発展性についても述べる． ○ 地理情報システムへの数理計画エンジンの組込開発 - 施設配置問題を例として - （*多田明功，佐藤誠，藤井浩一） 数理計画問題の中には配送スケジューリング問題等，求解結果を地図上で 可視化すると有意義な問題が多々存在する．施設配置問題をモチーフとし て，最適化実行および地理情報システムへの結果表示をシームレスに行う ことができるシステムの開発を行った． （佐藤 誠） ****************************************************************** ■ <トピック> 発表報告（自動制御連合講演会） ****************************************************************** 2008 年 11 月 22 日（土）・ 23 日（日）に山形大学工学部で行われた 第 51 回自動制御連合講演会にて「数理計画から見た制御」という題目で， 私 原田耕平が発表いたしました． 特に「混合整数計画問題に特有の，定式化における注意事項」及び「制御 分野への半正定値計画問題への応用」の二点に関して，いくつかの話題を 提供させていただきました． （原田 耕平） ****************************************************************** ■ <トピック> 数理計画用語集 用語追加 ****************************************************************** 弊社数理計画部では，「数理計画用語集」を公開しています． http://www.msi.co.jp/nuopt/glossary/index.html 今回の追加用語には，数理計画部で日頃やり取りしているメールを分析し， 出現頻度の高い用語を採用しています．ホットな用語を常に取り込み， Up To Date な用語集を目指します！ 今回は以下の用語を追加しております． アセットマネジメント，キャリブレーション，レコメンド， ロジスティクス，ロバストポートフォリオ，ロバスト最適化， 信頼領域法，修正 KKT 条件，改訂単体法，有効制約法， 直線探索法，非線形半正定値計画問題 ご興味がある用語がありましたら，是非ご一読いただければと思います． ご意見，ご要望等ございましたら，お気軽に用語集編集委員会 nuopt-glossary@ml.msi.co.jp までご連絡ください． （村山 昇） ****************************************************************** ■ <トピック> 数理計画法の誕生と発展（その 4） ****************************************************************** 今回は「新・線形計画法 内点法 VS 単体法」と題しまして，内点法の歴史 等をご紹介いたします. 線形計画問題に対するアルゴリズムである単体法は，1947 年に Dantzig によって発明されて以来，永らく実務的に最も効果的な解法としての地位を 確立していました． 時には，「線形計画問題に対する高速な新解法」なる方法が提案される事 もありました．しかし，理論的にはともかく，実際の問題に適用すれば単 体法の方が圧倒的に有用であるという状況が，40 年近く続いていました (*1)． ところが，1984 年に Karmarkar により，Karmarkar 法と呼ばれる新しい 解法が提案され，実務的にも単体法に匹敵する性能を持つ事が確認されま した．この Karmarkar 法は，後に内点法と呼ばれる一連の解法群の先駆け となるものでした(*2)． 内点法の有用性が明らかになるにつれ，数多くの研究者がこの分野に参入 し，内点法はこの後一気に飛躍を遂げる事になります．1990 年代に入ると 線形計画問題に対する内点法の研究はひとまず収束し，小島教授（東工大） の発案である主双対内点法が，最も効果的である事が明らかになってきま した． こうして，内点法は線形計画問題に対する実用的な解法としての地位を確 立しました． 一方の単体法は，内点法の研究の発展に伴い，しばらく守勢に回る事を余 儀なくされました．1980 年代後半に，当時最高の性能を誇るとされていた 単体法のプログラムに対して，それを上回る性能を，新しい内点法のプロ グラムがたたき出したのです． しかしながら，1990 年代後半に入り単体法サイドも徐々に巻き返しを図り ます．古くから提案されている数々の工夫を地道に反映させた結果，再び 単体法は内点法に拮抗する性能を得るに至ります． 現在の所，線形計画問題に対する解法としての両者は，甲乙付け難い存在 です．非常に大規模な問題を取り扱う際には内点法が有利ですが，整数計 画問題への適用を考えると単体法に分があります． 今日における線形計画問題に対するアルゴリズムの研究は，既にかなり収 束しつつある感は否めません．しかしながら，世界中の研究者が日々研究 に打ち込んでいます．将来，今の我々には思いもよらないアルゴリズムが 提案される日が来るかもしれません． 次回は「非線形計画法の確立 内点法と自動微分法」と題しまして，内点法 が非線形計画問題に適用されていく様をご紹介したいと思います． (*1) 例えば，1979 年に提案された Khachiyan の楕円体法などがあります． (*2) 1967 年に Dikin により提案されたアフィンスケーリング法が，内点 法の先駆けであるという意見もあります．但し，この方法は後年になるま であまり世間に認知されていませんでした． 参考文献： [1] 今野浩， カーマーカー特許とソフトウェア， 1995， 中公新書 [2] 今野浩， 役に立つ一次式， 2005， 日本評論社 [3] 小島政和 ・土屋隆・水野眞治・矢部博， 内点法， 2001， 朝倉書店 （原田 耕平） ****************************************************************** ■ <セミナー> NUOPT 無料セミナーのご案内 ****************************************************************** ---- [ NUOPT 無料セミナー 開催日程 ] ----------------------------- 以下，各セミナーの直近の日程のみ掲載いたします．各セミナーに関する その他の日程は，以下の URL にて御確認ください． http://www.msi.co.jp/nuopt/seminar_nittei.html ※ NUOPT 無料紹介セミナー ・ 3 月 3 日（火） 10:30 ～ 17:00 金融工学特集 ・ 4 月 21 日（火） 13:30 ～ 16:30 体感しながら NUOPT 入門 ・ 4 月 22 日（水） 13:30 ～ 17:30 スケジューリング特集 ※ NUOPT 無料スキルアップセミナー ・ 3 月 31 日（火） 10:30 ～ 17:00 実戦に向けての NUOPT 演習 会場：（株）数理システム・セミナールーム （東京都新宿区新宿二丁目 3 番 10 号新宿御苑ビル 4 階） お申し込み先： （株）数理システム << NUOPT >> 担当 < nuopt-info@ml.msi.co.jp > ------------------------------------------------------------------ NUOPT セミナーは上記の 4 種類を定期的に開催しております． なお，この 4 種類のセミナーは，適宜内容を更新しております．今回は， これらのセミナーで最近更新した内容の一部を紹介いたします． 「NUOPT 無料紹介セミナー～体感しながら NUOPT 入門」は，NUOPT とは何 か，数理計画とは何かに関しまして，具体例を通じて紹介しております． 本セミナーでは最近，NUOPT の導入事例に関する内容を増強いたしました． 具体的な導入事例（シフトスケジューリング案件・地理情報システムと NUOPT の融合案件等）を基に，開発の一連の流れを説明しております．個 別案件を既にお持ちの方々をはじめとしまして，NUOPT 導入を検討されて いる方々のよい判断材料となれば幸いです． 「NUOPT 無料紹介セミナー・スケジューリング特集」は，NUOPT を用いた スケジューリング問題の説明を，シフトスケジューリング・プロジェクト スケジューリング両者に関して行っております．従来，本セミナーではデ モを通じて，実務に使えるスケジューリング作成のノウハウを重点的にお 伝えしておりました．最近，セミナーに御参加いただいた方々の御要望に お応えしまして，スケジューリング問題の数理計画による定式化方法， NUOPT を用いた記述方法の紹介もあわせて行うよう変更いたしました．セ ミナーに御参加される皆様の NUOPT を用いたスケジューリング問題に対す る御理解の一助となれば幸いです． 「NUOPT 無料紹介セミナー・金融工学特集」は，数理計画法と金融工学の 接点に関して，実例に基づきながら具体的にかつ分りやすく紹介いたしま す．本セミナーでは最近，NUOPT をベースにした金融工学支援ツール FIOPT の紹介を追加しております．軽い紹介にとどめておりますが，どの ようなコンセプトの元で弊社が開発を進めているかを簡単にご説明いたし ます． （多田 明功） ****************************************************************** ■ < tips > SIMPLE よくある間違い（第 8 回） ****************************************************************** このコーナーでは，SIMPLE の記述に関してお客様が陥りやすい間違いを少 しずつですが紹介していきます．今回から本コーナーの担当者が変わりま した．よろしくお願いします． 今回は SIMPLE の関数 ifelse について，よくある間違いをご紹介します． 関数 ifelse は，区間によって定義が異なる関数を定義するためのもので す．とても便利な関数なのですが，この関数には意外な落とし穴がありま す．関数 ifelse を用いると，そのモデルは非線形計画問題になります． また，NUOPT マニュアルにもあるように「対象の関数は領域全体で連続か つ微分可能である必要」があります． 例えば，以下のような使い方は不適切です． ------------------------------------------------------------------ Variable x; Objective f(type=minimize); f=ifelse(x<=1,-2*x+2,3*x-3); 0<=x<=10; ------------------------------------------------------------------ この場合，ifelse で定義しようとしている関数は x=1 で微分可能となら ないので不適切です．このような「折れ線関数」は，以下のように記述す るのが適切です． ------------------------------------------------------------------ Variable x; Variable y; Variable z; IntegerVariable r(type=binary); Objective f(type=minimize); f=-2*y+3*z+2; x==y+z; 1*r<=y<=1; 0<=z<=9*r; ------------------------------------------------------------------ 上のモデルにおいて，r は x が 1 未満の値をとると 0，1 より大きい値を とると 1 となります．この r のおかげで x は「0 から 1 までの値」と 「1 以上の値」に分解できます．前者の値が y，後者の値が z です．これ によって折れ線関数が線形の式で記述できます．このように，ifelse の対 象外の関数については，r のような中間変数の導入によって表現できる場 合があります． いかがだったでしょうか．関数 ifelse は便利なのでついつい使ってしま いますが，使っている内突然のエラーに見舞われることもあります．この ような場合は，ifelse の対象としている関数が「領域全体で連続かつ微分 可能」であるかどうかをよく検証しましょう． 次回は関数 ifelse の「正しい」活用法についてご説明いたします．ご期 待ください． （藤井 浩一） ================================================================== ※ このメールは，展示会・セミナー等で名刺交換をされた方，過去に 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 ==================================================================