最適をめざさない最適化 ～ 勤務表作成にて ～ 久保 琢磨 （元総合研究大学院大学） ○宇野 毅明 （国立情報学研究所, 総合研究大学院大学） 2011年9月9日 OR学会中部支部シンポジウム 最適化活用の難しさ （たこつぼ） 応用の難しさ •よく、最適化の研究者から、実用化の難しさの話を聞きます 海洋大K先生： 「いろいろモデルしても現場でうまくいかないことがあるんだよ ね」 名古屋大学Y先生ら： 「それぞれの場面で制約が変わるので、解法の開発がその都 度場当たり的になってね」 成蹊大学 I 先生： モデルも解法もあるのに、なかなか現実に結びつかない．． ある種の解決 •やはり優秀な研究者は解決法を編み出すものです。 海洋大K先生： 著書、多数の書き物による現場、および類似する現場の人 へのノウハウの伝達、啓蒙 名古屋大学Y先生ら： 標準問題の制定と優秀な解法によるツールボックスの作成 成蹊大学 I 先生： 徹底したフィールドワークと、現場での実験による課題抽出 すばらしいの一言に尽きます。でも、なんでこんなにモデル化と 問題解決って、実用化が難しいんでしょう？ 精緻な最適化 • OR「研究」では、現実の問題を上手に数理的に表すのが目標 その一方で、「上手すぎる」のも問題 例えば、ナビゲーションシステムで、 ＋ 渋滞発生確率を元に、渋滞に遭う危険率を抑えた最短路 ＋ 信号でつっかえる確率を厳密に扱うモデル ＋ 寄り道したいところの中から1日で行けるところをなるべく多く 選び出して、全てを回るルートを自動で計算 ＋ 景色の良さ、運転しやすさ、店の多さなどを考慮した多目的 最適化での最短路 • たぶん、「そこまでしなくていいよ」 という気分にな ると思います。 最適化モデルの落とし穴 • モデル化を行うときには、必ず現実の問題とモデルの間に乖離 があることを忘れてはいけない ＋ どんなにモデルを細かくしても、「リアル」にはならない お節介になり、準備が大変になるだけ ＋ ある程度までうまくいったら、あとは「数理モデルであること」の 味を出すようにしないといけない 似顔絵が人間の毛穴まで描かないのと同じ。それよりも「イ ラストならではの良さ」を、デフォルメや強調などで出す • でも現実には、「リアル」を追い求めすぎている研究もある • そもそも物理や経済で言うところのモデルは 「システムを簡単 な原理で説明するもの」。複雑なものは範囲外 一般的な解決法 • 一般的な問題（混合整数計画、非線形計画）に対する高速解法 を作る （CPLEX、ニューオプト） • 選び抜かれた「基礎問題」に対して高速アルゴリズムを開発す る （茨木研） • スクリプト言語（python）、モデリング言語を使い、実装を容易に する （AMPLEなど） • 携帯やRFIDなどのデバイスと連携する • 現場に無理を言う • 前に解いたのと似た問題に取り組む （学術研究者？） 見方を変えて最適化を見てみよう • 最適化（モデル）は、システムを改善するための一手段。 最適化をすることが目的ではない － 車を運転して目的地に到着する、という作業の中で、 ナビが関わる部分はほんのわずか － ナビを導入することで、プラニングの手間が減り、運転時間 も短縮されるだろう。でも、ナビの改善による手間の削減は、 全体の作業の中で何パーセントなんだろう？ － ルートの精度を上げることより、入出力の便利さ（GPS、 音声案内）などのほうが、大きな効果を上げそうではある • ひょっとしたら、「うるさくないように、音声案内の数を制限して効 果的に案内するにはどうすればいいか」というような問題のほう が重要なのかもしれない 外から見た最適化 • 最適化の研究って、そもそも他分野から見ると － 連続最適化は、点列発生法とその解析 － 離散最適化は、近傍と凸性、あるいはボトムアップ的な集約 － 評価は、多項式性 • 正直、外から見ていたら、そんなことはどうでもいい • 科学として胸を張れるようになるには、もっとグローバルな視点 での大目標が必要 （自然科学の人は、宇宙の心理や生命の神秘、金回りの良さと いった大目標がある） • 自分の研究の基盤として、持っておくのも大事 応用での使えるものは • 最適化を他分野、産業で使うとき、最新研究は意外と役に立た ない。理由は先ほどの 凝りすぎ あと、そのモデル／解法を選ぶのが果たして本当に良いのか どうか、客観的に見てよく分からないという点もある。 • 正直むしろ、利用する立場からすれば、 モデルも解法も簡単なもので良い 20-30 年前の結果くらいがちょうどいい 簡単で扱いやすく、しかも手法の評価が確立されている • 応用分野の人たちと話をする（新しい問題を考える）ときには、 「難しく考えすぎず、論文にならない結果であるほど良い」 小規模ビジネスOR ～ 最適化を広く世の中に ～ 導入の話はなぜ必要か • なぜ、複雑なモデルの話を出したかというと、少しOR分野に閉 塞感が有ると思うので ☆ こういうときには、新しい視点の研究が必要 ☆ 新しい手法、新しい問題設定、新しい応用、原点に戻る、価 値基準の変更、他分野からの問題・技術・人の導入．．． • ここでも、新しい問題設定について、応用の市場規模やワーク ロード最適化の視点から議論したいと思います ORの問題（市場）規模 • zip則という、世の中の様々なものの分布を説明するものがある 例） 個人の収入、会社の従業員数、論文の共著者数・・ ・ • ORの問題にも、規模（もうけ）と件数の間にこんな感じのものが 有ると思います 古き良きOR： 製鉄、交通、施設配置・・・ 問題規模 （もうけ） パッケージビジネス： SCM、配送計画、 スケジューラ、金融工学・・・ 小規模ビジネスOR： ナビ、勤務表、グループ分け・・・ 件数 ロングテールへのアプローチ ＋ 利益が小さく、人的な苦労が大きい、 ＋ 同じような課題を抱える現場が多い ような問題に対して、解決技術を提供することを目的とする ただし、以下のような点が問題になる ＋ お金がない。デバイスやパソコンの新規導入はできない ＋ 技術力が無く、開発、カスタマイズができない ＋ 導入を考えるゆとりもない （興味もない） ＋ リテラシがない （システムを使いこなせない） ＋ 現場ごとに異なる条件・制約がある ＋ 現場に決定権がない ＋ 件数が多すぎて、マンツーマンでの対応ができない ．．． こんな状況での問題解決を考えるのが 小規模ビジネスOR 小規模ビジネスOR（SBO）の例 • SBOが想定する現場： 商店、事業所、学校、役所、消防署・郵 便局など公共施設、ご家庭、、、 構成人員が少なく、数が多く、共通した労働の多いところ • 小規模配送計画、勤務表作成、時間割作成、作業割当て、小 規模スケジューリング、クラス分け・グループ分け・席替え、、、 •基本的に貧乏なので、早い安いうまいものでないとどうにもなら ないし、技術的にたいしたものも使えない •現在の状況では、集計ソフト・会計ソフトぐらいの導入がやっと 既存研究のスタイル ① 問題を見つけてくる ② 変数と条件を洗い出して定式化し、アルゴリズムを作る ③ アルゴリズムを実装する ④データをそろえて問題を解く 王道だが、実際にはめんどくさい ③ 個別の問題それぞれにアルゴリズムを考え、実装するのは大変 実装・アルゴリズムの再利用ができない • データ／制約をそろえる／入力するのが大変 ① いい問題がない．．． • 逆に言えば、② は簡単なわけです （で、ここの研究をしてしまう） SBOにおける最適化 • 一般的に、SBOの最適化では、最適化がボトルネックでないこと が多い 予算がない、運用が難しい、データ入力に時間がかかる、、、 • そういうところでは、「最適化の手法」自体が現実に貢献する比 率がとても小さい • 実際には、予算がない、運用が難しい、データ入力に時間がか かる、といった問題を解決できるようなシステムのほうが役に立つ と思われる • 最適化の手法ではなく、如何に「作業量を最小化できるか」、 という点に注目するのが、SBOにおける大事なところ SBO のまとめ ★ 今まで無視（？）されてきた、小規模なORに取り組む 非常に多くの、共通性を持つ小規模な業務が対象 Web などの情報学分野では一般的 ★ 最適化の外側での困難が多く、業務全体をスムースにして 「作業量を小さく」 する 「総合的な最適化システム」 が重要 ★ 規模が小さいので、大がかりな道具やデータを用いることはナ ンセンス。あるものを簡単に使うことが肝要 ★ モデル＆最適化では、多くの業務に共通する問題構造を抽出 することが必要。ある種マーケッティングやフィールドワーク 小規模ビジネスOR ＠ 勤務表作成 （久保君の研究） 勤務表作成 （以後は久保君の研究です） • 日本に数多く存在する小規模事業所がかかえる標準的な問題 • 事業所で、だれがいつ（どこで）働くかを決める問題 基本は簡単だが、実行可能解を見つけるのが大変。 従業員には休みが必要だし、バイトやパートは限られた 時刻・時間しか働けない • 曜日による必要人数の変動や勤務可能日が主な制約 • 24時間稼働の事業所では、夜勤や準夜勤などを公平かつ無理 なく分配する点も制約になる （連続した夜勤の禁止、夜勤後の休日の必要性など） 勤務表作成の例 • 基本的には、スタッフ×日数の表を埋めることで作業する •日ごとに、 各人の勤務形態 （休みを含む） を決める • 夜勤が連続して いないか、休みは ちゃんと取れているか、 などチェックする 勤務表作成の難しさ • まずは最適化としての難しさを見る ＋ NP完全 ＋ 意外と変数が多い： 人数×日数（シフト数）） ＋ 制約が全体的に影響するので （1日目を変えると、30日目に も影響がある） 局所的に解きにくい ＋ そうはいっても、日ごと、あるいは人ごとの変化はある程度局 所的 ◇ 現実は、人数ぎりぎりのことが多く、頻繁に実行不能になる ◇ いわゆる「解くのが難しい問題」 ◇ 専門解法（メタヒューリスティック等）を作るか、ソルバを使う 現実の例を見てみましょう • とあるホテルの場合（久保君のバイト先） ＋ スタッフは12-3人： 正社員が5-6人で、残りはバイト （こういう状況はそれなりに一般的と思われる） ＋ 正社員が基本的に核となり、それにバイトを付ける感じ ＋ 基本的にぎりぎり。ぎりぎりでないなら、ギリギリになるまで休 みを取ると思われる。 ＋ 作成にかかる時間はおよそ２時間。１ヶ月分をまとめて作る。 休みの希望、バイトの希望などを考慮して、 うまくはまらないところを調整 最適化の貢献 • 最適化に関わる部分を考察してみる ＋ まず、ほとんど実行不能。なので、調整が不可避 ＋ 実行可能解が見つかればいい、というものではない バランス、公平さ、暗黙知などのいろいろなものがあり、 基本的には明文化できない評価項目が沢山ある 最適化でできることは限られている ＋ 運用は比較的楽。勤務表通りに運用して、 突発的な自体には調整で対応 ＋ 入力も楽。一回ベースを作れば、勤務希望日の入力のみ 最適化システムデザイン • 暗黙知や公平性の基準は事業所ごとに変わるので、モデリン グをするのは難しそう • モデリング言語を使っても、定式化は、現場の人には至難の業 「結果を修正する」ということを必須項目としよう • 調整や修正で、２時間のうち１時間以上とりそう データ入力と修正に時間がかかると意味が無くなる • 初期設定が大変だと、負担が大きそう （利用者が減りそう） 操作性・閲覧性が高いシステムであることが第一要件、 モデリングと最適化は2番目の要因となりそう 要件の達成に向けて 操作性・閲覧性を高くする： 洗練されたGUIが必要 データが表形式なので、既存の表計算ソフトを利用しよう ついでに、導入の容易さ、習熟の容易さも得られる 導入を容易にする： インストール、初期設定などの簡素化 表計算ソフトで実装。利用・開発両面で、簡素化が多い 便利な修正機能を盛り込む： 違反の可視化、修正の容易さ 違反してる制約に対応するセルを色づけ 簡便性： データ入力と最適化、修正が短時間で終了する モデル化はあまり精緻にせず、最適化も簡単に終わらせる 必要最低限の入力で動き、残りは追加的に設定可能とする 初期設定 • まず最初に、人数、 名前、職種、必要人員 などを設定。 これはしょうがない 毎月の作業 • 各スタッフの勤務希望を入力。基本的に月次設定はこれだけ 最適化 • ボタンを押したら最適化 修正 • 制約違反を色付けで可視化。修正は入力と同じなので、簡単か つ効率的 より高機能へのステップアップ • いったん慣れてから高次の機能を使う、という使い方が可能 ＋ 推奨勤務形態パタン ＋ スキル・相性 ＋ 勤務形態回数制限 などなど 実利用 • 久保君のバイト先のホテルで実際に使ってもらいました 作成時間が ２時間から ３０分。効果有り • ほとんどの時間は修正にかかる時間なので、GUIの占める貢 献は大きそうだ • 修正による暗黙知的評価の導入は、比較的うまくいっているよ うだ 作業になんら抵抗なく、それなりに満足できるものが得られてい るようだ 最適化を目指さない最適化 （久保君の研究） 最適化存続の危機！？ • 勤務表が小規模ビジネスOR の代表だと思うと、小規模ビジネ スORのキモは使いやすいGUIをそなえたシステム 最適化（OR）の出番はない！？ • しかし、最適化がないと、使いにくいのも事実 自動的に、それなりのたたき台を提供してくれる、 という意味では、必須の機能といえるだろう • それでも、修正やデータ入力など最適化の外側がメインである ことは事実 • ならば、「修正やデータ入力を省力化する最適化」が重要となる だろう 外側を向いた最適化 • データ入力を行わない最適化 無理。 しかし、「データ入力を少なくする」最適化は可能だろう ＋ 細かい制約・項目は考えず、修正に任せる ＋ デフォルト値の活用。最適解に利いてくるところだけ、 後から入力させる （対話型入力システム） ＋ ある程度自動で決める。困るところは指摘してもらえばいい ＋ 修正の履歴や最適解から、データ値を類推する • 基本的なコンセプトは 「新人君にお仕事をお願い」 とりあえずまかせておいて、必要なところだけ指摘すればいい （次回以降、覚えてくれれば、なおいいね。） 勤務表のデータ入力 • 毎月共通の事業所の業務形態、スタッフの基本勤務形態は、 入力しておかないと最適化できない • 各月の、スタッフの勤務希望、ここも重要 （希望は主に休みであり、他の勤務形態になる可能性が高いの で、あらかじめ指定した方がいいだろう） ここは必須であろう • 細かい制約・項目は無視し、これのみで考えるのがいいだろう 修正の容易さを目指す • 修正の容易さはどのように目指せばいいだろうか？ どのように修正したいか分からないと、修正のやりやすさが わからない でもそれは、暗黙知だから指定しないという方針だった • やりたいことを知らずに、うまく仕上げるのは不可能では？ 無理でしょう • でも、やりたいことにある程度の共通性があるのであれば、「平 均的に修正しやすい解」は存在するかもしれない 修正容易さ、のヒント • I先生から聞いたこと 「現場では、まず考慮制約だけを考えてスケジュールを作り、そ の後必須制約を満たすように変更していくんですよね。」 ある種の貪欲解法をしている。希望のみ満たされた初期解 から出発し、暗黙知と制約を満たすように希望を削っていく • こういうやり方が人間にとって都合がいいのかもしれない （制約を満たす方向に動くだけですむ） • 最適化の場合、制約を破ってからもう一度満たすので、欲しい 解から現在解の距離が遠いかも やってみた。 • ほんとかな、と思ったので、やってみました ＋ 必須制約を重視、考慮制約を重視、両方ほどほどに （つまりいい加減に）最適化した解を準備 ＋ ユーザに、「公平になるように、ちょっと相性条件も加えて、 最適化して下さい」とお願いする （計１３人） ＋ 公平さの尺度は、各人の感性に任せる （人々の自然な感覚が知りたいので） ＋ これでいいだろう、と思ったところで終了（ある程度現実的） 結果発表 • 必須、考慮、両方ともほどほどに考慮した解が、もっとも扱いや すいようです （正確には、必須制約を優先すると時間がかかる、 考慮制約を優先したやつはだいたいよい、両方考慮した やつは短い時間（考慮優先より１割減）でできる、という感じ） • 制約に張り付くよう、きっちりと最適化をしたことが、「その制約を 守って他の解に変更する」ということを難しくしているようです • ということは、ある程度制約から離れた解を見つける、 というスタンスが重要なのかもしれない 制約伝搬 • 一般に、ある変数の値を変更すると、いくつかの制約が満たされ なくなる • それらの制約を満たすべく、多の変数の値を変更すると、さらに 多くの制約が満たされなくなる、という具合に、制約違反が伝搬し ていく 制約伝搬、という • こういうことが起きなければ、解の修正はある意味容易 制約伝搬が起きないような最適化を目指すべきかも • と具体的にどうするか、なかなか難しい 制約が利いてる変数を限定し、ブロック化できればいいか？ ぎちぎちに最適化しない、というのは、一つの解答、かな？ 最適化を目指さない、というスタイル • 厳密に評価関数を最適化しない、あるいは評価を厳密に定義し ない最適化は、このごろけっこう見かけるし、重要である • 例えば、ページランクやリコメンデーション。目的ははっきりして いるが、数理的にははっきりしていない。現実のデータやモデルか ら、ある程度頑強な評価値 を出すことを基軸としている （評価値を基盤にしていろいろなことを考えている） • 機械学習では、オーバーフィッティングを避けるため、わざと最適 化を途中でやめている 制約に張り付かないこと」 が評価値になっている まとめ 提言： 最適化研究、モデルや手法を突き詰めること以外の方向性 があると、この先の研究も面白いのではないか • 応用を見る場合に、市場（顧客）の量や質という点や、全体的な 傾向をとらえたモデリングがありえるのではないか 小規模ビジネスORの提案 • 勤務表作成での、小規模ORの実践 ＋ 最適化をシステムのごく一部と位置づける ＋ ごりごりと最適化をせず、修正を容易にする ＋ 修正やデータ入力を省力化するような解を求める
© Copyright 2024 ExpyDoc
