特に 仕組み（体制）作り 実験的解析 ．．．に関する私見

Presentation on theme: "特に 仕組み（体制）作り 実験的解析 ．．．に関する私見"— Presentation transcript:

1 特に 仕組み（体制）作り 実験的解析 ．．．に関する私見
理論と実務をつなぐには ただし．．． （組合せ）最適化に対する 近似アルゴリズム設計工学 にお話を限定 特に 仕組み（体制）作り 実験的解析 ．．．に関する私見

2 アルゴリズム工学の研究 実務 応用 理論 大学，研究所 企業，官庁，自治体 実務を意識しない（しなくても良い）研究 実務指向の研究=
実務から生まれた問題 に対する理論的研究 実務から問題を抽出 ＋アルゴリズム設計 ＋実際問題の解決 実務 応用 理論 大学，研究所 企業，官庁，自治体

3 アルゴリズム工学の研究の流れ 良い問題の選定 良いアルゴリズムの設計 アルゴリズムの正しい評価 実務への橋渡し

4 解くべき問題の種類 定型化された（スタンダードな）問題 （汎用性高，新規性低） 定型化された問題のバリエーション
個別受注生産型の問題（実務主導型の問題） （汎用性低，新規性高） 良い問題の選定 良いアルゴリズムの設計 アルゴリズムの正しい評価 実務への橋渡し

5 定型化された問題 I 汎用的な問題 LP,MIP,NLP->そのままで有用 一般的な運搬経路問題,
一般的なスケジューリング問題 ->多少カスタマイズすればOK，ある程度有用（なケースが多い，がそうでないケースもある->個別受注生産型の問題）

6 汎用的な問題に対する 理論・応用・実務の関係
モデリング言語 AMPL, OPL,GAMS +ユーザー・インターフェィス 最適化コンポーネント（ライブラリ） ・・・アルゴリズムをblack box化 ILOG Dispatcher, VRP Solver (MRI & Kubo) ILOG Scheduler, Nonobe-Ibaraki’s Solver ソルバー 線形計画 混合整数計画 非線形計画 制約論理言語 メタ解法 応用 理論 実務

7 定型化された問題 II メタファーとしての問題：TSP,ビンパッキング問題，SATなど(ベンチマーク問題が豊富な問題)
ＴＳＰはNP-hard問題の代表例 ->そこで開発されたアルゴリズムを他の問題に拡張 豊富な比較対象->アルゴリズムのtest bed （8th DIMACS Challenge) フローショップスケジューリング問題は有用か ジョブショップスケジューリング問題は有用か？

8 フローショップ問題 最初の論文: Johnson (1954) ’s seminal paper in Naval Research Logistics Quarterly 動機は友人から聞いた未解決問題 その後膨大な量の研究が出版 The lessons of flowshop scheduling research, Dudek, Panwalkar, and Smith,Operations Research (1992) 応用なし 30年間に開発されたアルゴリズムは制限が多すぎて実務には使えない 実務は動的 実際のフローショップは全然違う などの理由により．．．

9 フローショップ問題（続き） 30年以上の間の膨大な研究によって
得られた知見： It is important to frequently step back from their modeling work and ask the question, “When I complete the work, well it be of value? Will there be applications? Do problems exists that this research can aid in solving?”

10 ジョブショップ問題 困難なスケジューリング問題たちのメタファー＆test bed
ジョブショップスケジューリング問題（１０×１０=930に対する挑戦！）に対する分枝限定法（の中身のいろいろな工夫）->一般的な資源制約付きスケジューリング問題の商用ソルバー（E.g., ILOG Scheduler）のコア アルゴリズムはジョブショップスケジューリング上で開発・比較->一般的なスケジューリング問題に適用

11 定型化された問題の バリエーション 理論 応用 TSPは標準: 多くの研究＋実務的にも有用 こんな条件を付加したバリエーションもありそうだ．
あるに違いない．．． あればいいな．．． そのうちあるかもしれない．．． 理論 応用

12 定型化された問題の バリエーション （とWell Solved Special Case）
K-TSPは有用か？ 部分巡回路問題は有用か？ 次数制限付きグラフ上でのTSP ( A Well Solved Special Case) は有用か？

