離散最適化基礎論

電気通信大学大学院情報理工学研究科情報・ネットワーク工学専攻
2018年度後学期
金曜4限 (14:40-16:10)
教室：西8-132

岡本吉央

テーマ：理想グラフに対する組合せ最適化

注意：内容は毎年変わります

レポート課題

演習問題の中から「補足問題」，「追加問題」を5つ選び，解答せよ．ただし，以下の制限がある．

1問20点満点で，計100点満点で採点される．
ただし，問題1.2と問題10.6は10点満点とする．
第1回，第2回，第3回の中から1問以上選ぶ．
第4回，第5回，第6回の中から1問以上選ぶ．
第10回，第11回，第12回，第13回の中から1問以上選ぶ．
他の受講生との相談や文献参照を行ってもよい．ただし，その際は，相談した相手の氏名や参照した文献を必ず明記すること．

締切は2月15日(金) 16:30．提出先は西4号館4階事務室前レポート提出箱「岡本」．

講義資料

新たに掲載したとき，つぶやきます

2/8 (13) 理想グラフに対するアルゴリズム
- スライド (2/8修正) | 印刷用スライド (2/8修正) | 演習問題
2/1 (12) グラフのシャノン容量
- スライド (2/8修正) | 印刷用スライド (2/8修正) | 演習問題 (2/5修正)
1/25 (11) 組合せ最適化と半正定値計画法
- スライド (1/30修正) | 印刷用スライド (1/30修正) | 演習問題
1/11 (10) 楕円体法 (2)：応用
- スライド (1/15修正) | 印刷用スライド (1/15修正) | 演習問題
12/21 (9) 楕円体法 (1)：基礎，アルゴリズム
- 村松先生がスライドで行います．
12/14 (8) 弱理想グラフ定理 (2)：多面体的手法
- 村松先生が板書で行います．
12/7 (7) 凸多面体の基礎
- 高橋先生が行います．
- スライド (高橋先生)
11/30 休講
11/16 (6) 組合せ最適化と線形計画法
- スライド | 印刷用スライド | 演習問題
11/9 (5) 弱理想グラフ定理 (1)；グラフ理論的手法
- スライド | 印刷用スライド | 演習問題
10/26 (4) 代表的な理想グラフ (3)：区間グラフと弦グラフ
- スライド (10/26修正) | 印刷用スライド (10/26修正) | 演習問題
10/19 (3) 代表的な理想グラフ (2)：二部グラフの補グラフ
- スライド (10/19修正) | 印刷用スライド (10/19修正) | 演習問題 (10/19修正)
10/12 (2) 代表的な理想グラフ (1)：二部グラフと二部グラフの線グラフ
- スライド | 印刷用スライド | 演習問題
10/5 (1) 理想グラフと組合せ最適化
- スライド (10/12修正) | 印刷用スライド (10/12修正) | 演習問題

2/8 (13) 理想グラフに対するアルゴリズム
- コメントをありがとうございました．評価はレポートで行いますので，よろしくお願いします．
- 半年間ありがとうございました。レポートがんばります。
  --- こちらこそありがとうございました．
- 難しかったですがわかりやすい講義をありがとうございました．
  --- こちらこそありがとうございました．
- 一年間のこうぎを受けているようなこい授業だと思いました。ありがとうございました。
  --- 確かに濃かったですね．;-) 自分もたくさん勉強になりました．
- どうか健康でいてください。
  --- ありがとうございます！
- グラフ理論や離散最適化の知識がまったくない状態で講義を取りました。講義を通して，それらへの抵抗がなくなり，読める教科書や論文が増えたように思います．一学期間，ありがとうございました．
  --- 抵抗がなくなったというのは嬉しい感想です．ありがとうございました．
- 線形代数、グラフ理論、最適化と色々混ざっていて楽しかったです。
  --- そうですね．いろいろと混ざるのが本質だと思ってます．
- 今後この講義が役立つ場面がくるかわかりませんが，ひとまず理解に努めてレポートを出せるようにしたいと思います．
  --- はい，レポートをお待ちしております ;-)
- 中高の数学の先生を目指しているのですが何か一言アドバイスお願いします。
  --- 数学は役に立たない，とよく言われることがあります．大学や大学院での勉強を通して，中学生や高校生に，数学が役に立っている様子を伝えていただければ，と思います．
