http://research.nii.ac.jp/~uno/approx.htm
宇野先生のページに載っている通りの解法があります。
目指しているのは、厳密解を目標にしつつ、必要なら途中途中で解を得るような方法です。
ナーススケジューリング問題としては、最近シミュレーテッドアニーリングで成果が出ているので、
こちらについても見てみたいのですが、残念ながら上記の要件を満たすことは難しいです。
メタヒューリスティクスでは、高速に近似解を得ることができますが、CPUパワーをそちらに摂られてしまうと、厳密解パワーに廻せなくなってしまいます。極初期に、少しだけ使うのは、意味があると思いますが、厳密解の50%や20%程度の劣化を意識したところでは、かなり難しいと感じています。
現在は、途中途中でMaxSATソルバを動かしていますが、このままですと、かなり性能が悪く、近似解でも良い解が中々出てきません。具体的には、厳密解近くまで来ないと中々良い解になりません。INRC2の8WEEKSが厳密解近くの解を出すまでには、丸一日程度かかるのですが、それらしい近似解の出力にもあまり変わらない時間であり、今のままだと全く実用的ではありません。
（実は、問題領域をどこにするかで、得意なソルバの種類は違ってきます。今問題にしているのは、INRC2の8WEEKS程度でのお話です。この辺の話も後で。かなり色々な事が分かってきました。）
そこで、上記主旨を踏まえて、MAXSATソルバを新たに設計することにしました。新しい挑戦です。
2019年2月23日土曜日
2019年2月20日水曜日
久々にメンテ
VeritakSVという公開していないverilogシミュレータがあるのですが、Windows10で突然動かなくなったという報告がいくつかあり久々にメンテしました。その際、VisualC++2015に環境を移したのですが、コンパイルが通らなかった記述が数十箇所あり、C++でも、いまだにそういう状態なんだ、
という思いをしました。2012年位まで書いていたのですが、クラスの実装をやり始めたところで、その時点で、C++ソースは20万行を越えていて、その後断念しました。というか、SystemVerilogの検証言語部の実装を検討していたときにSAT技術について学んで、妻の勤務表に使えないかなと思って取り組ん結果が、そちらが本業になってしまいました。
一部のコアユーザにのみ提供していて、未だに使っている人があるようです。
https://bellard.org/tcc/ というTinyCコンパイラをハックしたコード生成を使っているので、とても高速です。(VMコードの10倍速い) 今だったら良いバックエンド(LLVMとか幾つかある）ので、もう少しましな方法を採るでしょう。
という思いをしました。2012年位まで書いていたのですが、クラスの実装をやり始めたところで、その時点で、C++ソースは20万行を越えていて、その後断念しました。というか、SystemVerilogの検証言語部の実装を検討していたときにSAT技術について学んで、妻の勤務表に使えないかなと思って取り組ん結果が、そちらが本業になってしまいました。
一部のコアユーザにのみ提供していて、未だに使っている人があるようです。
https://bellard.org/tcc/ というTinyCコンパイラをハックしたコード生成を使っているので、とても高速です。(VMコードの10倍速い) 今だったら良いバックエンド(LLVMとか幾つかある）ので、もう少しましな方法を採るでしょう。
2019年2月11日月曜日
ナーススケジューリングで厳密解は得られるか？
現在の技術と計算機資源で、どんな問題でも厳密解が得られるようになったか？という問題についてです。
勿論、ナーススケジューリングは、NP困難な問題であるので、規模が大きくなれば自ずと答えは否です。しかしながら、通常遭遇する一般的な問題についての観測と感想です。
現在開発中のソルバは、INRC-IIのほぼ全ての問題について既存のKnownBest記録を塗り替えることができますが、そのうち厳密解が得られたのはほんの僅かでした。（一週間廻しても証明できませんでした。）従って、この結果をもってしても、通常問題で厳密解を得ることは難しそうだということが言えます。 特に、INRC-IIの問題は、行制約のほとんどがソフト制約であり、ソルバ的には、難しい問題です。一方、SchedulingBenchmarkサイト問題は、行制約のソフト制約はありません。その結果、長大規模な問題を除いて、厳密解が得られています。
以上の、観測から、ナーススケジューリングの現状の技術では、世界最高性能のソルバをもってしても「厳密解が得られない問題もある」、ということをご理解頂きたいと思います。一方で、大きな規模でも厳密解が得られる場面もあります。この差についての考察は、後日に。
これまでは、厳密解を得ることに挑んできましたが、実用的には、近似解でも早く結果が欲しい訳で、その部分の改善が残っています。こちらは、根底から設計する必要はありません。厳密解を得るソルバに手を加えていけばよいです。しかしながら、未だアイデア段階であり、これからFeasibilityStudy・設計・実装となります。
勿論、ナーススケジューリングは、NP困難な問題であるので、規模が大きくなれば自ずと答えは否です。しかしながら、通常遭遇する一般的な問題についての観測と感想です。
現在開発中のソルバは、INRC-IIのほぼ全ての問題について既存のKnownBest記録を塗り替えることができますが、そのうち厳密解が得られたのはほんの僅かでした。（一週間廻しても証明できませんでした。）従って、この結果をもってしても、通常問題で厳密解を得ることは難しそうだということが言えます。 特に、INRC-IIの問題は、行制約のほとんどがソフト制約であり、ソルバ的には、難しい問題です。一方、SchedulingBenchmarkサイト問題は、行制約のソフト制約はありません。その結果、長大規模な問題を除いて、厳密解が得られています。
以上の、観測から、ナーススケジューリングの現状の技術では、世界最高性能のソルバをもってしても「厳密解が得られない問題もある」、ということをご理解頂きたいと思います。一方で、大きな規模でも厳密解が得られる場面もあります。この差についての考察は、後日に。
これまでは、厳密解を得ることに挑んできましたが、実用的には、近似解でも早く結果が欲しい訳で、その部分の改善が残っています。こちらは、根底から設計する必要はありません。厳密解を得るソルバに手を加えていけばよいです。しかしながら、未だアイデア段階であり、これからFeasibilityStudy・設計・実装となります。
2019年2月10日日曜日
導入について
導入を検討されているお客様向けに資料を作成しました。
きっかけは、障碍者施設・児童擁護施設向けのご相談があったからです。
児童養護施設の勤務実態は複雑多岐にわかれており、厚労省の指導では大舎制の否定、小規模グループホーム化を推奨しており、その分職員の勤務が多岐に分かれて、手作業による勤務表の作成は困難を極めています。
とのことで、大変にご苦労されているようです。最近の児童虐待のニュースを耳にするにつけ、これら施設の重要性が高まってきていると思います。働く現場の方々に少しでもお役に立てたらと思います。
スケジュールナースでは、勤務表作成・組合せ最適化に関するコンサルティングも行っております。お気軽にお問い合わせください。
きっかけは、障碍者施設・児童擁護施設向けのご相談があったからです。
児童養護施設の勤務実態は複雑多岐にわかれており、厚労省の指導では大舎制の否定、小規模グループホーム化を推奨しており、その分職員の勤務が多岐に分かれて、手作業による勤務表の作成は困難を極めています。
とのことで、大変にご苦労されているようです。最近の児童虐待のニュースを耳にするにつけ、これら施設の重要性が高まってきていると思います。働く現場の方々に少しでもお役に立てたらと思います。
スケジュールナースでは、勤務表作成・組合せ最適化に関するコンサルティングも行っております。お気軽にお問い合わせください。
2019年1月31日木曜日
スティーブジョブズは何を遺したのか
の本に登場する最初の人物は、私の元の上司の上司です。この本を読むと、ジョブズが広瀬さんと出会ったときには、未だカリスマ性がなかったことが分かります。
広瀬さんとは、IBMやAPPLEに一緒に行きました。（日本のFDDが世界を席巻していた時代です。当時、広瀬さんは、技術部長、私はLSI設計を含むエレキ設計者でした。）
特に、USには、私の設計ミスとも言えるトラブルが原因で数ヶ月間、マイアミに滞在しました。そのとき、フォートローダーデール空港でパスポートやTCが入った鞄を盗まれてしまいました。女の子が不自然に近づいてくるのが分かったのですが、多分そのときです。ジェットラグの隙をつかれたのだと思いますが、間抜けなのは私です。
若かりし私が英語が出来なかったこともあり、広瀬さんが現地法人と折衝してくれて帰国までの算段をつけてくれました。ポリスと話したりTCの再発行で銀行に行ったり大変でしたが、ロスの領事館で臨時のパスーポートをもらい無事に帰国できたのは、広瀬さんのおかげです。
色々な上司に仕えてきましたが、今にして思うと、私の人生の中で一番強烈に印象に残るのは広瀬さんです。上記エピソードも関係しますが、それだけではなく、絶対絶命の状況の中、数十人のUS顧客を前にして英語で一歩も引かずに論陣を張るのを目にしたことがありました。その後、メディアに載るような業界の有名人に何人かお会いしましたが、あの時の広瀬さんほどカリスマ性を感じたことはありませんでした。 今から30年も前のお話でした。
広瀬さんとは、IBMやAPPLEに一緒に行きました。（日本のFDDが世界を席巻していた時代です。当時、広瀬さんは、技術部長、私はLSI設計を含むエレキ設計者でした。）
特に、USには、私の設計ミスとも言えるトラブルが原因で数ヶ月間、マイアミに滞在しました。そのとき、フォートローダーデール空港でパスポートやTCが入った鞄を盗まれてしまいました。女の子が不自然に近づいてくるのが分かったのですが、多分そのときです。ジェットラグの隙をつかれたのだと思いますが、間抜けなのは私です。
若かりし私が英語が出来なかったこともあり、広瀬さんが現地法人と折衝してくれて帰国までの算段をつけてくれました。ポリスと話したりTCの再発行で銀行に行ったり大変でしたが、ロスの領事館で臨時のパスーポートをもらい無事に帰国できたのは、広瀬さんのおかげです。
色々な上司に仕えてきましたが、今にして思うと、私の人生の中で一番強烈に印象に残るのは広瀬さんです。上記エピソードも関係しますが、それだけではなく、絶対絶命の状況の中、数十人のUS顧客を前にして英語で一歩も引かずに論陣を張るのを目にしたことがありました。その後、メディアに載るような業界の有名人に何人かお会いしましたが、あの時の広瀬さんほどカリスマ性を感じたことはありませんでした。 今から30年も前のお話でした。
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/
登録:
投稿 (Atom)