-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
数理システム NUOPT メールマガジン http://www.msi.co.jp/nuopt/
2008 Vol.3 ( 2008 年 8 月 20 日 発行 )
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
数理システム NUOPT メールマガジンでは，数理計画法パッケージ NUOPT
に関する様々な情報やご案内を提供していきます．
++++ [目次] +++++++++++++++++++++++++++++++++++++++++++++++++++++
■ <トピック> 数理計画用語集公開！
■ <トピック> 「NUOPT ソリューションページ」のご紹介（第 3 弾）
■ <トピック> NUOPT 勤務表自動作成プログラム セミナーのご案内
～ 御社の勤務管理システムに新しい付加価値を加えてみませんか？
■ <トピック> 発表・出展案内
■ <トピック> 数理計画法の誕生と発展（その 2）
■ <セミナー> NUOPT 無料セミナーのご案内
■ <セミナー> NUOPT 無料紹介セミナー スケジューリング特集 開催中
■ < tips > SIMPLE よくある間違い（第 6 回）
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
*****************************************************************
■ <トピック> 数理計画用語集公開！
*****************************************************************
去る 6 月 30 日に「数理計画用語集」を公開いたしました．
http://www.msi.co.jp/nuopt/glossary/index.html
おかげ様で順調にアクセス数を伸ばしており，用語集編集委員一同，苦労
して作ったかいがあったと実感しております．この数理計画用語集，今後
も成長させていくつもりであり，皆様には暖かい目で見守っていただけれ
ばと思っております．
用語集成長の第一弾として，以下の用語を追加いたしました．
ATLAS, BLAS, GIS, NP困難, NP完全, P=NP問題, S-PLUS, VMS, VRP,
カッティングストック問題, 緩和問題, 局所的収束性, 施設配置問題,
スラック変数, 大域的収束性, データマイニング,
ラグランジュ緩和問題, 列生成法
ご興味がある用語がありましたら，是非ご一読いただければと思います．
ご意見，ご要望等ございましたら，お気軽に用語集編集委員会
nuopt-glossary@ml.msi.co.jp
までご連絡ください．
（村山 昇）
******************************************************************
■ <トピック> 「NUOPT ソリューションページ」のご紹介（第 3 弾）
******************************************************************
前回・前々回のメールマガジンにて，「NUOPT ソリューションページ」と
して，
・GIS ソリューション
・シフトスケジューリングソリューション
の Web 公開をお知らせいたしました．
今回は，シフトスケジューリングソリューションの導入事例に，東日本旅
客鉄道株式会社様にお納めいたしました勤務システム「JINJRE （勤務）」
の案件が加わりましたので，簡単に紹介いたします．
具体的には，大規模勤務システムの中の勤務表自動作成機能の計算エンジ
ンとして NUOPT を用いております．
JR 東日本の駅をはじめとした約 1700 箇所で現在，職員の月単位の勤務
表作成のために本システムが稼働しております．
詳細につきましては，
http://www.msi.co.jp/nuopt/solution.html
を御覧ください．
なお，次回のメールマガジンでは，GIS ソリューションに関し，ある公共
施設に関する施設配置問題の導入事例を御紹介する予定です．
御期待ください．
（多田 明功）
*****************************************************************
■ <トピック> NUOPT 勤務表自動作成プログラム セミナーのご案内
～ 御社の勤務管理システムに新しい付加価値を加えてみませんか？
******************************************************************
---- [ システムインテグレータ向けセミナー 開催日程 ] -------------
・ 9 月 26 日（金） 13:30 ～ 17:00
会場：（株）数理システム・セミナールーム
（東京都新宿区新宿二丁目 3 番 10 号新宿御苑ビル 4 階）
お申し込み先：
（株）数理システム << NUOPT >> 担当 < nuopt-info@ml.msi.co.jp >
------------------------------------------------------------------
システムインテグレータの皆様へ
弊社の数理計画法パッケージ NUOPT は 10 数年にわたり幅広い分野で使わ
れており，昨今では勤務表自動作成のソリューションにも進出，高い評価
と実績を有しております．
勤務管理システムは，システムインテグレータの定番ソフトウェアであり，
お客様からの需要が多い商品の一つですが，競合も激しく，他社との差別
化を図るのが難しいのも事実です．
そこで，弊社の「勤務表自動作成プログラム」を組み込むことにより，お
客様への一歩進んだ提案を実現してみませんか？
このセミナーで，勤務表自動作成についてのノウハウを，わかりやすく紹
介します．
<< セミナー内容 >>
・勤務表作成におけるポイントと注意点
・勤務表自動作成プログラムの実演
・インターフェースについて
・納入事例の紹介
本セミナーの詳細については，下記 URL をご参照ください．
http://www.msi.co.jp/nuopt/seminar_shift.html
（坂田 昌一）
******************************************************************
■ <トピック> 発表・出展案内
******************************************************************
8 月 28 日（木）に（株）構造計画研究所にて 2008 年度第 1 回 OR セミ
ナーが行われます．本セミナーにおいて「実務的なスケジューリング問題
への適用」という題目で弊社取締役 田辺隆人が発表いたします．スケジュー
リング問題のモデリング一般について述べ，例題のデモンストレーションを
交えながら，アルゴリズムに関して解説，最後に実務におけるシフトスケ
ジューリングへの数理計画の適用事例について経験を交えつつお話ししま
す．
本セミナーの詳細については，下記 URL をご参照ください．
http://www.orsj.or.jp/activity/seminar.htm
9 月 10 日（水）・ 11 日（木）に札幌コンベンションセンターで日本 OR
学会 2008 年秋季研究発表会が行われます．本発表会において「非線形半
正定値計画問題に対する主双対内点法の超 1 次収束性」という題目で発表
いたします．こちらは東京理科大学 矢部博教授との共同発表です（発表者
は弊社代表取締役社長 山下浩）．本発表では，以前に我々が提案した非線
形 SDP 問題に対する主双対内点法の超 1 次収束性を議論します．その内
容は，スケーリングなしの主双対内点法（AHO）が 1 ステップで超 1 次収
束することと，スケーリング付きの方法（HRVW/KSH/M,NT）が 2 ステップ
で超 1 次収束することとなります．
本発表会の詳細については，下記 URL をご参照ください．
http://www.orsj.or.jp/nc2008f/
9 月 19 日 (金) ・ 20 日 (土) に青山学院大学(青山キャンパス)でスケ
ジューリング・シンポジウム 2008 が開催されます．本シンポジウムにお
いて「汎用的なシフトスケジューリングツール ～モデリングとその開発～」
という題目で弊社研究員 嶋田佳明が発表いたします．本発表では，NUOPT
にも組み込まれている制約充足アルゴリズム WCSP をエンジンに用いた
ShiftSchedulingPro について紹介する予定です．ShiftSchedulingPro は
これまでのシフトスケジューラーでは実現の出来なかったプロ仕様のスケ
ジューラーであると自負しております．興味のある方はぜひともお聞き頂
きたく存じます．
本シンポジウムの詳細については，下記 URL をご参照ください．
http://www.geocities.jp/schedulingsymposium/
10 月 23 日（木）・ 24 日（金）に東京大学・生産技術研究所で地理情報
システム学会の研究発表大会が行われます．本大会にて「GIS への空間的
最適化エンジンの組込開発」という題目で弊社研究員 多田明功が発表いた
します．こちらは東京大学 貞広幸雄准教授，千葉大学 貞広斎子准教授と
の共同発表です．本発表では，施設配置問題をモチーフとして，地理情報
システム（GIS）と NUOPT の融合に関して紹介いたします．我々としては
地理情報システム学会では初めての発表となるだけに，俄然気合が入りま
す．
本大会の詳細につきましては，下記 URL をご参照ください．
http://wwwsoc.nii.ac.jp/gisa/jp/conference/conference17.html
10 月 30 日 (木) ・ 31 日 (金) に東京工業大学(大岡山キャンパス)で第
20 回 RAMP シンポジウムが開催されます．本シンポジウムにおいて「大規
模離散計画問題へのラグランジュ緩和の応用」および「対局スケジューリン
グにおけるメタヒューリスティクスアルゴリズムの利用」という題目で，
発表いたします．前者は求解困難な大規模離散計画問題に対しラグランジュ
緩和を用いた事例について弊社取締役 田辺隆人が発表いたします．後者は
日本将棋連盟の奨励会の対戦表を NUOPT に搭載されているアルゴリズム
WCSP を用いて作成した事例について私 藤井浩一が発表いたします．
本シンポジウムの詳細については，下記 URL をご参照ください．
http://www.ism.ac.jp/~tsuchiya/RAMP2008/
日本 OR 学会 2008 年秋季研究発表会，スケジューリング・シンポジウム
2008，第 20 回 RAMP シンポジウムでは合わせて出展も行います．興味の
ある方は，是非お立ち寄りください．
（藤井 浩一）
******************************************************************
■ <トピック> 数理計画法の誕生と発展（その 2）
******************************************************************
今回は線形計画法でお馴染み，単体法の発案者 Dantzig についてのご紹
介をいたします．
George B. Dantzig は 1914 年 11 月にアメリカのオレゴン州ポートラン
ドに生まれました．幼少の頃から数学に興味を持っていた彼はメリーラン
ド大学で数学・物理の学科で学位をとり，その後ミシガン大学で 1937年
に数学の修士号をとります．はじめのうちは主に純粋数学を学んでいまし
たが，だんだん興味対象が統計学などの応用数学にうつっていき，修了後
には統計学研究所の職についています．
そして，第二次世界大戦下においてアメリカ空軍から指令が出ました．
「10 万種類の物資と 5 万人の人々の管理方法についての数学的方法をつ
くり出せ」と．このときの解決手法として単体法をつくりだし，Dantzig
は線形計画法の始祖となったのです．また，同時期にソ連でも Kantorovich
によって線形計画法に対する数学的方法が研究されていたのですが，こち
らの研究は国外に知られることがなく時が過ぎ去ってしまいました．線形
計画法において，単体法が現れる以前は微積分法によるラグランジュ未定
乗数法によって解の考察がなされていました．しかし，Dantzig の単体法
-線形計画問題にカスタマイズされた手法- の出現によって以前に比べて
非常に高速な計算が可能となったのです．
第二次世界大戦後，線形計画法は様々な分野へ波及していきます．線形計
画問題の一種である輸送問題に関与していた Koopmans らによって経済学
の興味を線形計画法に引き付け，また von Neumann によってゲーム理論と
の関係が考察されるなど広く応用されるようになったのでした．そして，
より複雑な整数計画問題へと挑戦していくのです．
次回は「整数計画法への発展」．切除平面法と分枝限定法についてのお話を
ご紹介いたします．
参考文献
[1]2005 The Washington Post Company
(http://supernet.som.umass.edu/photos/gdobit.html)
[2]坂和 正敏，線形システムの最適化，森北出版，1984
(家富 淳・岩永 二郎)
******************************************************************
■ <セミナー> NUOPT 無料セミナーのご案内
******************************************************************
---- [ NUOPT 無料セミナー 開催日程 ] -----------------------------
※ NUOPT 無料紹介セミナー
・ 9 月 24 日（水） 10:30 ～ 17:00 金融工学特集
・ 9 月 25 日（木） 13:30 ～ 16:30 体感しながら NUOPT 入門
・ 10 月 15 日（水） 13:30 ～ 17:30 スケジューリング特集
※ NUOPT 無料スキルアップセミナー
・ 10 月 16 日（木） 10:30 ～ 17:00 実戦に向けての NUOPT 演習
会場：（株）数理システム・セミナールーム
（東京都新宿区新宿二丁目 3 番 10 号新宿御苑ビル 4 階）
お申し込み先：
（株）数理システム << NUOPT >> 担当 < nuopt-info@ml.msi.co.jp >
------------------------------------------------------------------
皆様の御要望に応えて，NUOPTセミナーを 4 種類ご用意いたしました．直
近の予定は以下のとおりです．皆様のお越しを心よりお待ちしております．
・NUOPT 無料紹介セミナー・金融工学特集
<< 9 月 24 日（水） 10:30 ～ 17:00 >>
数理計画法と金融工学の接点に関してデモを交えながら，判り易く説明い
たします．実際にデモプログラムを御手許の PC で操作し体感していただ
く時間も設けております．
・NUOPT 無料紹介セミナー ～ 体感しながら NUOPT 入門
<< 9 月 25 日（木） 13:30 ～ 16:30 >>
実際に PC を操作しながら，数理計画法の基礎から応用までを体感してい
ただきます．NUOPT の導入を検討中の方，数理計画法を業務に役立てたい
と考えている方は是非とも御参加ください．
・NUOPT 無料紹介セミナー・スケジューリング特集
<< 10 月 15 日（水） 13:30 ～ 17:30 >>
スケジューリング問題に特化した話題を提供するセミナーです．勤務表作
成に代表されるシフトスケジューリング，工程表作成に代表されるプロジェ
クトスケジューリング，常に現場担当者を悩ましている，これらの問題に
対してのソリューションをご紹介いたします．
・NUOPT 無料スキルアップセミナー ～ 実戦に向けての NUOPT 演習
<< 10 月 16 日（木） 10:30 ～ 17:00 >>
実際に NUOPT を操作しながら，NUOPT の基礎を習得していただきます．
NUOPT 購入後に操作の基礎をマスターしたい方，NUOPT 購入前に操作の感
触を確かめておきたい方に最適のセミナーです．
（坂田 昌一）
******************************************************************
■ <セミナー> NUOPT 無料紹介セミナー スケジューリング特集 開催中
******************************************************************
去る 7 月 18 日（金），スケジューリング問題に特化した「NUOPT 無料紹
介セミナー スケジューリング特集」を開催いたしました．
セミナー当日は，多数の方に御参加いただき，まことにありがとうござい
ました．
セミナーでは，スケジューリング問題の性質の説明に始まり，シフトスケ
ジューリング問題・プロジェクトスケジューリング問題のデモンストレー
ションを行い，その後，実際にスケジューリング問題を解く際に用いてい
るメタヒューリスティクスアルゴリズムのインパクトについて説明し，最
後に，実務におけるスケジューリング問題の応用例を紹介させていただき
ました．
特にデモンストレーション時の，参加された皆様の御理解・御納得されて
いる様子を拝見し，本セミナーの実施意義を実感いたしました．
なお，次回の「NUOPT 無料紹介セミナー スケジューリング特集」からは，
時間を一時間延長し，
13:30 ～ 17:30
とさせていただきます．
一時間延長させていただく分，さらに内容に磨きをかけたセミナーとなる
よう努めていく所存であります．
今後も定期的に開催いたしますので，御興味ある方は是非一度御参加くだ
さい．
（多田 明功）
******************************************************************
■ < tips > SIMPLE よくある間違い（第 6 回）
******************************************************************
このコーナーでは，SIMPLE の記述に関して，お客様が陥りやすい間違いを
少しずつですが紹介していきます．
今回は SIMPLE のモデルにおいて「式」を表わす Expression の使い方を
見ていきます．以下に簡単なフィッティング問題の例を示します．
ある値 y を時間 t に関する 2 次関数で表すものとし，係数 a, b, c を
推定する問題です．以下は y の 観測値 Y[t] と係数 a, b, c を用いた
計算値との時間 t ごとの誤差の二乗和を最小化するモデルです．
------------------------------------------------------------------
Set T; Element t(set=T);
Variable a, b, c;
Parameter Y(index=t);
Expression e(index=t);
Objective err;
err = sum(e[t]*e[t],t);
e[t] = a*t*t + b*t + c - Y[t];
------------------------------------------------------------------
さて，このモデルに適当な Y[t] の値を与えて実行しようとすると，実行
時エラー（NUOPT 3）が出てしまいます．一見正しくモデル化できている
ようですが，なぜでしょうか．
実は Expression e[t] の中身を定義している最終行の文の位置に問題が
あります．e[t] は目的関数 err の定義に使われていますが，SIMPLE で
は Expression は使われる前に中身を定義する必要があるのです．定義さ
れる前に使われた Expression は 0 と解釈されるので注意が必要です．
Expression には，よくある誤用がもう一つあります．それは Expression
の定義にその Expression 自身が出てくる場合です．これは，時間の概念
が出てくる多期間最適化問題や金利の推定問題等にしばしば現れる形です．
例えば，資産額 w[t] が 1 期前の資産額 w[t-1] で表わされることを意
図した以下のようなモデルにおいて，SIMPLE は w[t] を意図通り解釈し
ません．この場合 w[t] に何が入るかは不定です．
------------------------------------------------------------------
...
Expression w(index=t);
w[t] = (1+r)*w[t-1], ... , t > 1;
...
------------------------------------------------------------------
回避策として Expression を Variable として宣言し，式の定義部を等式
制約で置き換える方法が挙げられます．または C++ の for 文を使って，
例えば以下のように w[t] を定義することもできます．
------------------------------------------------------------------
...
Expression w(index=t);
for(int i = 2; i <= n; i++){
w[i] = (1+r)*w[i-1];
}
...
------------------------------------------------------------------
式の重複記述を避け，モデルを見やすくする Expression ですが，使い方
を誤ると見つけにくいエラーを招くことがあります．「綺麗な薔薇には棘
がある」と言いますが，Expression の扱いは慎重にしたいものです．
（村山 昇）
==================================================================
※ このメールは，展示会・セミナー等で名刺交換をされた方，過去に
NUOPT に関するお問い合わせを頂いたことのある方，および本メール
マガジンの配信を希望された方にお送りしています．
※ バックナンバーはこちらから御覧頂けます．
http://www.msi.co.jp/nuopt/mailmagazine/index.html
※ 本メールマガジンは等幅フォントでお読みになることを推奨します．
※ 今後このメールマガジンが不要な方は，誠にお手数ですが，「メール
マガジン配信停止」という件名のメールを nuopt-magazine@ml.msi.co.jp
にお送りください．
発行：株式会社 数理システム << NUOPT >> 担当
東京都新宿区新宿二丁目 4 番 3 号 フォーシーズンビル 10 階
==================================================================