2/1 (12) グラフのシャノン容量
- コメントをありがとうございました．
- 計算機ではなく、数学によってC_nのシャノンキャパシティが特定されてほしいです…。
  --- 現代では，計算機を援用して数学を行うことになっているので，計算機を使うこと自体も数学だと考えられています．
- 行列の積の種類が多くて混乱する
  --- クロネッカー積は量子力学や符号理論でも出てくるので，慣れておくとよいと思います．
- 物理世界とちょっとつながる感じでうれしかったです．
  --- 今回の話は，理想グラフがどこから出てきたか，という話でもありますし，理想グラフがどこで役立つか，という話でもあります．その意味では応用的な内容だったのかもしれません．
- $\displaystyle \sup_k (\underbrace{G \boxtimes \cdots \boxtimes G}_{k \text{ times}})^{1/k}$ の $k$ の部分が分かった方がうれしいと思うんですが、最適化問題で $k$ の値は分かるんでしょうか？
  --- $G$ が $C_5$ の場合は，$k=2$ のところで $\sup$ が達成されるのですが，一般のグラフに対しては，ある有限の $k$ で $\sup$ が達成されるかどうかは分からないです．その意味で，$k$ の値は分からないです．
- グラフで通信路を表現するときに一般的な遷移行列と対応はありますか？
  --- あります．送信側と受信側のアルファベットが同一で，$i$ が $j$ に遷移する可能性があるとき (遷移確率が正であるとき) $i$ と $j$ の間に辺を引くことで，混同グラフが得られます．
1/25 (11) 組合せ最適化と半正定値計画法
- コメントをありがとうございました．
- 個人的なイメージですがハンガリー人には有名な数学者が多い気がします。
  --- 離散数学ではそうだと思います．ハンガリーにはケマルという高校生向け数学雑誌があり，そこでコンテストが行われています．この雑誌は19世紀からの歴史があり，そこの優秀者が後に優秀な数学者になるという傾向があるように思います．
- やっとここまでたどり着いたという感想をもちました。
  --- 私もそう思います．
- コレスキー分解 ← これすき
  --- 私も好きです :-)
- まだついていけてない部分が多いですが、理想グラフの話とつながって、ω(G)，χ(G)が求まるようになって、壮大な話だなあと思います。最大クリークを求めるの楽しみです．
  --- 壮大ですね．このような話が1980年代に確立したと思うと，今から思ってもすごいと思います．
- 最大クリークや最小彩色を求めることはどのように工学応用されるのですか．
  --- 現在，一番多く使われているのはクラスタリングだと思います．最大クリークは「部分構造を見つける」という問題で，最小彩色は「うまく分割する」という問題ですから，知識発見に関わる問題と相性がよいです．
1/11 (10) 楕円体法 (2)：応用
- コメントをありがとうございました．
- あけましておめでとうございます．
  --- あけましておめでとうございます！
- 退院されてよかったです．どうかご無理なさらず、元気であることを願います．
  --- ありがとうございます．
- 固有値の出し方おもいだします．
  --- 固有値はいろいろなところで頻出するので，しっかりと復習をして下さい．
- 楕円と半空間の共通部分を含む最小体積の楕円体を見つけるのが大変そう
  --- これは前回の授業で扱いましたが，結論だけ見れば，割と簡単に計算できます．
- 半正定値行列の集合が凸であるということが、可視化のおかげでかなり理解しやすいと思いました。
  --- 絵で直感的に理解することには力を入れています．皆さんも励行して下さい．
12/21 (9) 楕円体法 (1)：基礎，アルゴリズム
- 以下，村松先生にいただいたコメントと村松先生の御回答を掲載します．
- 図形的なイメージがわいたので、だえん体法はわかりやすいと感じた
  ---図形的なイメージはとても大切です。大事にしてください。
- スライドで進めてもらうと分かりやすい。でも内容は難しくて分かりにくい。
  ---今回の話は、細部を理解しようとしないでください。イメージができるようになればOKです。
- 多くのテクニックが使われる証明で一気には飲み込めなかったので、ゆっくり確認したいと思います。
  ---ぜひそうしてください。
- 楕円体法を実装するのに挑戦したくなりました！
  ---自分ではやりたくないですが、楕円体の実装は見てみたいです。がんばってください。