13 定型化された問題のバリエーション K-TSP
　総距離最小化 （ＴＳＰに帰着） 　最大距離最小化 （ルートの均等化） デポ VRPのための基礎？ NO!

14 定型化された問題のバリエーション 部分巡回路問題(賞金収集TSP・Steiner木問題など）
最大化 Σ(v ∈Tour) Prize(v) －Σ(e ∈Tour) Cost(e) Cost(e) Prize(v) 段取り替え最小化 Steiner木問題は 光ファイバー網設計問題

15 定型化された問題のバリエーション 次数制限付きグラフ上でのTSP
φ Edge ・ Tour Iterated Lin-Kernighan opt Bounded Width TSP

16 個別受注生産型の問題 応用 実務 抽出する必要あり！ 実務から応用への橋渡しで最も欠けている部分！ 重要な問題を選ばなければならない！
・（企業体の）費用の大幅な削減をもたらす 　　　　　　　導入費用<<削減費用！ できれば．．． ・地球環境を良くする，住みやすい社会を作る ・人類・地球を長持ちさせる 応用 実務

17 個別受注生産型の問題 問題の抽出 II 重要性の尺度として．．． 共同研究費用（高いほど重要かつ使用する確率高）
企業側の論理: 社員が３年がかりで作成したアルゴリズム ＞＞共同研究費数十万で作成したアルゴリズム 特許や論文のノルマを達成するための共同研究× 　

18 個別受注生産型の問題 問題の抽出 III 応用 実務 抽出した問題例の公開 守秘義務の壁！& 面倒くさい
抽出した問題例の公開 守秘義務の壁！& 面倒くさい ->実際問題例に似せた問題（pseudo-application： 小規模な例題から本来の問題に近い規模の問題） を作成し公開 応用 実務

19 自動販売機の補充から生まれた問題 IT技術によって自販機の位置および販売量が既知，データ整備，予測可能
市場規模：あるメーカーで5万台，1台あたり7000円/補充1回，おおよそ週１配送 ->１日5000万円! 全国で800万台-> 80億円/day （本当?） 最適コラム割り当て問題 在庫配送計画問題（Vender Managed Inventory or Automatic Replenishment)

20 最適コラム割り当て問題 自動販売機

21 最適コラム割り当て問題 コラム

22 最適コラム割り当て問題 -一般化割り当て問題の変形- ジュース（１２０種類） コラム 30本入り (COLD)×5
39本入り (HOT)×5 販売量予測 配送周期 20本入り (COLD)×5 15本入り (COLD)×5 容量制約（15-30本/コラム）

23 最適コラム割り当て問題 AMPL+CPLEX6.5 （小規模問題で×） 通常の定式化->解の対称性 分枝価格法 Tabu Search

24 在庫配送計画問題 -在庫モデル×VRPのバリエーション-
デポ ×∞（無限期間） 　有限期間（３０日）に帰着-> Rolling Horizon方式 　Neuro DP （強化学習）

25 実際問題を解くためには．．． 幅広い守備範囲（我田引水は×） 適切なアルゴリズムを選択・設計のセンス 最新のアルゴリズムに関する知識
実務家との信頼関係 真剣な取り組み 「論文になるなら無料で問題を解決しましょう！」 -> 研究>>実務問題解決 -> 共同研究は雑用

26 アルゴリズム設計 I 応用 理論 手法先行は（基本的には）× 関連研究の入念な調査＋ 妥当なアルゴリズムの選択
　手法先行は（基本的には）× 　関連研究の入念な調査＋ 妥当なアルゴリズムの選択 データ構造の選択・設計，プログラミング 良い問題の選定 良いアルゴリズムの設計 アルゴリズムの正しい評価 実務への橋渡し 応用 理論

27 アルゴリズム設計 II 応用 応用 実務 理論 応用
手法先行でも○のケース いくつもの応用（問題のクラス）に適用可能な汎用アルゴリズムの設計 E.g., 運搬スケジューリング問題に対する列生成（分枝価格法） 応用 応用 実務 理論 応用

28 アルゴリズム側の要求から出てきた 問題のクラス -運搬スケジューリング問題-
（時間枠付き）運搬経路問題 乗務員スケジューリング問題 Dantzig-Wolfeの分解原理 ⇒列生成法 分枝価格法（branch and price method） 統一的求解のためのフレームワーク

