数理システム 最適化メールマガジン

バックナンバー ( 2008 Vol.2 ) 2008 年 5 月 15 日 発行

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
  数理システム NUOPT メールマガジン  http://www.msi.co.jp/nuopt/
                           2008 Vol.2 ( 2008 年 5 月 15 日 発行 )
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

数理システム NUOPT メールマガジンでは,数理計画法パッケージ NUOPT 
に関する様々な情報やご案内を提供していきます.

++++ [目次] +++++++++++++++++++++++++++++++++++++++++++++++++++++
  ■ <トピック> 「NUOPT ソリューションページ」のご紹介
  ■ <トピック> 最新パッチリリースのお知らせ
  ■ <トピック> 用語集を公開いたします
  ■ <トピック> 出展・発表報告
  ■ <トピック> 数理計画法の誕生と発展(その 1)
  ■ <セミナー> NUOPT 無料セミナーのご案内
  ■ <セミナー> NUOPT 無料紹介セミナー スケジューリング特集 開催!
  ■ <  tips  > min(),max() 関数の使い所と注意
  ■ <  tips  > SIMPLE よくある間違い(第 5 回)
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

*****************************************************************
■ <トピック>  「NUOPT ソリューションページ」のご紹介
*****************************************************************

前回のメールマガジンにて,「NUOPT ソリューションページ」第一弾とし
て「ArcGIS と NUOPT の融合」を紹介いたしました.
具体的には,地図情報システム ArcGIS と NUOPT との連携により,NUOPT
の最適化計算によって得られた結果を地図上にて可視化することを実現い
たしました.可視化した応用事例といたしましては,施設配置問題・配送
スケジューリング問題等が Web ページにて既に公開されております.
なお,前回のメールマガジンにて紹介させていただいたところ,各方面か
ら反響をお寄せいただきました.誠にありがとうございました.

今回は「NUOPT ソリューションページ」第二弾といたしまして,「NUOPT を
用いたシフトスケジューリング」について紹介いたします.具体的には,
ナーススケジューリングに代表されるシフトスケジューリングの概略,導
入実績,さらには弊社自社開発のスケジューラー「Shift Scheduling Pro
(シフトスケジューリングプロ)」の紹介を Web にて公開いたします.
導入実績に関しましてはなかなか公開できないものが多いのですが,まず
一例として日本将棋連盟(奨励会)に導入いたしました「対戦の助(すけ)
― 将棋対戦スケジュール自動生成システム ―」を紹介いたします.その
他の事例につきましても順次掲載いたしますので御期待ください.

上記に関する詳細につきましては,Web ページ
    http://www.msi.co.jp/nuopt/solution.html
にて御確認ください.

                                                 (多田 明功)

******************************************************************
■ <トピック>  最新パッチリリースのお知らせ
******************************************************************

NUOPT V10 がリリースされて,はや 2 ヶ月が経とうとしておりますが,最
新の NUOPT は如何でしょうか.ソルバーとしての新機能・チューニングだ
けでなく, GUI の改良など,エンドユーザ様にとって更に使いやすくなっ
ているものをリリースできたと自負しております.

さて,今回はリリース後に発見された不具合を修正するパッチをリリース
する運びとなりました.主な修正点は,以下の 5 点です.

  1. Ver.10.1.0 において solveQP を実行した場合に異常終了する.
  2. min/max 関数において一般の非線形関数を用いた際に,場合によって
     は異常終了する.
  3. min/max 関数において線形関数を用いた際に,表示が乱れる,あるい
     は計算が正しく行われない可能性がある.
  4. IIS 検出機能において,IIS の中に上下限制約が現れた場合の .sol
     の表示が乱れる.
  5. GUI にて wcsp を用いた場合,Excel/GUI 側に解の更新が正しく検知
     されない.

なお,パッチについての詳細は以下の URL からご覧ください.
    http://www.msi.co.jp/nuopt/support/nuopt_to_10_1_8_patch.html