- 半正定値もですが正定値もあまりよく知らないです。（正定値の定義が論理記号を使って書いてある）
  ---勉強してください。ちなみに１次元の場合、正定値行列は正の数、半正定値行列は非負の数にあたりますね。だからどうということもないですが。
12/14 (8) 弱理想グラフ定理 (2)：多面体的手法
- 以下，村松先生にいただいたコメントと村松先生の御回答を掲載します．
- 板書で証明を味わうのは久しぶりだったので楽しかった。
  ---ありがとうございます。
- 証明がごちゃごちゃしていて分かりづらかった、、、
  ---すみません。途中、ストーリーを飛ばしたりしてましたからね。。。
- 絵が描きづらいし、難しそう。
  ---絵は描きづらいです。難しいです。だから、わかったときに感動があります！
- 興味深い証明でした。よく復習してみます。
  ---ぜひそうしてください。わからないことがあったら聞きに来てください。
- 証明のスピードがちょうどよくてわかりやすかった。
  ---ありがとうございます。板書は板書の良さがありますよね。
- 最初の $a) \Rightarrow c)$ の証明でグラフ $G'$ を考えるところが少し混乱しました。
  ---すみません。岡本先生みたいに綺麗な図をかけると良いのですが、、、(岡本注：これは複製補題を使ったグラフ理論的な弱理想グラフ定理の証明でも登場しているので，その部分も参考にして下さい．)
- 証明をもりもり描くのは久々で新鮮でした。あとから見直してじっくり確認したいと思います。
  ---ぜひそうしてください。わからないことがあったら聞きに来てください。
12/7 (7) 凸多面体の基礎
- 以下，高橋先生にいただいたコメントと高橋先生の御回答を掲載します．
- 凸包の話から体力が持たなかった．授業のペースがは早いように感じた．
  --- 少し詰め込みすぎたと反省しています．
- 岡本先生がとってもとっても心配です．ゆっくり休んで早く良くなって復帰されることを願っています．
  --- 私も早く良くなって復帰できることを願っています．
- 単語に聞き慣れないものが多々あったので少し難解でした．
  ex. 集合システム(E,F)，ファセット定義不等式の説明に出てきた極小な部分系
  --- 詰め込んだ結果，1つ１つの話題が駆け足になってしましました．
- 連続最適化の内容が入ってくると途端に分からなくなる．
  --- LPの話が中心だったので実数は扱いましたが，そこまで連続最適化していないと思います．
- 幾何系の話題が好きなので次回以降が楽しみです．
  --- 次回以降は村松先生が弱理想グラフ定理の証明，楕円体法を解説してくれます．
- 計算幾何学との関連について想起しました（凸ほうの話など）
  --- 凸包は計算幾何学の1トピックですね．
11/16 (6) 組合せ最適化と線形計画法
- コメントの掲載が遅くなってしまい，申し訳ありません．
- 今週急に寒くなった気がします。
  --- 体調には十分気をつけてください．
- 西8のエアコン効き弱すぎませんか？言ってもしようのない話ですが…
  --- 聴講者数に比べて，部屋が大きすぎるのだと思います．
- 組合せ最適化問題の解き方が少し理解できました。自分の研究に使えたらいいな～
  --- そうですね．大学院の授業としては，皆さんの研究の中で使えるようになっていただけるのは究極の目標です．
- グラフに関する問題を数理計画法の枠組みで解く際に，グラフが理想グラフであった方が色々と都合が良いよねという話だと解釈しました。
  --- 正しい解釈だと思います．
- 表現を変えるだけで非常に多くの視点から問題を眺められるようになるのはとても面白いと思いました。
  --- 1つの問題を表現する方法がいろいろとあり，また，それを解く手法もいろいろとある，というのは重要な視点で，うまく使いこなせるようになるといいと思います．
- 授業の構成が上手くてわかりやすいなーと尊敬します．
  --- ありがとうございます．
- スライドp.24の(1/2, 1/2, 1/2)の点はx_a～cでつく有れる多面体の外側にあるのが最初気づきにくかったです．
  --- 確かにそうですね．立体の図は，動かしてお見せするほうがよさそうですね．