29 良いアルゴリズムとは？ アルゴリズムの評価尺度
性能 速さ（CPU時間，仮想実行時間，メモリアクセス回数），メモリ使用量，解の良さ（性能比率，相対誤差） 一般性 頑強性，パラメータに対する頑強性，汎用性 利便性 単純性，実装の容易さ，拡張の容易さ，モジュール化のし易さ 報道価値性 新規性，重要性

30 アルゴリズムの正しい評価とは？ アルゴリズム解析のパラダイム 解析的方法 実験的方法 最悪値解析 確率的解析
良い問題の選定 良いアルゴリズムの設計 アルゴリズムの正しい評価 実務への橋渡し アルゴリズム解析のパラダイム 解析的方法 最悪値解析 確率的解析 実験的方法 特定の応用（実務）のためのアルゴリズムに対する実験 (application paper） （標準的な問題に対する）アルゴリズムの優越性を示すための実験 (salespitch paper) アルゴリズムの平均的・実際的な振る舞いについての知識を得るための実験 (experimental paper)

31 どの解析法を使うべきか？ 3つの格言 Experimentation provides a pathway from theory into practice. (David Johnson) The purpose of mathematical programming is insight, not numbers. (Arthur M. Geoffrion) My suggestion is simple: by whichever is more effective for the problem at hand. (John Bentley)

32 どんな問題例を使うべきか？ Application paper（検証実験） Salespitch paper（競争的実験）
実際問題もしくはそれに類似した問題 Salespitch paper（競争的実験） ベンチマーク問題（なければ自分で作成；開発したアルゴリズムで解きやすいクラスだけ生成しないように！） Experimental paper （分析的実験） ランダム問題生成プログラム（E.g., U(0,1] for bin packing) ->漸近値解析 特に有効なのはパラメータで制御可能なランダム問題生成プログラム（E.g., U(a,b] for bin packing) ベンチマーク問題は補完的（頑強性を調べるため）

33 実験的解析の手順 I 実験 目標を定める（比較実験か分析実験か） 評価尺度を決める
評価尺度を測定するための基準を定める（CPU時間 or メモリアクセス回数 or 仮想実行時間） 問題例の仕様を定める（ランダム or ベンチマーク or リアル） 実験環境を決める 実装（データ構造の選定含む） 実験 予備実験 実験計画 本実験 データ解析 結論導出

34 実験的解析の手順 II 本実験 -競争的実験-
挙動分析実験（視覚化）：現象の観察＋なぜそのような現象が起きるのか？を調べる パラメータの適正値を得るための実験（視覚化） ベンチマーク問題に対する最良値を得るための実験（数値による表示） 平均的な挙動を示すための実験（数値＋図）

35 実験的解析の手順 III 従来の研究との比較法
従来の研究で用いたプログラムをもらって，同じ計算機上で比較 従来の研究と同じプログラムを自分で作成して比較（ほぼ同じ性能が出せれば OK） 実装の詳細が報告されてない or 実装が困難従来の研究の報告値と比較（計算機のおおよその速度の比較を付記） 従来の計算機が特殊 比較困難な理由を正直に述べ，努力を認めてもらう

36 実験的解析の手順 IV 本実験 -分析的実験-
Dependency study: 問題例のパラメータ（たとえばサイズ）と評価基準（計算時間，性能比率など）の依存関係を調べるための実験 問題例の規模との依存関係をみるときは，サイズを倍々にしていって，Log-Log（or Semi-Log） Plotが有効 Robustness study: 複数回のランダム・トライアルによって分布（ばらつき具合）を調べるための実験 Probing study: アルゴリズムに検針を入れることによってアルゴリズムに対するさらなる洞察を得るための実験

37 実験的解析のための格言集 I （旧十戒：離散構造とアルゴリズムIV 「メタヒューリスティックス」近代科学社）
再現性 実験環境を正確に報告せよ 実装の詳細を報告せよ できるだけベンチマーク問題を使うべし（分析的実験の場合には，(parameterized)ランダム問題例が有効） 実験に用いた問題例は細心の注意をもって保管せよ パラメータには（根拠付きで）推奨値をあげるべし 終了判定基準にＣＰＵ時間を使うなかれ（とは言っても大量の実験をするときには便利だ．同等な終了判定基準を示せばOK） -> 終了判定基準にＣＰＵ時間を使うときには，同等な終了判定基準を示すべし

