-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
数理システム NUOPT メールマガジン http://www.msi.co.jp/nuopt/
2008 Vol.4 ( 2008 年 11 月 5 日 発行 )
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
数理システム NUOPT メールマガジンでは，数理計画法パッケージ NUOPT
に関する様々な情報やご案内を提供していきます．
++++ [目次] +++++++++++++++++++++++++++++++++++++++++++++++++++++
■ <トピック> 数理システムユーザコンファレンス 2008 のご案内
■ <トピック> MP.doc のご紹介とバージョンアップのご案内
■ <トピック> 「NUOPT ソリューションページ」のご紹介（第 4 弾）
■ <トピック> 数理計画用語集 用語追加
■ <トピック> 発表・出展報告
■ <トピック> 数理計画法の誕生と発展（その 3）
■ <セミナー> NUOPT 無料セミナーのご案内
■ < tips > 式の値，微係数を直接与える裏技
■ < tips > SIMPLE よくある間違い（第 7 回）
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
*****************************************************************
■ <トピック> 数理システムユーザコンファレンス 2008 のご案内
*****************************************************************
恒例の弊社主催の「数理システムユーザーコンファレンス」が今年も開催
されます．弊社製品の先進的な導入事例について，多方面にわたる方々か
ら講演がございます．
今年の開催日は 11 月 14 日（金），場所は六本木アカデミーヒルズ（六
本木ヒルズ 49 階）となっております．
なお，参加費用は無料ですが，事前のお申込みが必要となります．
詳細内容とお申込みについては弊社 Web ページ
http://www.msi.co.jp/userconf/08/
をご覧になってください．
今年は NUOPT に関する講演が 4 本ございます．
[ 日本電信電話株式会社 辻野 雅之 氏 ]
IP 網トラヒックエンジニアリングにおける最適化技術
[ 東京大学 貞広 幸雄 氏 ]
GIS への最適配置モデルの導入 －システム開発と適用－
[ 棋士五段 西尾 明 氏，日本将棋連盟 常盤 秀樹 氏，数理システム
藤井 浩一 ]
日本将棋連盟・関東奨励会における対戦表自動作成システムの導入事例
[ 数理システム 田辺 隆人 ]
東日本旅客鉄道株式会社様 勤務システム JINJRE (勤務)における数理計
画法を用いた自動勤務表作成
また，展示ルームでは NUOPT のデモも行っております．今回は，動画で
NUOPT を体感できる NUOPT 紹介 CD（NUOPT 試用版も付属）の配布も予定
しております．是非ともお立ち寄りください．
（坂田 昌一）
******************************************************************
■ <トピック> MP.doc のご紹介とバージョンアップのご案内
******************************************************************
Microsoft Word で最適化 MP.doc (エムピードック)が 1.4 にバージョン
アップしました．
MP.doc V1.4 では累積的な不具合の修正を行い，MathType の最新版である
バージョン 6.0 と Microsoft Word 2007 に対応しました．
MP.doc V1.3 以前のバージョンをお使いのユーザ様は
http://www.msi.co.jp/nuopt/MPsupport/support_mpdoc1.html
よりアップグレードすることができます．
MP.doc とは，モデリング言語 SIMPLE ではなく MathType の数式を使って
モデル記述を行い，Microsoft Word ドキュメント上で最適化を実行するこ
とができる NUOPT のアドオンパッケージです．
・ モデリング言語はちょっと難しそう..
・ 数式なら書けるのですが..
・ 言語の習得に時間をかけず，すぐに問題を解きたい．
という方にお薦めのソフトウェアです．
MP.doc についてもっと詳しく知りたい方は，MP.doc V1.4 の WEB ページ
http://www.msi.co.jp/nuopt/MPdoc/MPdoc.html
をご参照ください．
（高橋 良徳）
*****************************************************************
■ <トピック> 「NUOPT ソリューションページ」のご紹介（第 4 弾）
******************************************************************
これまで，NUOPT ソリューションページに関しまして，
・GIS ソリューション
・シフトスケジューリングソリューション
の紹介をいたしました．
今回は，GIS ソリューションに関しまして，以下の導入事例を追加してお
ります．
品川区教育委員会学務課様による最適学校配置・最適学区の検証事例
詳細につきましては，
http://www.msi.co.jp/nuopt/gis/case_facility.html
を御覧ください．
（多田 明功）
******************************************************************
■ <トピック> 数理計画用語集 用語追加
******************************************************************
弊社 数理計画部では，「数理計画用語集」を公開しています．
http://www.msi.co.jp/nuopt/glossary/index.html
おかげ様で NUOPT に関係する HP の中でアクセス数 No.1 のサイトとなり
ました．これに驕ることなく，今後も「数理計画用語集」を成長させてい
きたいと考えております．
今回は以下の用語を追加しております．
Dantzig-Wolfe 分解，IIS，SimpleExternalFunc，ラグランジュ緩和法，
ベクトル，サポートベクターマシン，集積点，妥当不等式，実行不可能，
実行可能解，最適解，絶対値，線形，非線形，負定値，分散電源
ご興味がある用語がありましたら，是非ご一読いただければと思います．
ご意見，ご要望等ございましたら，お気軽に用語集編集委員会
nuopt-glossary@ml.msi.co.jp
までご連絡ください．
（村山 昇）
******************************************************************
■ <トピック> 発表・出展報告
******************************************************************
2008 年 9 月 10 日（水）・ 11 日（木）に札幌コンベンションセンター
で行なわれた日本 OR 学会 2008 年秋季研究発表会において，「非線形半
正定値計画問題に対する主双対内点法の超 1 次収束性」という題目で弊社
代表取締役社長 山下浩（共同研究者：東京理科大学 矢部博 教授）が発表
いたしました．この結果は現在のところ理論的なものですが，今後の実装
に反映させたいと考えております．
2008 年 9 月 19 日 (金) ・ 20 日 (土)，青山学院大学(青山キャンパス)
にて行われたスケジューリング・シンポジウム 2008 において，出展・発
表を行いました．出展ブースにおいては，ShiftSchedulingPro のデモを行
い，お越し頂いた方にはこういった機能も欲しいといった意見も頂戴し，
当方にとっても非常に有益な時間を過ごすことが出来ました．発表に関し
ましては，「汎用的なシフトスケジューリングツール ～モデリングとその
開発～」を弊社研究員 嶋田佳明が発表致しました．PC の不都合で多少も
たついた所もありましたが，質疑応答では「価格はいくらなのか」といっ
た現実的な質問もあり，ShiftSchedulingPro の導入について興味を持って
頂けたのではないかと思っております．本ソフトは現在 Version 2 の開発
中であり，GUI のさらなる操作性の向上・新機能の追加を行っております．
本ソフトに関しまして，弊社 Web ページ
http://www.msi.co.jp/nuopt/shift/shiftschedulingpro.html
に紹介を載せております．興味がございましたらご覧ください．
2008 年 10 月 23 日（木）・24 日（金），東京大学・生産技術研究所に
て行われました第 17 回地理情報システム学会学術研究発表大会において，
「GIS への空間的最適化エンジンの組込開発」という題目で弊社研究員 多
田明功が発表いたしました．短い発表時間の中で，数理計画というある種
GIS とは異なる分野をお伝えすることは正直難しかったのですが，多くの
聴衆の皆様が本発表に興味を示していただきまして，大変嬉しく感じてお
ります．また，発表内容に関しまして，御質問・御助言をいただき，まこ
とにありがとうございました．今回発表しました GIS ソリューションに関
しまして，弊社 web ページ
http://www.msi.co.jp/nuopt/gis/index.html
に紹介を載せております．興味がございましたらご覧ください．
2008 年 10 月 30 日 (木) ・ 31 日 (金) に東京工業大学(大岡山キャン
パス)で第 20 回 RAMP シンポジウムが開催されました．本シンポジウムに
おいて「大規模離散計画問題へのラグランジュ緩和の応用」を弊社取締役
田辺隆人が，「対局スケジューリングにおけるメタヒューリスティクスア
ルゴリズムの利用」を私 藤井浩一が発表いたしました．私の発表におきま
しては，関東奨励会の対局スケジュール作成というゲームスケジューリン
グの応用に関してのものでしたが，実務におけるスケジューリングの泥臭
さを少しでもお伝えできたならば幸いです．発表しました対局スケジュー
リングに関しましては，弊社 Web ページ
http://www.msi.co.jp/nuopt/shift/case_shogi.html
に紹介を載せております．興味がございましたらご覧ください．
（藤井 浩一）
******************************************************************
■ <トピック> 数理計画法の誕生と発展（その 3）
******************************************************************
今回は「整数計画法への発展」と題しまして，整数計画法の誕生，発展お
よび現状をご紹介いたします.
整数計画法は，1958 年 Ralph Gomory によって研究がはじまりました．こ
れ以前には Fulkerson, Johnson, Dantzig らによって巡回セールスマン問
題が研究されるなど個別の問題が研究されていました．Gomory によって初
めて統一的な整数計画法の研究が行なわれたのです．
当時 Gomory は海軍のコンサルタントを行なっていました．海軍部隊に関
する線形計画のモデルを考案し発表したところ，聴衆から「空母が 1.3 と
いう答えは意味がないので，整数の答えが欲しい」という意見が出たそう
です．この意見を受け Gomory は整数計画法への挑戦を始めました．
Gomory の手法は，「カット」と呼ばれる制約式を問題に追加し，緩和解を
整数解に近づけていくものです．Gomory カットと呼ばれる有名なカットも
この研究の中で生まれたものです．この手法は「切除平面法」と呼ばれ，
理論的にその有限性が保証されているケースもあります．しかし残念なが
ら収束が遅く実用へは至りませんでした．
一方で，Lang-Doig によって開発された「分枝限定法」という手法を整数
計画法に用いる研究が行われました．分枝限定法は列挙法の一種です．切
除平面法に比べれば単純なアルゴリズムと言えますが，実用的に有効であ
り，多くの整数計画法商用ソルバーにおいて採用されました.
1990 年代に入り，Balas，Ceria，Cornuejols，Natraj らによって Gomory
カットが分枝限定法と有効に組み合わせられることが示されました．これ
によって Gomory カットが再評価されたのです．個別の問題に対しカットを
適用する研究はそれまでも進められていましたが，Balas らによって初め
て一般的な整数計画問題に対し分枝限定法とカットをうまく組み合わせら
れることが示されたのです．今では，有効なカットの導入は商用ソルバー
にとって欠かせない要素の一つとなっております．
また上記以外にも整数計画法のアルゴリズムは数多く研究されています．
Haus，Koppe，Weismantel らの integral basis method と呼ばれるアルゴ
リズムはその一つです．このアルゴリズムは，代数的手法を用いて目的関
数を改善する実行可能解を求めていきます．まだ適用されている問題は小
規模ですが，将来を期待されているアルゴリズムです．
日々進展していく整数計画法ですが，弊社も遅れをとらぬようその研究・
開発に力を入れております．近い将来，その成果を皆様にお見せできれば
と思います．
次回は「新・線形計画法 内点法 VS 単体法」と題しまして，線形計画法
の発展の歴史をご紹介いたします．
参考文献：
[1] E.Balas, S.Ceria, G.Cornuejols, N.Natraj, "Gomory Cuts
Revisited" (1996), Operations Research Letters 19.
[2] R.E.Gomory, "Early Integer Programming", History of
Mathematical Programming, A Collection of Personal
Reminiscences, North-Holland, Amesterdam (1991) 55-61.
[3] UU.Haus, M.Koppe, R.Weismantel, "The integral basis method
for integer programming", Mathematical Methods of Operations
Research (2001)53,353-361.
（藤井 浩一）
******************************************************************
■ <セミナー> NUOPT 無料セミナーのご案内
******************************************************************
---- [ NUOPT 無料セミナー 開催日程 ] -----------------------------
※ NUOPT 無料紹介セミナー
・ 11 月 26 日（水） 13:30 ～ 16:30 体感しながら NUOPT 入門
・ 11 月 28 日（金） 13:30 ～ 17:30 スケジューリング特集
・ 12 月 2 日（火） 10:30 ～ 17:00 金融工学特集
・ 1 月 28 日（水） 10:30 ～ 17:00 金融工学特集
※ NUOPT 無料スキルアップセミナー
・ 12 月 11 日（木） 10:30 ～ 17:00 実戦に向けての NUOPT 演習
・ 1 月 29 日（木） 10:30 ～ 17:00 実戦に向けての NUOPT 演習
会場：（株）数理システム・セミナールーム
（東京都新宿区新宿二丁目 3 番 10 号新宿御苑ビル 4 階）
お申し込み先：
（株）数理システム << NUOPT >> 担当 < nuopt-info@ml.msi.co.jp >
なお，日程については以下の URL でもご確認頂けます．
http://www.msi.co.jp/nuopt/seminar_nittei.html
------------------------------------------------------------------
今回はセミナー後に頂きましたアンケートの一部を紹介したいと思います．
※スケジューリング特集
・デモの時間をもう少し短くしてもいい気がします．各制約条件のモデル
（数式）を少し解説いただきたかったです．
・1 つ 1 つの制約を追加しながらデモができたので，解の変化の状況を把
握しやすく理解しやすかった．
スケジューリング特集では「どのようなことができるか」という点を主に
取り上げているので「どのように設定するか」という説明に対しては，や
や不十分であると認識しております．今後，限られた時間の中でより濃密
なセミナーになるよう心がけていきます．
※金融工学特集
・NUOPT の使い方が分かってよかった．しかし，サンプルデータが単純す
ぎたので，実務的なデータも取り入れて欲しかった．
・定式化について，すでに知っていたこと，知らなかったことを含めて勉
強になりました．
・少し難解なため，もう一度お聞きしたく思いました．
・実例があってよかった，面白かった．
金融工学特集は実務に具体的に携わっている方からアカデミックな方まで
様々な層の方がいらっしゃいます．ご来場頂きました方の関心分野を問わ
ず興味深いセミナーができるように今後も心がけていきます．
（佐藤 誠）
******************************************************************
■ < tips > 式の値，微係数を直接与える裏技
******************************************************************
ここでは知る人ぞ知る，マニアックな関数 SimpleExternalFunc の仕様を
紹介します．「数理計画用語集」内でも少し触れていますが，こちらは外
部非公開関数になりますので取り扱いには注意してください．
ある関数値の値の評価及び微係数が代数的に表現できないような問題に使
用することができます．モデルファイル内で表現したい式を Expression
で準備します．
------------------------------------------------------------------
Expression y; // 今回は y = x[1]*x[1] + 2*x[2]*x[2] だとします．
------------------------------------------------------------------
次にダミーのパラメータと y に渡す式を準備します．
------------------------------------------------------------------
Set I = "1 2";
Element i(set = I);
Parameter p,q; // ダミーなので特に意味はない
Variable x(index = i);
Expression z(index = i);
z[i] = x[i];
y = extfunc(z[i],i,p,q);
// ここでは y = f(z[i]) という風に指定するのみ．
------------------------------------------------------------------
この後，extfunc の中身に関しての詳細設定を行います．モデルファイル
の最後尾で以下のように設定します．
------------------------------------------------------------------
%%%%% %%%%%
#include <stdio.h>
// extfunc を使うとコールバックされる C++ 関数
// n : x の長さ
// x : 変数を double のベクターにしたもの．
// m , p : ダミーの認識，説明は割愛
void SimpleExternalFunc(int n,double* x,int m,double* p,double* f,
double* g,double* h)
{
if ( f ) { // f が non-null なら f を設定する．
*f = x[0]*x[0] + 2*x[1]*x[1];
}
if ( g ) { // g が non-null なら gradient を設定する．
g[0] = 2*x[0];
g[1] = 4*x[1];
}
if ( h ) { // h が non-null なら hessian を設定する．
h[0,0] = 2;
h[1,0] = 0;
h[0,1] = 0;
h[1,1] = 4;
}
}
------------------------------------------------------------------
SimpleExternalFunc 内で f , g , h を設定することによって，複雑な応
答も表現することができます．
（佐藤 誠）
******************************************************************
■ < tips > SIMPLE よくある間違い（第 7 回）
******************************************************************
このコーナーでは，SIMPLE の記述に関して，お客様が陥りやすい間違いを
少しずつですが紹介していきます．
今回は SIMPLE の文法から少し離れて，求解パラメータの設定や解の表示
といった入出力周りについての間違いを紹介します．
モデルは前回と同じフィッティング問題ですが，内点法系の解法の停止条
件として用いる最適性条件の残差の上限値（options.eps で設定）をモデ
ルの外から Parameter を介して与え，さらに観測値と理論値の誤差が
0.03 より大きいものについては，その誤差を出力するものとします．
前回の正解モデルに後ろの 3 行を加え，やりたいことは記述したつもりで
すが，このモデルは意図通り動くでしょうか．
------------------------------------------------------------------
Set T; Element t(set=T);
Variable a, b, c;
Parameter Y(index=t);
Expression e(index=t);
e[t] = a*t*t + b*t + c - Y[t];
Objective err;
err = sum(e[t]*e[t],t);
Parameter p;
options.eps = p;
simple_printf("%f,%f\n", t, e[t], fabs(e[t]) >= 0.03);
------------------------------------------------------------------
実はこのモデルには 3 つの間違いが含まれています．
まず 1 つ目です．このモデルをコンパイルすると，後ろから 2 行目のと
ころで「'Parameter' から 'double' に変換できません」のようなエラー
が出てしまいます．
これは double 型であるべき options.eps に Parameter 型の p を直接代
入しようとしたために起こったエラーです．SIMPLE では，
options.eps = p.val.asDouble();
として，Parameter 型の p を陽に double 型に変換する必要があります．
2 つ目の間違いは「観測値と理論値の誤差が 0.03 より大きい」を表わす
fabs(e[t]) >= 0.03
という条件式にあります．結論から言うと，ここは
fabs(e[t].val) >= 0.03
としなければなりません．SIMPLE には「Variable,Objective,Expression,
VariableParameter のオブジェクトの現在の値を参照するときはオブジェ
クトの後ろに .val をつけなければならない」というルールがあります．
.val をつけない場合の動作は保障されていません．ただし，Parameter に
ついてはこの限りではありません．
最後に，実はこれが最もよくある間違いなのですが，最適化結果を参照す
るためには，その前に
solve();
を書く必要があります．この 1 文が書かれている場所で求解が行われ，
書かれていない場合はモデルの最後で求解が行われます．今回の例では，
options.eps の設定より後ろ，simple_printf より前に solve(); を書く
必要があります．
これらの間違いは，知らないと非常に気が付きにくく厄介です．特に
solve(); を書き忘れてもエラーが起きることもなく，結果を見るつもり
が，初期値を見ることになってしまうので，注意が必要です．
しかし，ここで得られた知識は SIMPLE を有効活用する上では必須といえ
るでしょう．良薬口に苦し，一つ一つ地道に学んでいきたいものです．
（村山 昇）
==================================================================
※ このメールは，展示会・セミナー等で名刺交換をされた方，過去に
NUOPT に関するお問い合わせを頂いたことのある方，および本メール
マガジンの配信を希望された方にお送りしています．
※ バックナンバーはこちらから御覧頂けます．
http://www.msi.co.jp/nuopt/mailmagazine/index.html
※ 本メールマガジンは等幅フォントでお読みになることを推奨します．
※ 今後このメールマガジンが不要な方は，誠にお手数ですが，「メール
マガジン配信停止」という件名のメールを nuopt-magazine@ml.msi.co.jp
にお送りください．
発行：株式会社 数理システム << NUOPT >> 担当
東京都新宿区新宿二丁目 4 番 3 号 フォーシーズンビル 10 階
==================================================================