- 早くSDPらへんの話が知りたいのですが，オススメの文献はありますか？
  --- 以前 (私が学生だった頃)，日本オペレーションズ・リサーチ学会の機関誌で「半正定値計画とその応用」という記事が4回に渡って掲載され，それはとても勉強になりました (第1回，第2回，第3回，第4回)．この辺りの内容は2000年ぐらいまでの基礎知識で，今となっては，組合せ最適化における常識なので，最先端の内容はこれよりもっと進んでいるわけですが，そうであっても，もちろん基礎は重要なので，この4回の記事を参考にして下さい．
11/9 (5) 弱理想グラフ定理 (1)；グラフ理論的手法
- コメントをありがとうございました．
- 無限に眠い．
  --- 発散しないように，お願いします．
- BGMが美容室みたいでした．
  --- 美容室にいかないので分かりません ;-)
- 最大独立集合の数だけ頂点を複製して，すべての最大独立集合と交わるクリークがあることを示すところが綺麗で楽しかったです．
  --- そうですね．証明が味わえると楽しいですね．
- 弱理想グラフ定理を証明するのに頂点を複製しようと思う発想がどうして出てくるんだろうと思いました．
  --- 彩色を独立集合への分割であると見なしたとき，厄介なことの1つが用いる独立集合の要素数がバラバラであるということです．しかし，複製を行うと，用いる独立集合の要素数がすべて等しくなります．それによって，証明の見通しが立てやすくなる，という利点があります．なかなか思いつく発想ではないと思いますけどね．
- 複製の操作を使うのは頭が良すぎるなと感じました。補グラフが出てくると混乱するのですが対応関係を上手く使っていて面白かったです．
  --- 頭が良すぎるな，と観点について，私も同じ気持ちです．ただ，多面体的な証明をやってみると，複製を使うことが何だか自然に思えてくる気もします．その気持ちが後の方で共有できるとうれしいです．
- 難しいけどがんばります。
  --- 私にとってもなかなか難しいです :-)
- 図形的に証明の流れをつかめるのはグラフ理論の強みだと思いました。
  --- しかし，残念ながら，論文とか教科書を見ても，あまり図は出てきません．この講義では，できるだけイメージを掴めるように図を多用していますが，本来，数学ですから，図の直感を排して，ことばだけで理解できることが理想ですね．
- 個人的には，グラフの複製の順を変えても結果が同じになるということが直観的ではなく，特別，今回の授業を難しく感じた．
  --- 授業の中ではその点を少しごまかしてしまいました．実際，順を変えても同じグラフが得られることは証明できますので，考えてみて下さい．
- 村松先生の数理計画法のときのノートを掘り出す必要が出てきそうですね．
  --- そうかもしれないですね．数理計画の理論をあまり深くは使わないつもりですが，復習が必要そうでしたら，積極的にお願いします．
- 社会人になるまで残り5ヶ月です。やっておいた方がいいことって何かありますか。
  --- しっかりと修了できるように，しっかりと勉強して下さい．
- クリーク数の計算が最適化問題として定式化できて安心しました。すこし考えにくい概念だったので．．．
  --- 組合せ最適化問題をいかに数理計画問題として解くのか，という次回の内容になります．お楽しみに．
- 多面体的手法に関して発展的な書籍／論文はありますか？
  --- どこまでが基礎でどこからが発展なのか，という線引きは難しいですが，基礎的なことはいわゆる組合せ最適化の教科書に書いてあります．日本語だとコルテ，フィーゲンの『組合せ最適化』が詳しいです．ただ，この本はそんなに多面体的ではないです．『最適化ハンドブック』という本があり，そこには「多面体的組合せ論」という章があり，そこもなかなか詳しいです．ただ，このハンドブックは古いです．発展的なものになると，多面体では収まらず，たいてい，もっと複雑な凸集合 (凸体) を扱うことになります．あるいは，多面体的手法を近似アルゴリズム設計に用いるといった内容のものもあったりします．
10/26 (4) 代表的な理想グラフ (3)：区間グラフと弦グラフ
- コメントをありがとうございました．掲載が遅くなり，すみません．
- 音楽が流れているとききいってしまって集中できないので、音量を小さくしていただきたいです．
  --- 了解しました．耳障りなようでしたら，直接お申し出ください．
- トロピカル・ハウスを流してください
  --- 直前のコメントと両立するかわかりませんが，善処します．
