|
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
数理システム NUOPT メールマガジン http://www.msi.co.jp/nuopt/
2007 Vol.3 ( 2007 年 11 月 15 日 発行 )
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
数理システム NUOPT メールマガジンでは，数理計画法パッケージ NUOPT
に関する様々な情報やご案内を提供していきます．
++++ [目次] +++++++++++++++++++++++++++++++++++++++++++++++++++++
■ <トピック> NUOPT V10 ・ 2008 年初頭にリリース開始
■ <トピック> NUOPT V10 の新機能に関するお知らせ
■ <トピック> 数理システムユーザコンファレンス 2007 のご案内
■ <トピック> 学会への出展報告
■ <トピック> 研究集会等での講演報告
■ < tips > SIMPLE よくある間違い（第 3 回）
■ < tips > selection() の効能
■ <セミナー> NUOPT 無料セミナーの御案内
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
******************************************************************
■ <トピック> NUOPT V10 ・ 2008 年初頭にリリース開始
******************************************************************
NUOPT は発売から着実に改良を重ねて，来年 2008 年の初頭には遂にバー
ジョン 10（NUOPT V10）をリリースする運びとなりました．
NUOPT は数理計画問題の定番である線形計画問題を始めとして，非線形計
画問題等に対する解法の充実を図って参りました．さらに，近年では割当
問題やスケジューリング問題等に代表される計算困難な離散変数型の問題
に対し，近似解法ならではの圧倒的な高速処理，驚異的な安定性と求解精
度を提供するメタヒューリスティクスエンジンを搭載し，国産最適化ソル
バーとして独自の地位を築いております．
ところで，NUOPT に組み込まれているメタヒューリスティクスエンジン
WCSP/RCPSP は，日本 OR 学会・第一回近藤賞を受賞された茨木俊秀先生
（現・関西学院大学教授）を中心とする「京都大学・問題解決エンジンプ
ロジェクト」により生み出されたものでございます．NUOPT V10 では，こ
のメタヒューリスティクスエンジン WCSP を更にパワーアップし，皆様に
より快適にお使い頂けるように致します．
さらに，昨今の研究成果が著しい非線形 SDP（半正定値計画問題）アルゴ
リズムも新たに搭載し，最適化ツールの新境地を目指します．
なお，今回リリースされる「NUOPT V10」では，お客様のご利用形態にあわ
せて以下の 4 種類のモジュールをご用意致しました．
＜LP/IP Lite モジュール＞
LP/IP（線形計画問題，整数計画問題）のみに対応するシンプル ＆ エコ
ノミカルなパッケージです．
＜LP/IP モジュール＞
LP/IP に加えて，割り当て問題やスケジューリング問題に対応したメタ
ヒューリスティクスエンジンを搭載した，ビジネスソリューション向け
パッケージです．
＜NLP モジュール＞
LP/IP に加えて，NLP （非線形計画問題）にも対応します．さらに，今
回新たに SDP アルゴリズムも搭載致します．高度な科学技術計算および
最先端の金融工学の専門職の方々必携のパッケージです．
＜フルセット＞
上記 3 つのモジュールを全て含んだ，充実したパッケージです．
（坂田 昌一）
******************************************************************
■ <トピック> NUOPT V10 の新機能に関するお知らせ
******************************************************************
早いもので，NUOPT もいよいよ 10 回目のリリースを迎える事になりまし
た．次回リリースの NUOPT V10 では，以下のような新機能を予定しており
ます．
○ GUI 操作性の向上
GUI の操作性が向上します．メッセージウインドウと経過表示が一体化し，
モデルのエラー修正も容易になります．
○非線形 SDP アルゴリズムの導入
非線形の半正定値計画問題に対する内点法アルゴリズムをリリース致しま
す．線形の半正定値計画問題のみならず，目的関数や行列制約に，非線形
項が出現する半正定値計画問題をも取り扱う事が可能です．
○ WCSP の関数群追加
メタヒューリスティクスによる整数計画法エンジン WCSP に新たな関数群
が追加されます．例えば，最大値の最小化など通常の数理計画の定式化で
は中間変数を導入して記述する必要があるような場合，その措置のために
問題のサイズの増大と求解速度の低下を招くケースが見られました．
V10 では，メタヒューリスティクスエンジンにおいて微分不可能な定式を
近傍探索時にそのまま評価させることによって，問題の変形の手間を省き
かつ大幅なパフォーマンスの向上を実現します．
より高性能・高機能なソフトウェアを目指し，我々開発者一同はリリース
に向けて日々奮闘しております．
（原田 耕平）
******************************************************************
■ <トピック> 数理システムユーザコンファレンス 2007 のご案内
******************************************************************
恒例の弊社主催の「数理システムユーザコンファレンス」が今年も開催さ
れます．
今年の開催日は 11 月 22 日（木），場所は六本木アカデミーヒルズ（六
本木ヒルズ 49 階）となっております．なお，参加費用は無料ですが，事
前のお申込みが必要となります．
お申込み方法等の詳細につきましては，弊社 web ページ
http://www.msi.co.jp/userconf/07/
をご覧になってください．
また，今年は NUOPT に関しまして以下の 3 本の講演が行われます．
[東京ガス株式会社 盛野幸一氏]
最適化手法を用いたエネルギーシステム設計
- 事務所ビルにおける一次エネルギーおよび CO2 の最小化 -
[株式会社大広 杉浦登氏]
TV 番組における放送素材の最適化配分
[株式会社明電舎 星靖之氏]
分散電源系統の電熱最適設備計画システム（改定版）のご紹介
以上 3 つの NUOPT に関する事例以外にも，弊社製品の適用事例が多く発
表されます．
弊社の総合力を結集して，皆様に先進的なソリューションを訴求いたしま
すので，皆様お誘い合わせの上お越しください．
（坂田 昌一）
******************************************************************
■ <トピック> 学会への出展報告
******************************************************************
9 月 27 日〜 28 日に政策研究大学院大学で開催された， OR 学会 2007
年秋季研究発表会に出展いたしました．会場では出展のブースが奥まった
ところになり，皆様の目にとまりにくい状況でした．それにも関わらず多
数の方にお声をかけて頂き，ありがとうございました．弊社と関連のある
企業の方の発表も聞かせて頂き，大いに刺激を受けました．
9 月 29 日〜 30 日に京都大学で開催されたスケジューリング・シンポジ
ウム 2007 にも出展いたしました．OR 学会と連日で開催されたため，多く
の方が東京から急いで京都に移動されたようでした．来場者や懇親会の参
加者は例年に比べ非常に多く，大盛況でした．弊社の NUOPT は汎用数理
計画ソルバーですが，スケジューリング問題に特化したスケジューリング
プロという製品を販売しており，機会があれば今後学会等で発表していき
たいと思っております．
最後に私事ですが，高校時代の同級生と学会で再開し，しばし昔話に花を
咲かせたりもしました．
（佐藤 誠）
******************************************************************
■ <トピック> 研究集会等での講演報告
******************************************************************
10 月 25 日〜 26 日に長崎ブリックホールにて行われた第 19 回 RAMP
シンポジウムにて，以下の二件の講演を行いました．
1. 金融工学アプリケーションにおける数理計画法の実際（田辺 隆人）
2. 実務的なシフトスケジュール作成問題へのメタヒューリスティクスアル
ゴリズムの応用（新田 利博，嶋田 佳明，田辺 隆人）
1. は二次計画法を大規模線形計画法，混合整数二次計画法，半正定値計画
法など，金融工学分野にて現れる様々な数理計画法の種類とパフォーマン
スについて論じたものです．
2. は NUOPT 組み込みのメタヒューリスティクスエンジン WCSP を用いた
実務的なスケジューリング問題を解く受託プロジェクトの例を通じて，実
務において求められるスケジュール作成問題の定式化や特徴，NUOPT の性
能について議論しました．
いずれもフロアから活発なご意見やご質問が寄せられました．
（田辺 隆人）
******************************************************************
■ < tips > SIMPLE よくある間違い（第 3 回）
******************************************************************
このコーナーでは，SIMPLE の記述に関して，お客様が陥りやすい間違いを
少しずつですが紹介していきます．
前回までは変数が 2 つの非常にトリビアルなモデルを扱ってきました．
今回は SIMPLE によるモデリングの最も重要なポイントである集合，添え
字を用いたモデルを扱います．
下のモデルは，供給地として工場(Factory)，需要地として顧客(Customer)
を持ち，工場と顧客の各ペアの間の配送量 x を決定する典型的な配送問題
のモデルです．このモデルの中には文法的な誤りが全部で五つあります．
皆様お分かりでしょうか．
------------------------------------------------------------------
Set Factory; Element f(set=Factory);
Set Customer; Element c(set=Customer);
Variable x(index(f,c));
Parameter cost(index={f,c}), upper(index=f), lower(index=c);
Objective cost_total;
cost_total = sum(cost[f,c]*x[f,c],f,c); // 総輸送コスト
sum(x[f,c],c) <= upper(f); // 各工場から配送できる量には上限がある
sum(x[f,c],f) >= lower(c); // 各顧客へ配送する量には下限がある
x[f,c] >= 0;
------------------------------------------------------------------
まず，一つ目の誤りです．4 行目は添え字として f と c を持つ配送量 x
の宣言ですが，index の後ろに "=" が抜けています．
(誤) Variable x(index(f,c)); -> (正) Variable x(index=(f,c));
二つ目の誤りは，既にお気付きかと思いますが，6 行目のパラメータ cost
の宣言で添え字を指定する index= の後の括弧の種類です．正しくは波括
弧 "{}" ではなく丸括弧 "()" を用います．
(誤) cost(index={f,c}) -> (正) cost(index=(f,c))
三つ目の誤りは，9 行目の目的関数 cost_total の定義式にあります．こ
こでは，添え字 f と c について式 cost[f,c]*x[f,c] の和をとっていま
す．このように 2 つ以上の添え字について和をとる場合は，それらの添え
字を丸括弧 "()" で括る必要があります．
(誤) sum(cost[f,c]*x[f,c],f,c)
-> (正) sum(cost[f,c]*x[f,c],(f,c))
なお，11 行目の sum(x[f,c],c) のように添え字が 1 つだけである場合
は，丸括弧を付けても付けなくても構いません．上述の変数，定数宣言時
の index= の後の丸括弧についても同様のことが言えます．
最後に，四つ目，五つ目の誤りは，11 行目，12 行目の添え字付き定数
upper，lower の括弧の種類です．添え字付きの変数，定数を式に書く時は
丸括弧 "()" ではなく角括弧 "[]" を用います．
(誤) upper(f) -> (正) upper[f]
(誤) lower(c) -> (正) lower[c]
今回は，集合，添え字に関する誤りを紹介してきました．こうしてまとめ
てみると，集合，添え字を用いるようになって最初につまずくのは，今回
主に紹介した括弧の使い方だということがわかります．「集合，添え字は
慣れないと難しい」とよく言われますが，意外とこのような所が原因なの
かもしれません．
（村山 昇）
******************************************************************
■ < tips > selection() の効能
******************************************************************
集合 U の要素 i について，集合 S の要素 j を一つ割りあてる方法を決
定する問題の定式化は以下のような基本的な構造を持ちます．
------------------------------------------------------------------
Set U; Element i(set=U);
Set S; Element j(set=S);
IntegerVariable x(index=(i,j),type=binary); // 変数
sum(x[i,j],j) == 1; // .. (1)
------------------------------------------------------------------
この構造は，
・輸送箇所の選定問題（U を需要地の集合，S を供給地の集合とする，
今回の「SIMPLE よくある間違い」での例が同じ構造です）
・シフトスケジューリング問題（U をシフトのマス目の集合，S をシフ
トと定義する）
・営業マンのテリトリ決定問題（U を顧客，S を営業マンとする）
・n-Queen 問題（盤面の列（行）を U，駒のある場所を S とする）
などの様々な問題の基本的枠組みとして用いることができます．この基本
的枠組みに輸送箇所の選定問題であれば，例えば
sum(x[i,j],i) <= 5; // 各供給地がサポートできる需要地は高々 5 つ
のように問題の特性に依存した記述を加えて具体的な問題が構成されてい
るわけです．この種の問題に対し，NUOPT に組み込まれているメタヒュー
リスティクスエンジン WCSP を適用する場合に是非ご利用頂きたいのが，
上記 (1) の制約式を
selection(x[i,j],j); // (1) と等価
と置き換える方法です．この記法は意味を明確化する以外に，探索空間を
制約式が成立している箇所のみに限って，探索を高速化するという効果が
ございます．大規模な問題において効果は顕著で， U,S の集合がそれぞれ
200 の n-Queen 問題では次のような実験結果が得られています．
(1) のまま ・・・ 27.5 秒
selection 導入 ・・・ 4.2 秒
( 利用マシン: Pentium(R) D CPU 3.60 GHz 3.59 GHz,3.50 GB RAM)
selection() では残念ながら
sum(x[i,j],j) == 2;
のような記述は表現することはできません．しかし，要素 i について要素
j を割り当てないこともあり得るケース:
sum(x[i,j],j) <= 1;
は，「割り当てない」という状態を集合 S に追加することにより，
selection() で表現することができます．
（田辺 隆人）
******************************************************************
■ <セミナー> NUOPT 無料セミナーの御案内
******************************************************************
皆様に NUOPT を知っていただき，更に使いこなしていただくために，弊社
では，NUOPT 無料セミナーを開催しております．セミナーのコースは 2 種
類用意しております．それぞれのセミナーについて説明をいたします．
※ NUOPT 無料紹介セミナー 〜 体感しながら NUOPT 入門
（NUOPT の購入を検討中の方にお勧めです）
http://www.msi.co.jp/nuopt/seminar.html
NUOPT の導入を計画中のお客様のためのセミナーです．本セミナーでは，
NUOPT を適用したアプリケーションに実際に触れていただきながら，説
明を致します．
直近の紹介セミナーについては以下のとおりです．
・12 月 12 日（水） 13:30 〜 16:30 計算不可能領域への挑戦
シフトスケジューリング問題や割り当て問題など，日常的かつ単純な
がら莫大な計算時間を要する問題に対して，高価な CPU など購入せず
に費用対効果に見合ったより現実的な手法（NUOPT によるメタヒュー
リスティクス解法）を紹介いたします．
・ 1 月 29 日（火） 10:30 〜 17:00 金融工学特集を予定
金融工学における最適化手法について，分かりやすくご紹介いたしま
す．久々の金融工学を取り扱ったセミナーです．この機会をお見逃し
なく．なお，詳細につきましては弊社 web ページ
http://www.msi.co.jp/nuopt/seminar_finance.html
に後日掲載いたします．
・ 2 月 25 日（月） 13:30 〜 16:30
内容については，鋭意企画中です．近々に弊社 web ページで告知いた
します．
会場：（株）数理システム・セミナールーム
（東京都新宿区新宿二丁目 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 をお使いのお客様の参加も歓迎しま
す．なお，直近の開催日程は次のとおりです．
12 月 13 日（木） 10:30 〜 17:00
1 月 28 日（月） 10:30 〜 17:00
2 月 27 日（水） 10:30 〜 17:00
会場：（株）数理システム・セミナールーム
（東京都新宿区新宿二丁目 3 番 10 号新宿御苑ビル 4 階）
お申し込みは，（株）数理システム << NUOPT >> 担当
< nuopt-info@ml.msi.co.jp >まで
（坂田 昌一）
==================================================================
※ このメールは，展示会・セミナー等で名刺交換をされた方，過去に
NUOPT に関するお問い合わせを頂いたことのある方，および本メール
マガジンの配信を希望された方にお送りしています．
※ バックナンバーはこちらから御覧頂けます．
http://www.msi.co.jp/nuopt/mailmagazine/index.html
※ 本メールマガジンは等幅フォントでお読みになることを推奨します．
※ 今後このメールマガジンが不要な方は，誠にお手数ですが，「メール
マガジン配信停止」という件名のメールを nuopt-magazine@ml.msi.co.jp
にお送りください．
発行：株式会社 数理システム << NUOPT >> 担当
東京都新宿区新宿二丁目 4 番 3 号 フォーシーズンビル 10 階
==================================================================
|