不具合・パッチについてのご不明な点につきましては弊社サポート
( nuopt-support@ml.msi.co.jp ) 宛てにお問い合わせください.

                                                 (新田 利博)

*****************************************************************
■ <トピック>  用語集を公開いたします
******************************************************************

WCSP て何?数理計画におけるデザインパターンとは?双対問題?分枝限定
法?SIMPLEX 法て何だっけ?...いまさら聞けないあの用語,我々が解
説します.

この度,我々 NUOPT 担当で数理計画に関する用語をまとめた用語集を公開
することにしました.我々が普段使っている用語,専門的な用語から日常
的な用語まで,NUOPT 担当の技術者が懇切丁寧に,時にはカジュアルに解
説いたします!

6 月末公開予定.お楽しみに!

                                                 (村山 昇)

******************************************************************
■ <トピック>  出展・発表報告
******************************************************************

2008 年 3 月 19 日の統計数理研究所における研究集会「最適化 : モデ
リングとアルゴリズム」において,「非線形 SDP 問題に対する主双対内点
法の局所的超 1 次収束性について」というタイトルで,東京理科大学矢部
博先生,弊社山下浩(発表者)が発表致しました.

また,2008 年 3 月 25 日~ 26 日,京都情報大学院大学にて行われた OR
学会 2008 年春季研究発表会にて,出展・発表を行いました.

今回の出展ブースは,入り口から入ってすぐの場所だったため,多くの方
にお声をかけて頂きました.リリースしたての NUOPT V10 については,多
くの興味をお寄せ頂きました.研究者・実務家の方々のご意見を生で聞く
機会はそれほど多くありませんので,当方としては非常に有用な時間を過
ごさせて頂きました.今後とも出展ブースを見かけた際には,お声掛けい
ただきたく存じます.

発表に関しては,今回弊社から 1 名(私なのですが…)発表をさせて頂き
ました.目を疑うほどの錚々たる方々の前で発表することができ,非常に
よい経験をさせて頂きました.内容としても,面白かったというご意見を
多数頂きまして,発表後は胸を撫で下ろしました.話の内容は NUOPT の
WCSP の新機能について行ったのですが,V11 ではさらに新機能をご提供す
る予定でございますので,大規模 0-1 計画問題を抱えている方々はご期待
ください.

                                                 (佐藤 誠)

******************************************************************
■ <トピック>  数理計画法の誕生と発展(その 1)
******************************************************************

メールマガジンの新企画として,本年度は「数理計画法の歴史」を取り上
げたいと思います.数理計画法は他の学問(たとえば数学とか天文学等)
と比較すると新しい学問だと言えます.歴史が身近に感じられ,その点で
は非常に興味を持てるなと私は感じております.執筆者は,皆様により面
白みを感じて頂くために,ジャンル毎に深く精通している者が担当する予
定でございます.

数理計画法の現在の位置づけとしては,「産業界で使える学問(技術)」
であると考えています.応用ジャンルとしては,金融・広告・電力...
と挙げればきりがなく,最近ではスポーツの対戦スケジューリングにも応
用されているという話をよく聞きます.

このように産業界側からの要請が多く存在することもあり,「理論的に優
れたアルゴリズム」というだけではこの世界では認められることは難しい
ようです.「解けてナンボ」という風潮が強く,実際に解ける手法という
ものが好まれているように感じます.「解を出す」という視点が重要なこ
とからも分かる通り,数理計画法はコンピュータの発展とは切っても切り
離せないものです.アルゴリズムの「良さ」「悪さ」というのは一概に判
断することは難しく,時代のコンピュータのスペックによって立場が逆転
することもありえるものです.

このコーナーでは,数理計画法における歴史的なブレークスルーを中心に
話を進めて行きたいと思います.

  -- 数理計画法の誕生            線形計画問題と単体法
  -- 整数計画法への発展          切除平面法~分枝限定法
  -- 新・線形計画法              内点法 VS 単体法
  -- 非線形計画法の確立          内点法と自動微分法
  -- さらなる大規模問題への挑戦  メタヒューリスティクス解法