- グラフがchordalかどうかを目で見てぱっと判別するのがけっこう難しいです
  --- 私もよく間違えます ;-)
- 区間グラフは弦グラフであるということは理解できました。弦グラフは区間グラフであるという主張は成り立つのでしょうか
  --- 残念ながら，それは成り立ちません．例えば，次のグラフは弦グラフなのですが，区間グラフではありません．
- もしかして弦グラフは3-彩色可能ですか？
  --- 残念ながら，それは成り立ちません．例えば，完全グラフはどれも弦グラフなので，その頂点数が4以上ならば，3彩色可能ではなくなります．
- 何かを対象を二部グラフや区間グラフ，弦グラフでモデル化できたとしたら，染色数やクリーク数が計算しやすいということですか．
  --- その通りですね．理想グラフとしてモデル化できたとしたら，染色数やクリーク数が計算しやすいです．
- '頂点数に関する帰納法' という記述は '|V'|<|V|'である任意のG'=(V',E')について命題が成立する' という仮定をしてGについて議論してる，という認識でいいですか？
  --- その認識で正しいです．
- 文字で学習して記憶した用語も，他の人の言葉で聞くとより定着した気がするのですが気のせいでしょうか．
  --- 同じ内容を何度も勉強していると，だんだんと慣れてきて，だんだん分かってくる，ということはあると思います．その内容の説明として違う方法を試すと，また違った発見があるかもしれませんね．
10/19 (3) 代表的な理想グラフ (2)：二部グラフの補グラフ
- コメントをありがとうございました．
- Kőnig-Egerváryの定理の証明が難しかった。
  --- そうですね．私にとっても難しかったです．
- Kőnig-Egerváry (読めません。) の定理の証明に全然ついていけませんでした。
  --- 学部の『グラフとネットワーク』の講義では，もう少し直感的な証明 (アルゴリズムを使った証明) をしているのですが，そちらを紹介した方がよかったかもしれません．
- Kőnig-Egerváryの定理の証明(3)スライドで，命題の否定から導かれる性質も背理法で説明されて椅子から転げ落ちそうでした
  --- 背理法による証明は，分かりにくくなりがちですね．
- これを $S_e$ とすると，
  
  $S_e \triangle S_f$ がこうなりそうで少し分からない気持ちになってます
  --- $e$ の端点である $x$ は $S_e$ の要素になれないので (p.33の注)，上の図のような状況は起きないわけです．背理法で証明をしているので，ありえない状況を図にしなくてはならず，ややこしいですね．
- 今，この講義で二部グラフを扱っている理由は何ですか．聞きのがしているだけかもしれませんが...
  --- 聞きのがしは気にせず，質問して下さい :-)
  二部グラフを扱っている理由は，理想グラフの例として基本的なものだからです．なぜ基本的なのか，という理由は最終回で触れるかもしれません．
- スライドのτ(G)の定義 (p.17) が「最大要素数」となっていたのですが，おそらく「最小要素数」だと思います。
  --- ありがとうございます．修正しました．
- 早口言葉のようで発生するのが大変そうだなぁと思いました ("二部グラフの補グラフの～" のところ)
  早口言葉は得意ですか？
  --- 苦手です ;-)
- グラフ理論で使う概念がお互いに密接に関連していることを知らなかったので，おどろきがありました。
  --- そうですね．概念のつながりが分かると，いろいろなものの見方が変わってきますね．
- α，τ，νの文字にした由来はあるのでしょうか。νはmatchingのmから来ていると思いますが
  --- ちょっと調べてみたのですが，由来はわかりませんでした．
- χ(G)やω(G)，α(G)，τ(G)，ν(G)等，使われている文字に意味があるのか気になった．
  --- χについてはchromatic numberの「ch」のギリシア文字だと思います．
- 次はサティを流して欲しい
  --- またフランスですね ;-)
10/12 (2) 代表的な理想グラフ (1)：二部グラフと二部グラフの線グラフ
- コメントをありがとうございました．
- Gは二部グラフですか？
  --- はい，二部グラフです．
- 二部グラフは証明で扱いやすいと思っているので個人的には好んでいます．
  --- そうですね．次回も二部グラフの扱いやすさを味わいます．
- 辺彩色のアルゴリズムがわかりやすかった
  --- 自分で適当な例を作って，アルゴリズムの動きを追ってみるとよいと思います．そうすると，理解が深まります．