38 実験的解析のための格言集 II 一般性 Deus ex machina（天下りの機械神）によってパラメータを決めるなかれ
玩具問題で遊ぶなかれ（小規模実験ではウソになるケースが多い！） できるだけ多くの問題例を解くべし できるだけ大きな問題例を解くべし 結論だけでなく，なぜそのような結論が出るのかに対する説明をつけよ

39 実験的解析のための格言集 III 研究者としての良識 自分で作成した効率の悪い解法と比べるなかれ 従来の研究をよく調べよ
肯定的な結果に固執するなかれ 統計技法を濫用して結果をごまかすなかれ 事前処理などの時間も隠さずつけよ 実験結果の不具合に対する説明も隠さずつけよ プログラミング技術の拙さを言い訳にするなかれ（とはいっても，どこまで（データ構造などに）凝ればいいかは難しい問題！） ->ある程度効率的な実装をせよ（分析的実験でも）

40 実験的解析のための格言集 IV プレゼンテーション 図による表現を有効に活用せよ（特に漸近値を調べるときのLog-Log Plot）
生データを読みにくい図でごまかすなかれ（スケールによって効率をごまかすなかれ） ベンチマーク問題の最良値を更新したときには，値だけでなく解も報告せよ

41 アルゴリズム工学 科研 特定領域プロジェクト
アルゴリズム工学 科研　特定領域プロジェクト 良い問題の選定 良いアルゴリズムの設計 アルゴリズムの正しい評価 実務への橋渡し 副題 ー理論と応用の橋渡しー プログラムの公開（アルゴリズムデータベース） 可視化GUIの作成 実務 応用 理論

42 プログラムの無料配布は 理論と実務の橋渡しになりえるか？
利用者（研究者，技術者，プログラマ，End User）のアルゴリズムに関する知識に依存するが．．． マニュアルの整備（対象が研究者，技術者以外の場合にはreadmeの類では×，Value Added Resaleのためにはテクニカルドキュメント（内部仕様書）が必要） サポート体制（個人の責任の範囲！） 信頼性（個人の責任の範囲！！） ユーザーの要望によるカスタマイズ （経験では．．）無料奉仕は最善の方法ではない！

43 橋渡しのための仕組み アルゴリズム （コアプログラム） 販売，コンサル 法人 研究者 実務家 技術指導料 著作権料 代金 研究費 実問題
カスタマイズ マニュアル整備 GUI作成 コンポーネント化

44 （最適化が社会的認知を得るための） より望ましい仕組み
エンドユーザー 法人 Value Added Resale 再販法人 エンドユーザー 法人 Bridge 法人 研究者 再販法人 エンドユーザー 法人 コアプログラム 実験的解析 カスタマイズ 内部仕様書 エンドユーザー 法人

45 橋渡しのための格言 事例研究が泥臭いと決めつけるなかれ 安請け合いした実際問題を学生に丸投げするなかれ
応用がないことを自慢するなかれ（pure math.なら別だが．．） 実験を学生に丸投げするなかれ（実験的解析は簡単な作業ではない！） 委託研究を雑用と位置づけるなかれ 自分の研究の，理論から実務の間の線上における位置づけを意識せよ

46 次回のRAMPシンポジウム 理論と実務のフュージョン
宮本さん（商船大） ｽｹｼﾞｭｰﾘﾝｸﾞ固定テストの高速化 Gosselinさん（ILOG） CPLEX,OPL, Scheduler 最適化ｺﾝﾎﾟｰﾈﾝﾄ 佐藤さん（東洋ﾋﾞｼﾞﾈｽｴﾝｼﾞﾆｱﾘﾝｸﾞ） SABLINA ﾛｼﾞｽﾃｨｸｽ・ｺﾝｻﾙﾂｰﾙ 水野さん（東工大） Self-Dual LP 内点法の統一理論 実務 応用 理論