と,今回は前置きだけになってしまいましたが,次回は「数理計画法の誕
生」ということで,巨匠 Dantzig にご登場いただきたいと思います.

                                                 (佐藤 誠)

******************************************************************
■ <セミナー>  NUOPT 無料セミナーのご案内
******************************************************************

---- [ NUOPT 無料セミナー 開催日程 ]------------------------------
※ NUOPT 無料紹介セミナー  ~  体感しながら NUOPT 入門
    ・ 6 月 18 日(水)  13:30 ~ 16:30
    ・ 7 月 17 日(木)  10:30 ~ 17:00 << 金融工学特集 >>
    ・ 7 月 18 日(金)  13:30 ~ 16:30 << スケジューリング特集 >>
※ NUOPT 無料スキルアップセミナー  ~  実戦に向けての NUOPT 演習
    ・ 6 月 19 日(木)  10:30 ~ 17:00

会場:(株)数理システム・セミナールーム
            (東京都新宿区新宿二丁目 3 番 10 号新宿御苑ビル 4 階)
お申し込み先:
  (株)数理システム << NUOPT >> 担当  < nuopt-info@ml.msi.co.jp >
------------------------------------------------------------------

NUOPT 購入検討中の方々に向けて,そして NUOPT 購入後の使い方習得の場
として,弊社では,NUOPT 無料セミナーを開催しております.

直近のセミナーについては以下のとおりです.

・ 6 月 18 日(水)NUOPT 無料紹介セミナー  13:30 ~ 16:30
      ~ 業務改善のための数理計画法 ~
製造業の生産現場においては品質向上・コスト削減・納期短縮を目標にし
ながら,常に業務改善が求められています.適切な材料配合は如何に行う
べきか?エネルギー消費を最小にするための機器運転計画とは?最短納期
のための工程設計とは?・・・など業務改善の観点から数理計画法を捉え
て NUOPT が実現できるソリューションを紹介していきます.また,公平か
つ効率的な出勤シフトの作成,最大効果を得るための予算配分など,事務
分野での業務改善にも数理計画法は効果を発揮します.事務系・技術系を
問わず,業務改善のための一手法として数理計画法の導入をお考えの方々
のお越しをお待ちしております.

・ 6 月 19 日(木) NUOPT 無料スキルアップセミナー  10:30 ~ 17:00
NUOPT 購入後に操作方法の基礎を素早く習得することが目的のセミナーで
す.勿論,購入前の検討のための御参加も歓迎いたします.
このセミナーでは,簡単な例題から始めて,代表的ないくつかの例題を演
習形式で説明いたします.その際に,例題の制約条件式や目的関数等の一
部分を実際に記述していただき,モデリング言語 SIMPLE の記述に慣れて
いただくことが出来るよう配慮しております.
また,モデルの定式化のコツやアプリケーション開発のための連携処理に
ついても,簡単にお話し差し上げる予定です.
詳細は http://www.msi.co.jp/nuopt/skillupseminar.html まで.

・ 7 月 17 日(木) NUOPT 無料紹介セミナー  10:30 ~ 17:00
      ~ 金融工学特集 ~
好評の金融工学特集は,過去 3 回とも開催告知後まもなく定員に達してし
まい,皆様に御迷惑をお掛けしました.そこで過去 3 回と同内容で 4 度
目の金融工学特集を開催いたします.なお,今回も多数のお申し込みが予
想されますので,参加ご希望の方は早めにお申し込みください.
詳細は http://www.msi.co.jp/nuopt/seminar_finance.html まで.

・ 7 月 18 日(金) NUOPT 無料紹介セミナー  13:30 ~ 16:30
「スケジューリング特集」と銘打ち新企画が進行中です.詳細につきまし
ては,次の記事をご参照ください.

                                                 (坂田 昌一)