- 第2回にして，置いていかれてます。でも，がんばります．
  --- 割と，各回は独立です．細かい部分は分からなくても，流れは追えるようにして下さい．
- 同じ線グラフ
  --- その通りですね．一般的な法則は導けそうでしょうか？
- 学問に限らず，構築性の高いもの (小説，数学) が好きなので，講義の流れがすっきりしていると感じました
  --- まさに「アーキテクチャ」だと思いますね．計算機のアーキテクチャと言うときには，計算機を形作る様々なモジュールが結合して，全体としての機能を実現している様子を建築物になぞらえているわけです．
- K₅の線グラフ，予想以上に書き辛く...
  --- もとのグラフの辺の中点に線グラフの頂点を置くと，描きやすいかもしれません．
- DebussyのClaire de Lumを流して欲しい
  --- Claire de luneでしょうか．ちなみに，私は前奏曲が好きです．
10/5 (1) 理想グラフと組合せ最適化
- コメントをありがとうございました．以下のように掲載されます．
- 昨年も受講しましたが，諦めが早かったので取れませんでした．今年こそ頑張ってやっていく所存です．よろしくお願いします．
  --- こちらこそよろしくお願いします．
- 講義についていけるか分かりませんが取ろうと思います
  --- こちらこそよろしくお願いします．
- よろしくお願いしまあああす (Enterキー)
  --- 電車の中で読む数学記事は「Shorの量子アルゴリズム」ですね．(それが素因数分解，つまり，暗号解読につながってます．)
- 休み明けで眠気が消えません
  --- 金曜午後の授業なので，それも眠さの理由かもしれませんね．
- やせましたね。体調は大丈夫でしょうか。
  --- 体調はあまりよくないかもしれません．
- 離散数理工学が面白かった＆役に立ったので来ました。
  --- お役に立てたようで，うれしいです :-)
- BGMは流さないのでしょうか？
  --- リクエストが複数あれば流しましょう．
- Thanks for the comprehensive slide, extremely helpful.
  --- Thanks for the comment :-)
- 連続最適化と離散最適化が交わる場面が楽しみです．
  --- それはメインテーマの1つとなります．お楽しみに．
- 組合せ最適化と離散最適化は何か違うのでしょうか
  --- 組合せを選ぶ (例えば，有限集合の部分集合を選ぶとか) ことを考えるのが組合せ最適化で，離散的な集合から要素を選ぶことを考えるのが離散最適化です．組合せ最適化の多くは離散最適化問題として書くことができますが，連続最適化問題として書くこともできます．
- 計算理論に関して詳しくないので，NP困難性について補足してほしい．
  --- この授業に限っていえば，NP困難な問題というのは難しい問題である，とか，手に負えない問題である，とか，それぐらいの理解で十分です．NP困難性の説明をちゃんとしようとすると，それだけで3回ぐらい授業が必要になってしまい，それはこの授業の主眼ではありません．
- 元IBMから陸軍士官という変化が意外でした
  --- 陸軍士官学校に勤めている，というだけで，陸軍士官であるわけではないと思います．
- 完全グラフと理想グラフがそんざいして，片やperfect graphとなるのは訳語として妙な話に思えた．
  --- 完全グラフはcomplete graphで理想グラフはperfect graphですね．数学において「complete」という語は普通「完備」と訳されるので，complete graphも「完備グラフ」と訳されれば，perfect graphに対して「完全グラフ」という訳語を与えることができたかもしれませんが，訳語を充てた人が深く考えていなかったのかもしれません．
- 理想グラフという名前は本当に理想的な名前なのでしょうか？ (すごい名前です)
  --- 直前のコメントに関係していますが，日本語ではわかりにくい用語だとは思います．perfect graphは「完璧グラフ」とか「パーフェクトグラフ」と訳されることもありますが，「理想グラフ」が最も伝統的なので，この授業でもそれを採用します．また関連する概念にidealというのがあって，これもどう訳せばよいかよくわかりません．
- 2000年代以降の大成果はどんなものがあるのか気になった
  --- これを話すためには強理想グラフ定理の内容にちょっと踏み込む必要があるかもしれませんが，可能ならば，予備の日に取り扱ってみます．グラフの分解の話になります．