の本に登場する最初の人物は、私の元の上司の上司です。この本を読むと、ジョブズが広瀬さんと出会ったときには、未だカリスマ性がなかったことが分かります。
広瀬さんとは、IBMやAPPLEに一緒に行きました。（日本のFDDが世界を席巻していた時代です。当時、広瀬さんは、技術部長、私はLSI設計を含むエレキ設計者でした。）
特に、USには、私の設計ミスとも言えるトラブルが原因で数ヶ月間、マイアミに滞在しました。そのとき、フォートローダーデール空港でパスポートやTCが入った鞄を盗まれてしまいました。女の子が不自然に近づいてくるのが分かったのですが、多分そのときです。ジェットラグの隙をつかれたのだと思いますが、間抜けなのは私です。
若かりし私が英語が出来なかったこともあり、広瀬さんが現地法人と折衝してくれて帰国までの算段をつけてくれました。ポリスと話したりTCの再発行で銀行に行ったり大変でしたが、ロスの領事館で臨時のパスーポートをもらい無事に帰国できたのは、広瀬さんのおかげです。
色々な上司に仕えてきましたが、今にして思うと、私の人生の中で一番強烈に印象に残るのは広瀬さんです。上記エピソードも関係しますが、それだけではなく、絶対絶命の状況の中、数十人のUS顧客を前にして英語で一歩も引かずに論陣を張るのを目にしたことがありました。その後、メディアに載るような業界の有名人に何人かお会いしましたが、あの時の広瀬さんほどカリスマ性を感じたことはありませんでした。 今から30年も前のお話でした。
2019年1月31日木曜日
2019年1月19日土曜日
LKIT-16
世界で初めて16bit CPUを量産したのは日本のパナファコムという富士通と松下合弁の会社で、私が最初に入社した会社です。合弁とはいっても富士通色の濃い会社でして、同僚は富士通へ勉強に行っていたりしました。
上司の上司で当時、開発企画の部長さんは、いつも煙草をふかしている人で、デスクに堆く積まれた書類の山が記憶に記憶に残っています。およそ50cmはあろうかという高さでしたが、あるとき地震が来ても、倒壊せず、してやったりピースサインをしていました。今思うと、古きよき時代だったですね。
そのCPUのアーキテクチャの論文が見つかりました。（今思うとパナファコムは、自社オリジナルCPU用のBASICやらEPOCALCという簡易言語まで作ってしまう凄い会社だったと思いますが（C言語以前で、LEXやらYACCもなかった時代です）、優秀な人が多かったように思います。女子のソフト屋さんに東女出身が多かったような気が。）
https://ipsj.ixsq.nii.ac.jp/ej/index.php?active_action=repository_view_main_item_detail&page_id=13&block_id=8&item_id=25321&item_no=1
都村さんが、アーキテクチャ設計者だったとはついぞ知りませんでした。しかも、ワイアードロジックと記載されています。当時の主流はマイクロプログラムだったと思うのですが、HDLや論理合成技術のない時代に大変な事だったと思います。（確かレジスタ間演算が300nsだった記憶があります。今の時代からすると1000倍位遅いです。）
当時、私は、周辺機器FDDの評価を担当していました。その後アルプス電気に転職してFDDを設計しました。
その後、私は独立し日本で初めてVerilogHDLシミュレータを開発設計することになるのですが、こうして手書きのアーキテクチャを見ると感慨深いものがあります。
上司の上司で当時、開発企画の部長さんは、いつも煙草をふかしている人で、デスクに堆く積まれた書類の山が記憶に記憶に残っています。およそ50cmはあろうかという高さでしたが、あるとき地震が来ても、倒壊せず、してやったりピースサインをしていました。今思うと、古きよき時代だったですね。
そのCPUのアーキテクチャの論文が見つかりました。（今思うとパナファコムは、自社オリジナルCPU用のBASICやらEPOCALCという簡易言語まで作ってしまう凄い会社だったと思いますが（C言語以前で、LEXやらYACCもなかった時代です）、優秀な人が多かったように思います。女子のソフト屋さんに東女出身が多かったような気が。）
https://ipsj.ixsq.nii.ac.jp/ej/index.php?active_action=repository_view_main_item_detail&page_id=13&block_id=8&item_id=25321&item_no=1
都村さんが、アーキテクチャ設計者だったとはついぞ知りませんでした。しかも、ワイアードロジックと記載されています。当時の主流はマイクロプログラムだったと思うのですが、HDLや論理合成技術のない時代に大変な事だったと思います。（確かレジスタ間演算が300nsだった記憶があります。今の時代からすると1000倍位遅いです。）
当時、私は、周辺機器FDDの評価を担当していました。その後アルプス電気に転職してFDDを設計しました。
その後、私は独立し日本で初めてVerilogHDLシミュレータを開発設計することになるのですが、こうして手書きのアーキテクチャを見ると感慨深いものがあります。
2019年1月15日火曜日
ビタビアルゴリズム -情報通信の深淵
http://www.it.mgmt.waseda.ac.jp/hirawork/2010/2010_13.pdf
より引用です。
Viterbi 算法は Dijkstra のアルゴリズムの一つの変形であり，その出版は Viterbi の論文より早く，コンピュータサイエンスでは良く知られていた，と指摘された．それは，Bellman の DP（Dynamic Pro-gramming）そのものであることは Viterbi 自身も別の論文で認めてはいる．
http://www.mnc.toho-u.ac.jp/v-lab/yobology/viterbi/viterbi.htm
私自身は、HDDのチャネルPRML復号でその存在を知り、その後、符号理論を勉強したとき偉い先生であることを知りました。それ以前に、会社員時代、会社内でビタビ教授のCDMA関連の講演を聞く機会がありました。そのときは、全く無知だったので内容はよく覚えていません。しかし、同時通訳者の方(2人組で交代しながら）が凄かったのは覚えています。
で、組合せ最適化の教科書を見ると動的計画法の話は載っています。どこかで見たアルゴリズムに似ているな、と思ったのですが、やはりそういうことだったのですね。私が関わってきた全く違う分野で、それら技術の底流にあったのは、実は動的計画法だった、という落ちでした。
シャノン限界に近い符号の再発見により、ビタビ復号は最新の規格で採用されることはないと思います。それでも上記のように幅広い応用を持つ動的計画法の考え方というのは、大学教育でもっと取りあえげてもよいと思います。
隠れマルコフについてはこちら
https://mieruca-ai.com/ai/markov_model_hmm/
より引用です。
Viterbi 算法は Dijkstra のアルゴリズムの一つの変形であり，その出版は Viterbi の論文より早く，コンピュータサイエンスでは良く知られていた，と指摘された．それは，Bellman の DP（Dynamic Pro-gramming）そのものであることは Viterbi 自身も別の論文で認めてはいる．
http://www.mnc.toho-u.ac.jp/v-lab/yobology/viterbi/viterbi.htm
私自身は、HDDのチャネルPRML復号でその存在を知り、その後、符号理論を勉強したとき偉い先生であることを知りました。それ以前に、会社員時代、会社内でビタビ教授のCDMA関連の講演を聞く機会がありました。そのときは、全く無知だったので内容はよく覚えていません。しかし、同時通訳者の方(2人組で交代しながら）が凄かったのは覚えています。
で、組合せ最適化の教科書を見ると動的計画法の話は載っています。どこかで見たアルゴリズムに似ているな、と思ったのですが、やはりそういうことだったのですね。私が関わってきた全く違う分野で、それら技術の底流にあったのは、実は動的計画法だった、という落ちでした。
シャノン限界に近い符号の再発見により、ビタビ復号は最新の規格で採用されることはないと思います。それでも上記のように幅広い応用を持つ動的計画法の考え方というのは、大学教育でもっと取りあえげてもよいと思います。
隠れマルコフについてはこちら
https://mieruca-ai.com/ai/markov_model_hmm/
2019年1月13日日曜日
INRC-II 8weeks Data
This article deals with the nurse scheduling problem as described in the context of the international
competition INRC–II.The experimental tests focus on a benchmark of twenty instances published during the INRC–II.The instances describe the constraints for the schedule of 30 to 120 nurses over 4 and 8 weeks horizon. Table below shows the result obtained by my developping solver.
competition INRC–II.The experimental tests focus on a benchmark of twenty instances published during the INRC–II.The instances describe the constraints for the schedule of 30 to 120 nurses over 4 and 8 weeks horizon. Table below shows the result obtained by my developping solver.
| 8WEEKS | Known Best Result | New Result | ||||
| LB | UB | GAP(%) | LB | UB | GAP(%) | |
| n030w8 1 2-7-0-9-3-6-0-6 | 1920 | 2070 | 7.2 | 1994 | 2025 | 1.5 |
| n030w8 1 6-7-5-3-5-6-2-9 | 1620 | 1735 | 6.6 | 1710 | 1735 | 1.4 |
| n035w8 0 6-2-9-8-7-7-9-8 | 2330 | 2555 | 8.8 | 2408 | 2495 | 3.5 |
| n035w8 1 0-8-1-6-1-7-2-0 | 2180 | 2305 | 5.4 | 2153 | 2290 | 6.0 |
| n040w8 0 0-6-8-9-2-6-6-4 | 2340 | 2620 | 10.7 | 2464 | 2600 | 5.2 |
| n040w8 2 5-0-4-8-7-1-7-2 | 2205 | 2420 | 8.9 | 2285 | 2345 | 2.6 |
| n050w8 1 1-7-8-5-7-4-1-8 | 4625 | 4900 | 5.6 | 4778 | 4865 | 1.8 |
| n050w8 1 9-7-5-3-8-8-3-1 | 4530 | 4925 | 8.0 | 4744 | 4870 | 2.6 |
| n060w8 0 6-2-9-9-0-8-1-3 | 1970 | 2345 | 16.0 | 2099 | 2280 | 7.9 |
| n060w8 2 1-0-3-4-0-3-9-1 | 2260 | 2590 | 12.7 | 2394 | 2485 | 3.7 |
| n070w8 0 3-3-9-2-3-7-5-2 | 4400 | 4595 | 4.2 | 4475 | 4575 | 2.2 |
| n070w8 0 9-3-0-7-2-1-1-0 | 4540 | 4760 | 4.6 | 4637 | 4755 | 2.5 |
| n080w8 1 4-4-9-9-3-6-0-5 | 3775 | 4180 | 9.7 | 3942 | 4155 | 5.1 |
| n080w8 2 0-4-0-9-1-9-6-2 | 4125 | 4450 | 7.3 | 4287 | 4385 | 2.2 |
| n100w8 0 0-1-7-8-9-1-5-4 | 2005 | 2125 | 5.6 | 2026 | DUT | |
| n100w8 1 2-4-7-9-3-9-2-8 | 2125 | 2210 | 3.8 | 2153 | 2185 | 1.5 |
| n110w8 0 2-1-1-7-2-6-4-7 | 3870 | 4010 | 3.5 | 3990 | 3990 | 0.0 |
| n110w8 0 3-2-4-9-4-1-3-7 | 3375 | 3560 | 5.2 | 3450 | 3450 | 0.0 |
| n120w8 0 0-9-9-4-5-1-0-3 | 2295 | 2600 | 11.7 | 2485 | 2495 | 0.4 |
| n120w8 1 7-2-6-4-5-2-0-2 | 2535 | 3095 | 18.1 | 2912 | 2930 | 0.6 |
2019年1月2日水曜日
INRC-IIは、超難問
スタッフ数5人のインスタンスでさえ、CPLEXで5分近くかかりました。
n005w4_1_6-2-9-1 LB=UB=1520
Antoine Legrainさんの論文では、厳密解が求まるのは、21人以下の4Weeksのみのようですが、私のところでは、個別に厳密解が得られる場面もありそうです。
４Weeksの全てのインスタンスにおいて、未踏の解(新しい解)を発見しました。（解は、Validatorで確認済みです。） Antoine Legrainさんのデータは、24hRun、私のところは、数時間のRunです。
全てのインスタンスにおいて、優れた結果となっています。
LBは、これ以上良い値はないが、値が存在する保証ないという性質を持ちます。重みは、１０,１５，２０，３０，４５，６０，９０ なので、そのGCDは、５です。例えば、LB=1338のときにありえる整数解の最小値は、GCD値を利用すると1340ということになります。この場合、UB=1340を発見した時点で探索終了とすることができます。極小さいインスタンスを覗いて、こんな風に上手くいく例はあまりありません。LBーUB間には、GAPあるのが普通であり、この値が大きいとき、これ以上解がないという証明をするためには、より広大な探索空間をスキャンせざるを得ず、それだけ、UBの最小値を得てから長い時間を要するのが普通です。
UBは、実際にValidatorが確認した値です。GAP＝(UB-LB)/LB として算出しています。
GAP=0 となったとき、UB=LBですから、これ以上良い値はありえないという証明になります。つまり厳密解が求まったことを示しています。黄色部がGAP=0となっています。GAP値で比較してみると性能差が分かります。
GAPが1%未満というインスタンスが結構あるので、時間をかければ厳密解が求まるインスタンスもありそうです。最新結果はhttps://english.nurse-scheduling-software.com/benchmarks/benchmarks.html
Santosさんとの結果を比較しても優秀な結果となっています。
https://www.gerad.ca/colloques/ColumnGeneration2016/PDF/HaroldoSantos.pdf
António Ramadasさんとの比較でも同様です。
https://github.com/antonio-ramadas/nurse-rostering-solution/blob/master/A%20GRASP%20Approach%20using%20a%20Constructive%20Heuristic%20Approach%20to%20the%20Nurse%20Scheduling%20Problem.pdf
その他INRC-II関係の論文です。ttp://www.patatconference.org/patat2016/files/proceedings/paper_56.pdf
http://www.patatconference.org/patat2016/files/proceedings/paper_21.pdf
http://patatconference.org/patat2018/files/proceedings/paper46.pdf
https://lib.ugent.be/fulltxt/RUG01/002/273/956/RUG01-002273956_2016_0001_AC.pdf
http://www.scs-europe.net/dlib/2016/ecms2016acceptedpapers/0502-simo_ECMS_0113.pdf
http://www.cs.nott.ac.uk/~pszjds/research/files/dls_mod2017.pdf
http://ds-o.org/images/FAIM_papers/Kumar_V2.pdf
ということで、サーベイした中では、圧倒的な結果となりました。
＊Sara Ceschiaさんの論文で一部私のより良い値が出ていますが、恐らく誤りです。その理由は、私のLB値よりも小さいこと、なおかつValidatorの値も論文中の値と一致していないこと の2点によります。
このインスタンスの特徴としては、SchedulingBenchmarkサイトで皆無だった横方向のソフト制約が多いことが挙げられます。ただし、日本的な制約ではなく、RealProjectからは逸脱している感が否めません。それでも、横方向のソフト制約がこれでもか、という位入っているので、SchedulingBenchmarkサイトよりは、現実的なベンチマークになっているような気もします。
シフト数は、４ですが、少ない代わりにスキルという概念が導入され、シフト数で表現すると最大16シフト位には相当します。このスキルの実装がまた難しく、苦労しました。（SC2では、スキルをタスクとして扱う予定です。）
もう一つの特徴は、混沌としたソフト制約の海の中に解が存在する、とでもいいましょうか、とにかく難しいインスタンスになっています。
n005w4_1_6-2-9-1 LB=UB=1520
Antoine Legrainさんの論文では、厳密解が求まるのは、21人以下の4Weeksのみのようですが、私のところでは、個別に厳密解が得られる場面もありそうです。
４Weeksの全てのインスタンスにおいて、未踏の解(新しい解)を発見しました。（解は、Validatorで確認済みです。） Antoine Legrainさんのデータは、24hRun、私のところは、数時間のRunです。
全てのインスタンスにおいて、優れた結果となっています。
LBは、これ以上良い値はないが、値が存在する保証ないという性質を持ちます。重みは、１０,１５，２０，３０，４５，６０，９０ なので、そのGCDは、５です。例えば、LB=1338のときにありえる整数解の最小値は、GCD値を利用すると1340ということになります。この場合、UB=1340を発見した時点で探索終了とすることができます。極小さいインスタンスを覗いて、こんな風に上手くいく例はあまりありません。LBーUB間には、GAPあるのが普通であり、この値が大きいとき、これ以上解がないという証明をするためには、より広大な探索空間をスキャンせざるを得ず、それだけ、UBの最小値を得てから長い時間を要するのが普通です。
UBは、実際にValidatorが確認した値です。GAP＝(UB-LB)/LB として算出しています。
GAP=0 となったとき、UB=LBですから、これ以上良い値はありえないという証明になります。つまり厳密解が求まったことを示しています。黄色部がGAP=0となっています。GAP値で比較してみると性能差が分かります。
GAPが1%未満というインスタンスが結構あるので、時間をかければ厳密解が求まるインスタンスもありそうです。最新結果はhttps://english.nurse-scheduling-software.com/benchmarks/benchmarks.html
| Known Best Result | New Result | |||||
| LB | UB | GAP(%) | LB | UB | GAP(%) | |
| n030w4 1 6-2-9-1 | 1615 | 1685 | 4.2 | 1660 | 1675 | 0.9 |
| n030w4 1 6-7-5-3 | 1740 | 1840 | 5.4 | 1820 | #VALUE! | |
| n035w4 0 1-7-1-8 | 1250 | 1415 | 11.7 | 1338 | 1370 | 2.3 |
| n035w4 2 8-8-7-5 | 1045 | 1145 | 8.7 | 1076 | 1085 | 0.8 |
| n040w4 0 2-0-6-1 | 1335 | 1640 | 18.6 | 1625 | 100.0 | |
| n040w4 2 6-1-0-6 | 1570 | 1865 | 15.8 | 1742 | 1765 | 1.3 |
| n050w4 0 0-4-8-7 | 1195 | 1445 | 17.3 | 1296 | 1325 | 2.2 |
| n050w4 0 7-2-7-2 | 1200 | 1405 | 14.6 | 1303 | 1335 | 2.4 |
| n060w4 1 6-1-1-5 | 2380 | 2465 | 3.4 | 2460 | 100.0 | |
| n060w4 1 9-6-3-8 | 2615 | 2730 | 4.2 | 2665 | 2675 | 0.4 |
| n070w4 0 3-6-5-1 | 2280 | 2430 | 6.2 | 2395 | 100.0 | |
| n070w4 0 4-9-6-7 | 1990 | 2125 | 6.4 | 2105 | 2120 | 0.7 |
| n080w4 2 4-3-3-3 | 3140 | 3320 | 5.4 | 3292 | 3300 | 0.2 |
| n080w4 2 6-0-4-8 | 3045 | 3240 | 6.0 | 3178 | 3190 | 0.4 |
| n100w4 0 1-1-0-8 | 1055 | 1230 | 14.2 | 1168 | 1175 | 0.6 |
| n100w4 2 0-6-4-6 | 1470 | 1855 | 20.8 | 1785 | 100.0 | |
| n110w4 0 1-4-2-8 | 2210 | 2390 | 7.5 | 2322 | 2330 | 0.3 |
| n110w4 0 1-9-3-5 | 2255 | 2525 | 10.7 | 2455 | 2455 | 0.0 |
| n120w4 1 4-6-2-6 | 1790 | 2165 | 17.3 | 2012 | 2020 | 0.4 |
| n120w4 1 5-6-9-8 | 1820 | 2220 | 18.0 | 2050 | 2050 | 0.0 |
Santosさんとの結果を比較しても優秀な結果となっています。
https://www.gerad.ca/colloques/ColumnGeneration2016/PDF/HaroldoSantos.pdf
António Ramadasさんとの比較でも同様です。
https://github.com/antonio-ramadas/nurse-rostering-solution/blob/master/A%20GRASP%20Approach%20using%20a%20Constructive%20Heuristic%20Approach%20to%20the%20Nurse%20Scheduling%20Problem.pdf
その他INRC-II関係の論文です。ttp://www.patatconference.org/patat2016/files/proceedings/paper_56.pdf
http://www.patatconference.org/patat2016/files/proceedings/paper_21.pdf
http://patatconference.org/patat2018/files/proceedings/paper46.pdf
https://lib.ugent.be/fulltxt/RUG01/002/273/956/RUG01-002273956_2016_0001_AC.pdf
http://www.scs-europe.net/dlib/2016/ecms2016acceptedpapers/0502-simo_ECMS_0113.pdf
http://www.cs.nott.ac.uk/~pszjds/research/files/dls_mod2017.pdf
http://ds-o.org/images/FAIM_papers/Kumar_V2.pdf
ということで、サーベイした中では、圧倒的な結果となりました。
＊Sara Ceschiaさんの論文で一部私のより良い値が出ていますが、恐らく誤りです。その理由は、私のLB値よりも小さいこと、なおかつValidatorの値も論文中の値と一致していないこと の2点によります。
このインスタンスの特徴としては、SchedulingBenchmarkサイトで皆無だった横方向のソフト制約が多いことが挙げられます。ただし、日本的な制約ではなく、RealProjectからは逸脱している感が否めません。それでも、横方向のソフト制約がこれでもか、という位入っているので、SchedulingBenchmarkサイトよりは、現実的なベンチマークになっているような気もします。
シフト数は、４ですが、少ない代わりにスキルという概念が導入され、シフト数で表現すると最大16シフト位には相当します。このスキルの実装がまた難しく、苦労しました。（SC2では、スキルをタスクとして扱う予定です。）
もう一つの特徴は、混沌としたソフト制約の海の中に解が存在する、とでもいいましょうか、とにかく難しいインスタンスになっています。
登録:
投稿 (Atom)