******************************************************************
■ <セミナー>  NUOPT 無料紹介セミナー スケジューリング特集 開催!
******************************************************************

これまで NUOPT 紹介セミナーの特別バージョンといたしまして「NUOPT 
無料紹介セミナー 金融工学特集」を数回開催いたしました.
今回は,新たな特別セミナー「NUOPT 無料紹介セミナー スケジューリン
グ特集」の開催日が 7 月 18 日(金)に決定いたしましたので,簡単に
概略を紹介いたします.

工場や病院等の現場において,スケジュール作成は不可欠な作業ではある
ものの,その作成には幾つかの困難を伴い,結果として現場では長年スケ
ジュール作成に携わっている,いわゆる「職人さん」が存在するのが現状
です.この現象は,多岐に渡る制約,なかなか明文化することのできない
制約を鑑みてスケジュールを作成しなければならないため,と我々は認識
しております.

本セミナーでは考慮すべきスケジュール問題に対し,いかにして数理計画
問題として定式化・モデル化するか,定式化したモデルに対し NUOPT の
どのような解法を用いて実際の解(スケジュール)を得るかに照準を合わ
せて説明させていただきます.

具体的には,ナーススケジューリング問題に代表されるシフトスケジュー
リング,ジョブショップ問題に代表される資源制約付きのプロジェクトス
ケジューリングの例題を通じて,上述した「難しさ」を体験しつつ,実際
にスケジュール作成までの一連の過程を参加者の皆様に体感していただき
たく存じます.

奮って御参加ください.

※本セミナーは,実務に数理計画を活用されている方から,スケジューリ
ング問題への数理計画の適用方法を知りたい方まで,スケジューリング問
題に携わる様々な職場の方,研究者の方を対象にしています.

※参加者の皆様には本セミナーのために作成されたデモプログラムを体験
していただきます(マシンは会場にて準備しております).

詳細につきましては,Web ページ
    http://www.msi.co.jp/nuopt/seminar_scheduling.html
にて御確認ください.

                                                 (多田 明功)

******************************************************************
■ <  tips  >  min(),max() 関数の使い所と注意
******************************************************************

ある施設配置問題を考えます.施設によってサービスされる顧客は 20 人
(a,b,c,..,s,t),施設の設置可能な場所は 100 通り,施設を設置する各場
所 i と顧客 j の距離が A[i,j] というデータ行列として定義されている
とします.データ行列 A は SIMPLE 可読な .csv 形式では次のように記述
されているとしましょう.

------------------------------------------------------------------
A,a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t
1,5,5,5,17,5,15,12,18,2,12,9,16,5,2,14,20,13,20,9,5
2,10,5,4,7,10,12,3,5,20,5,5,16,17,12,3,2,18,14,3,5
3,9,7,5,4,13,9,20,3,4,5,5,5,8,15,20,3,16,12,8,20
          .. (省略) ..
99,2,1,16,8,1,5,20,16,5,15,4,1,13,12,8,6,5,13,7,6
100,5,10,5,1,13,5,5,8,14,7,16,17,2,5,6,8,19,7,3,5
------------------------------------------------------------------

100 通りの設置箇所のうち実際には 10 個以上の場所を選定して施設を配
置するとします.「顧客 j から,最も遠い場所にある施設までの距離」を
すべての顧客について和を取ったものを,配置の「良さ」として定義しま
す.例えば一人の顧客は設置される施設のすべてに何らかの接触をするも
のして,ある顧客が最も遠い場所に出掛けてゆく場合の「しんどさ」を最
小化したい,といった状況が考えられるでしょうか.この問題は混合整数
線形計画問題として記述でき,SIMPLE では次のように記述されます.

------------------------------------------------------------------
Set J; // 顧客集合
Set I; // 施設集合
Element i(set=I),j(set=J);
Parameter A(index=(i,j));
IntegerVariable x(index=i,type=binary); // 施設 i を選ぶかどうか
Variable y(index=j); // 顧客 j から存在する施設までの最大距離になる
A[i,j]*x[i] <= y[j];
sum(x[i],i) >= 10;
Objective obj(type=minimize);
obj = sum(y[j],j);
------------------------------------------------------------------

解いてみると設置場所は正確に 10 箇所となることがわかります.余計な
場所に施設を設置することは,顧客の「しんどさ」を増大させることにし
かならないことから説明が付きます.

顧客や設置場所が多くなると,この問題を厳密に解くことはかなり難しく
なりますが,そのような状況において威力を発揮するのが,メタヒューリ
スティクスアルゴリズム wcsp です.max() 関数を用いて以下のように記
述します.V10 からは max() 関数が線形関数に特化して高速化されており,
実用的な速度で良質の実行可能解を得ることができます.

------------------------------------------------------------------
Set J;
Set I;
Element i(set=I),j(set=J);
Parameter A(index=(i,j));
IntegerVariable x(index=i,type=binary);
Expression y(index=j); // max 関数の結果を格納する
y[j] = max(A[i,j]*x[i],i); // y の定義
sum(x[i],i) >= 10;
Objective obj(type=minimize);
obj = sum(y[j],j);
options.method = "wcsp";
options.maxtim = 10;
solve();
------------------------------------------------------------------

..と言いたいところなのですが,実はこのモデル記述では全く良い解が出
ません.あるデータのサンプルについて我々の実験で得られた厳密解は
"286" なのですが,解の更新が "391" というあたりで止まってしまい,最
適解に遠く及びません.実はこれは近似解法 wcsp の性質に特化した現象
なのです.近似解法は近傍の情報を用いて解を逐次更新しますが,y[j] の
内容である max() 関数は変数の微小な変化に対して比較的「鈍い」という
性質を持っていることから,この記述のままでは解の更新が止まってしま
うのが直接の原因です.このような場合には良い解に至る手掛りを与えて
あげるのがコツ.この場合には具体的な手立ては次の二つがあります.

  i)  施設数の制約を sum(x[i],i) == 10; とする.
  ii) max を sum に置き換えた関数を
          y0[j] = sum(A[i,j]*x[i],i);
      と定義して,
          Objective obj(type=minimize);
          obj = 10000*sum(y[j],j) + sum(y0[j],j);
      のように,目的関数の微小項として加える.

いずれもどの方向が良い解なのかという情報量を近似解法に与える効果が
あり,導入すると,同一のデータにて 0.2 秒程度で最適解を出力すること
ができました.実務的な問題では複雑な制約が多数存在し,目的関数の項
の種類も多岐にわたるので,あまり心配されることはありませんが,近傍
探索の性質として,良い解に関する局所的な情報を与えることが速い収束
のコツであるというノウハウは様々な局面において役立ちます.

さて,上述の施設配置問題の設定を若干変更して,顧客は設置された施設
の最短のものから,何らかのサービスを受ければよい,とすると上述の
max を min に変更したモデルが得られます.これは min/min 問題と呼ば
れ,混合線形計画法としての記述がかなり困難な部類に属します.しかし,
近似解法 wcsp であれば,以下のように簡潔に記述することができ,また
高速に実行可能解を得ることができます.

------------------------------------------------------------------
Set J;
Set I;
Element i(set=I),j(set=J);
Parameter A(index=(i,j));
IntegerVariable x(index=i,type=binary);
Expression y(index=j);
Parameter M = 1000;
y[j] = min(A[i,j]*x[i] + (1-x[i])*M,i);
                  // 選択しない施設は M の距離を持つ
sum(x[i],i) <= 4; // 施設の数は 4 つ以下とする
Objective obj(type=minimize);
obj = sum(y[j],j);
options.method = "wcsp";
options.maxtim = 10;
solve();
------------------------------------------------------------------

この設定では,上述した近似解法の解の更新が止まってしまう,という現
象は起きません.おそらくは,施設の数が 4 と少なく,施設数の制約が常
に効いた状態になることから,近似解法への探索のヒントが大きいためと
考えております.

ここでは施設配置問題として紹介しましたが,「顧客」を「設備」,「施
設」を「テストパターン」と考えれば,同様の定式化で設備をテストする
テストパターンの設計問題であると捉えることができる,など様々な応用
が存在し得ます.

                                                 (田辺 隆人)

******************************************************************
■ <  tips  >  SIMPLE よくある間違い(第 5 回)
******************************************************************

このコーナーでは,SIMPLE の記述に関して,お客様が陥りやすい間違い
を少しずつですが紹介していきます.

前回は添字を固定するときの間違いを簡単な例を通して紹介しました.今
回は SIMPLE の添字の解釈について,もう少し踏み込んで見ていきます.

さて,いつも通り唐突に問題です.以下の (1)~(6) の中で,文法的に正
しい(実行時エラー(SIMPLE 67)を出さない)文は何個あるでしょうか.

------------------------------------------------------------------
Set A; Element a(set=A);
Set B; Element b(set=B);
Set C; Element c(set=C);
Set D; Element d(set=D);

Parameter p(index=(a,b,c,d));

p[a,2,c,d] = 0;     // --- (1)
p[1,2,c,d] = 0;     // --- (2)
p[1,b,3,4] = 0;     // --- (3)
p["1,2",3,d] = 0;   // --- (4)
p["1,2,3",d] = 0;   // --- (5)
p["1,2,3,4"] = 0;   // --- (6)
------------------------------------------------------------------

NUOPT をお持ちの方は一つずつ試してみると(他はコメントアウトして)
わかりますが,文法的に正しい(実行時エラーを出さない)文は (1),(3),
(5),(6) の 4 個です.(2),(4) は正しく解釈されません.

実は SIMPLE では,[] の中を "," で区切ったときの各要素について,最
初の 2 つの要素の中に Element 型か Parameter 型の要素がないと添字
を正しく解釈できないのです.ただし,"" で括られた部分は 1 つの要素
とみなします.

(1) については左から最初の要素,(3),(5) については 2 番目の要素が
Element 型ですので (1),(3),(5) は正しく解釈することができます. 

(2) について左から二つの要素は 1 と 2,(4) については "1,2" と 3
で共に組み込み型ですから (2),(4) は正しく解釈されません.

ただし,(6) のように要素が一つの場合は,char* でも正しく解釈されま
す.もちろん "" で括られた部分を "," で区切ったときの要素の数が添
字の数(この場合は 4 個)になっている必要がありますが.

ここまで来れば,前回挙げた「Element 以外(正確には Element と
Parameter 以外)は全部 "" で括る」,「全て Element 型を用いて条件
式で添字を固定する」という回避策が妥当なものだということが分かるか
と思います.

「集合,添え字は慣れないと難しい」とよく言われますが,これでもう集
合,添字周りでエラーが出た時も怖くありませんね.

集合,添字,恐るるに足らず!

                                                 (村山 昇)

==================================================================
※ このメールは,展示会・セミナー等で名刺交換をされた方,過去に
    NUOPT に関するお問い合わせを頂いたことのある方,および本メール
   マガジンの配信を希望された方にお送りしています.
※ バックナンバーはこちらから御覧頂けます.
     http://www.msi.co.jp/nuopt/mailmagazine/index.html
※ 本メールマガジンは等幅フォントでお読みになることを推奨します.
※ 今後このメールマガジンが不要な方は,誠にお手数ですが,「メール
   マガジン配信停止」という件名のメールを nuopt-magazine@ml.msi.co.jp
   にお送りください.

発行:株式会社 数理システム << NUOPT >> 担当
        東京都新宿区新宿二丁目 4 番 3 号 フォーシーズンビル 10 階
==================================================================