離散最適化基礎論
電気通信大学大学院情報理工学研究科情報・通信工学専攻
2014年度後学期
金曜4限 (14:40-16:10)
教室：西5-214
岡本 吉央
テーマ：組合せ最適化における線形計画法の利用
注意：内容は毎年変わります
ショートカット：講義資料 | コメント | 試験 | 公式シラバス | スケジュール | 過去の講義
講義資料
- 2/6 (13) 最近のトピック：拡張定式化
- 1/23 (12) 整数性ギャップ：上界
- 1/9 (11) 整数性ギャップ：下界
- 12/19 (10) 完全双対整数性：全域木 (2)
- 12/12 (9) 完全双対整数性：全域木 (1)
- 12/5 (8) 完全双対整数性：ネットワークフロー
- 11/28 (7) 完全双対整数性
- 11/14 (6) 双対問題の整数性
-
スライド (12/9更新) |
印刷用スライド (12/9更新) |
演習問題 (11/15更新)
- 演習問題6.3は発展問題とし，期末試験の範囲に含めない
- 11/7 (5) 双対性の幾何学
- 10/31 (4) 凸多面体の整数性
- 10/24 (3) 凸多面体の基礎
-
スライド (11/2更新) |
印刷用スライド (11/2更新) |
演習問題 (10/31更新)
- 演習問題3.5, 3.6, 3.7, 3.8, 3.9, 3.11, 3.12の提出締切は1週間延長
- 10/10 (2) 組合せ最適化問題と整数計画問題
- 10/3 (1) 線形計画問題と整数計画問題
コメント
- 2/6 (13) 最近のトピック：拡張定式化
- コメントありがとうございました．これで講義は終了です．あとは期末試験だけとなります．しっかりと準備をお願いします．
-
演習問題が難しい
---
ちょっと難しいぐらいがよいと思っています．一人でできるとはあまり思わず
，他の人と相談しながらやる，ということを想定しています．
-
面白かったです．ありがとうございます．
---
こちらこそありがとうございました．
-
約半年の間 ありがとうございました
---
こちらこそありがとうございました．
-
わかりやすく，おもしろい授業でした．ありがとうございました．単位とれるかどうかはわかりませんが試験がんばります．
---
はい，試験にはしっかりと準備して臨んでください．
-
授業全体を通して説明がとても丁寧で分かりやすかったです．テスト頑張ります．
---
ありがとうございます．試験はがんばって下さい．
-
テストがんばります
---
はい，よろしくお願いします．
-
半年間ありがとうございました．
---
こちらこそありがとうございました．
-
半年間，ありがとうございました！岡本先生の次回科目に期待してます
---
「離散最適化特論」はありませんので，ご了承ください．
-
最適化問題の関連性が広く色々な問題を考えなきゃいけないと思うと大変な分野だなと思いました．
---
別の言い方をすると，それが最適化という分野を面白くしているわけです．最適化というのは手法なので，その適用分野はどんどん広がっています．今後も広がっていくでしょう．
-
「離散最適化基礎論」というタイトルから基礎は難しいなと改めて思いました．興味深い内容が多かったのですが，最後の部分を学ぶにはいったいどれくらいの時間が必要なのかと果てしなく思いますが，少しずつ勉強していきたいと思います．ありがとうござました．
---
こちらこそありがとうございました．どんな分野でも最先端にたどりつくのは大変です．しかし，それを効率よくする方法の1つは，その専門家のそばにいて，常にそのような話題にひたることだと思います．ぜひ励行して下さい．
-
面白い授業ありがとうございました．スラック行列の分解は0の位置と値の並び方に法則性があるので計算できるかもと思いましたが授業時間内ではわかりませんでした．
---
こちらこそありがとうございました．あとでもよいので，わかりましたら教えて下さい．
- 1/23 (12) 整数性ギャップ：上界
- コメントありがとうございました．来週は休講ですので，お間違いのないようによろしくお願いします．
-
修論提出1週間前です．幸いです…
---
「幸いです」であってますか？ 「辛いです」じゃないんですね？ それならよかったです．
-
卒研つらいです．
---
あと1週間ぐらいなので，ラストスパートだと思って乗り越えて下さい．
-
卒論書くのが大変です．卒論がなくなったほしいです．
---
なくなりません ;-) 「書く」というのは自分の考えを伝えるコミュニケーションの基本なので，怠ってはダメです．しっかりと書いて，しっかりと提出して下さい．
-
テストがんばります
---
はい，よろしくお願いします．
-
難しいです．試験が心配です．
---
しっかりと準備してきてください．
-
試験の出題範囲に発展問題は入らないとのことですが，復習問題と追加問題ですと，やはり追加問題の方が多く出題されるのでしょうか．
---
それは分からないです ;-) あまりヤマを張らずに，準備してきてください．
-
暖房の真下あたりにいたせいか，いつもより眠かったです．テストのときは座る場所を考えなければいけないかもしれません．
---
そうですね．もしテストのときの空調の具合が悪かったら，そのときに挙手かなにかで私に伝えて下さい．
-
就活で途中の授業に出れなかったのが残念です．
---
資料は掲載していますので，それを見て自習をして下さい．質問があったらいつでもどうぞ．
-
デカ盛りが始まりましたね．
---
始まりましたねー．オススメのお店があったら教えて下さい．
-
卒論でも取りくんでみたんですけど上界と下界を改善するのって難しいですよね
---
そうですね．ただ，上界と下界が詰まっていない，ということは，そこに突っつきどころがある，ということなので，「研究がそこから始まる」と見れますね．アプローチすることは難しいかもしれませんが，やりがいはあります．
-
意外と未解決な問題が多くて驚きました．
---
割とあります．近似アルゴリズムの周辺は未解決問題だらけだといって言い過ぎではないです．講義でも紹介した『数学セミナー』の記事をぜひ参考にして下さい．
-
研究のトレンドが楽しかったです．再来週も楽しみにしています．
---
また違った角度からトレンドを紹介する予定でいます．お楽しみに．
-
最後のひとりごとはとても面白かったです．
---
ありがとうございます．大学院の授業なので，未解決問題もたくさん紹介したかったのですが，いままでできなかったのがよくなかったです．
-
電通大出身の先生がすごい賞をとっていてびっくりした。
---
あまり知られていないことかもしれないと思ったので，紹介しました．周りの人にも紹介して下さい．
-
電通大卒の方がすごい賞を取っているのはうれしいです．なぜ今まで知らなかったのか自分自身に疑問をもちます．
---
周辺の人があまりそのことを語らないのが原因だと思います．この機会に知って頂けてよかったです．
- 1/9 (11) 整数性ギャップ：下界
- コメントありがとうございました．センター試験準備で1/16はお休みとなります．
-
あと数回ですが今年もよろしくお願いします
---
はい，よろしくお願いします．
-
今年もよろしくおねがいします．
---
こちらこそよろしくお願いします．
-
冬休み復習しようと思ったのですが実際は何もしなかったです．
---
「冬休みあるある」ですね．よい休息ができたと思って，リフレッシュした気持ちを持って進めていきましょう．
-
新年から体のコンディション悪く全く集中できませんでした。次回はじっかり整えていきたいと思います。
---
ストレスでも免疫力は低下するそうです．体調管理には十分注意して下さい．
-
最近はついに部屋の暖房をいれてしまいました
---
私は11月ぐらいからいれてます．
-
今日はなぜか眠かった
---
暖房が熱すぎたかもしれないですね．
-
最初の「整数性ギャップの話をします」が「成績アップの話をします」に聞こえて少し期待しました．
---
期待させてしまってすみません．講義に出てるだけで成績アップがなされるわけではないので，注意して下さい．
-
許容解を見つけるのが難しそう
---
この辺りは実際，ちょっとした慣れが必要だったり，勘所があったりします．演習問題を通して身につけて下さい．
-
整数性ギャップの定義の $c\geq 0$ は何故ですか？ $c<0$ の場合は考えなくてもよいのでしょうか．
---
実を言うと，「整数性ギャップ」ということばの定義にはいろいろと異なるものがあり，その中の1つは $c<0$ の場合 (より正確には $c \geq 0$ でない場合) も考えます．ただ，この授業で扱っているような，組合せ最適化問題を整数計画問題として定式化したようなものでは，$c \geq 0$ の場合だけを考えるのが普通です．組合せ最適化問題では $c \geq 0$ となっていることが普通であり自然ですし，$c < 0$ の場合を考えると，目的関数値 (あるいは最適値) が負になることがあり，考える比の持つ解釈が困難になることもあるからです．
-
「(LP)の許容領域が整凸多面体⇒(P)の整数性ギャップ=1」の逆命題は成り立つのですか？
---
上の質問とも関係します．この講義で示した定義のもとで，逆は成り立ちません．しかし，$c \geq 0$ ではない場合も考えるように整数性ギャップを定義すると，逆が成り立ちます．
-
最大重みマッチングの整数性ギャップの下界は3/2が最も良いのでしょうか？
---
実は，3/2が最も良いです．つまり，任意のグラフに対して最大重みマッチング問題 (の講義で示した定式化) の整数性ギャップは3/2以下になります．
-
最大重みマッチングは効率よく解ける問題なのに下界が3/2 (1ではない) というのは定式化が悪いからなのでしょうか？ 「効率よく解ける問題 ⇒ 整数性ギャップが1となる定式化が存在する」となるのでしょうか？
---
質問が2つあるので，分けて答えます．(1) 講義で示した定式化以外に，最大重みマッチング問題の定式化で，その整数性ギャップが1であるものが存在します．その意味で，講義で示した定式化は悪い定式化です．(2) 「効率よく解ける問題 ⇒ 整数性ギャップが1となる定式化が存在する」ということが必ずしも正しいかどうかはわかっていません．しかし，整数性ギャップが1となる定式化 (つまり，(完全双対) 整数性を持つ定式化) を目指すことで，効率のよい解法が得られる，という傾向があり，それが研究に対する指針を与えています．
-
卒研がつらい
---
他の人もつらいので，いっしょになんとか乗り切りましょう．あと1か月ぐらいです．
- 12/19 (10) 完全双対整数性：全域木 (2)
- コメントありがとうございました．次回は1月9日です．
-
今年はどうもありがとうございました
---
来年もよろしくおねがいします．
-
今年のクリスマスが中止になりますように．
---
毎年来るので，中止にはなりません ;-)
-
冬休みは何をしますか
---
温泉にいきます．
-
おやすみなさい
---
おきてください．
-
今日難しすぎてつらかった
---
そうですね．今日は難しかったですね．
-
今日の内容はエグいです…。ポカーンってなりました
---
おそらく説明の仕方があまりよくなかったんだと思います．今回の内容が分かるように今までの講義で積み上げてきていたつもりだったんですけど，おそらくそれがうまくいってなかったのだと思います．
-
正直，今回はつらかったです…
---
私も変にテンションが上がって，つらかったです．
-
さむかったです．説明が大変そうでした．
---
大変そうにみえたのは，おそらく変なテンションのせいです．
-
かなり難しかったです．復習します．
---
はい，復習をお願いします．
-
証明難しかった…
---
私も講義の準備をするとき，何度かつまりました．簡単ではないと思います．
-
証明を追うのだけでも大変なのに，初めに証明した人はどういう気持ちで証明できたのかを聞きたいです．
---
どうなんでしょうね．私も聞きたいです．この辺りは線形計画問題に対する深い理解がないと証明を思いつくのは難しいかと思います．例えば，$x^*$の方はKruskalのアルゴリズムを使えばよいわけですが，$y^*, w^*, z^*$の方は線形計画問題に対する相補性定理をじっと眺めると，なるほどそうか，と思える部分があったりします．その辺りには，線形計画問題に対する理解が求められているわけです．
-
証明がおもしろかったです
---
いままで出てきたいろいろな道具が組み合わされていますからね．独特な味わいがあります．
-
今日のやつ テストに出たら 確定死
---
発展問題 テストにでない (五七五なので，七七にてお返しします．)
-
先生の説明は理論展開が難しくてもなんとなくついていけます．しかし，より易しい説明 (証明) を友人とかから聞くとついていけずに．，自分の理解力がないのでは，と最近悩んでいます．
---
こういうのは相性があると思います．また，自分自身が理解できるようにいろいろな知識をまとめ上げるのも重要だと思いますので，是非試してください．
- 12/12 (9) 完全双対整数性：全域木 (1)
- コメントありがとうございました．今回はだいぶ急いでしまった気がします．すみません．
- 前回の資料の79ページ目，$u \in S, v \not\in S$ではないとき，$z^*_{(u,v)}=0$を示す，と授業ではいいましたが，示す必要はありませんでした．制約から，$z^*_{(u,v)}\geq 0$が成り立っていて，それだけで十分です．失礼しました．
-
かなり内容が難しくなったように感じました
---
証明をするときに，例を一緒に出しながらやらないといけなかったですね．すみません．
-
証明が難しかった
---
私も難しいと思います．
-
混乱しそうになりました
---
私も混乱しそうになりました．
-
休憩をはさんでから早口になっていた気がします．
---
はい，私もそのような気がします．次は気をつけます．
-
証明がつらい
---
がんばりましょう．
-
途中ねむっちゃってすみません
---
こちらこそ眠らせてしまいすみません．
-
そろそろ冬休みなのでうれしい
---
お正月には凧あげて，コマをまわしてあそびましょう．
-
先生の服はパーカーが多いように思いますが，他の服は無いのですか？
---
良いところに気づきましたね ;-) ないといっても過言ではないほど，パーカーとフリースばかり冬場は着ています．
-
点線を引くやつ，今回は成功してよかったですね．
---
何気なくやったのですが，気付かれてしまいましたね ;-) 成功してよかったです．
-
金曜日は疲れがたまりますね．
---
週末にちゃんと疲れがとれないのがよくないのかもしれません．
-
最近朝寒くて外に出るのがつらいです
---
今週急激に寒くなりましたね．まだ雪が降らないだけよいかと思います．
-
面白いです．
---
ありがとうございます．
-
整数計画問題を定式化して緩和すると，線形計画問題にすることができるのでしょうか？
---
あまり細かいことをいうとややこしくなるので，それを避けてお答えすると，普通は線形計画問題にします．
-
最小費用全域木問題の完全双対整数性を持つ定式化が楽しみです
---
次回をお楽しみに．独特な雰囲気がでてきます．
- 12/5 (8) 完全双対整数性：ネットワークフロー
- コメントありがとうございました．次回は今回の続きからやります．
-
暖房がつくと，やはり眠くなってしまいますね．がんばって起きてます
---
水分を取ったり，キャンディをなめると，起きていられるかもしれません．
-
部屋があたたかくて心地良かったです．
---
そうですね．油断しないようにしないといけないですね．
-
今日はあたたかったです．
---
あたたかかった，ですね．日本語は難しいですね．
-
最近の演習問題が難しい
---
行列に関する細かい考察が必要ですから，難しく感じられるかもしれないですね．線形代数の復習も兼ねていると思って下さい．
-
「還る」は「かえる」と読み，「よみがえる」とは読まないようです．
---
ありがとうございます．日本語は難しいですね．「よみがえる」は「蘇る」ですね．
-
今日は回路を勉強しているようでした
---
そうですね．実際，流れの話題は回路と密接に関係していて，多くの研究者が電気回路，電子回路，論理回路の応用からグラフやネットワークの研究を始めた，という経緯もあります．あと，抵抗の逆数はたしかにコンダクタンスでした．忘れてしまっていて，失礼しました．
-
クリスマスは何をする予定ですか？
---
旅にでます
-
最近忙しくて演習問題を解く時間がとれないです．どう時間を作ればいいでしょうか？
---
忙しいと思っていると焦ってしまって時間がつくりにくくなるので，あまり忙しいと思わないほうがよいかもしれないですね．
-
演習問題について質問です．第n回の問題でn.m以外の問題は提出したのですが，n.mは後で提出してもよいのでしょうか？
---
提出していただいて構いませんが，私が確認する保証はありませんので，それについてはご了承ください．(時間があれば確認します．)
-
以前のスライドであっているのか分からなかったところです．
- 第7回P29の$A' \in \mathbb{Z}^{m \times k}$と$I' \in \mathbb{Z}^{m\times (k-k')}$の$m$は$k$でないでしょうか？
- 第6回P32の図の赤色の法錐が整数性を持たない気がします
---
どちらもご指摘通りです．ありがとうございます．直しておきます．
-
緩和したときのギャップに関することは知られているのでしょうか？
---
知られています．それは最後の方の話題になりますので，そこまでお待ちください．
-
証明がほとんどなくてよかった．
---
証明があることもよいと思えるようになって下さい ;-)
-
例があると分かりやすいですね．完全ユニモジュラ性の印象が強いですが，いままでの色々な概念を忘れそうです．
---
忘れないように，講義の中でも復習をしていきます．
-
仕事に役に立ちそうです．
---
ぜひ役立ててみて下さい．
- 11/28 (7) 完全双対整数性
- コメントありがとうございました．今回は証明が多くて大変でした．演習問題をやる時間がとれなくてすみませんでした．
-
二部グラフの接続行列は完全ユニモジュラの最後の方がよく分かりませんでした．$X$と$Y$の置き方によって$y^{\top}B'$の値は変わらないのでしょうか？
---
どの場合でも$y^{\top}B'=0$になります．置き方が変わると$y^{\top}$も$B'$も変わるのですが，$y^{\top}B'=0$となることは変わりません．
-
完全ユニモジュラ行列は制約が強すぎて使えなさそうな感じだと (定式化で現れにくそう) 思いました．来週楽しみです．
---
実は，自然な行列が完全ユニモジュラだったりするので，案外有用です．次回やります．
-
増えた課題が難しいです．
---
$A$の側と$-A$の側で選ばれる列がどのような関係を持っているのか，調べてみましょう．
-
証明がすごく難しかったです．
---
おそらく，説明がうまくなかったんだと思います．まだまだ改善の余地があります．
-
内容が難しくてほとんど頭に入ってこなかった
---
だんだんと難しくなってきてますが，次回からまた趣がかわるので，お楽しみに．
-
今回は演習問題が多くて大変そう
---
証明が多くてすみません．その一方で，証明が楽しめるようになると，本当に楽しくなります．
-
前回休んだので今回理解が追いつきませんでした．復習します．
---
はい，復習をお願いします．
-
今日は休憩があってうれしかった
---
すみません，私が疲れてしまっただけです．
-
教室が本格的に寒くなってきたので，暖房入れてほしいです．
---
たぶん入っていたと思いますが，弱かったのかもしれません．もし弱かったら，私に一言お願いします．
-
睡魔に打ち勝つ必勝法が知りたいです．
---
寝ている間は睡魔に襲われません．
-
ユニモジュラって言葉，なんとなくかわいらしいと思います．
---
ゴジラとかミニラみたいな感じでしょうか？ どなたか，ぜひキャラクター化して下さい．
- 11/14 (6) 双対問題の整数性
- コメントありがとうございました．今日は出席者が少なかった気がします．欠席した人は資料などをみて，自習をお願いします．
-
試験でHilbert基底を求めるときは，計算用紙が大変そう．
---
そうですね．計算用紙が方眼紙ならよいのですけどね．
-
「Hilbert基底を答えよ．」が期末にでるかと思うと…．時間が足りなくなりそうですね．
---
でるかどうかはわかりませんが，でるかもしれません．
-
数字が大きいと図を描くのが大変ですね．
---
そうですね．そのためにコンピュータがあるわけですね．
-
証明が難しいと感じた
---
用意していた図があまり説明に対して効果的でなかったのがよくなかったです．証明の意味することを図に描きながら考えると，割と素直な証明なのですけど，うまく説明できなくてすみません．
-
Hilbertは人名でしょうか？ 初めの方の疑問 (整数の方が難しい) がなんとなく分かってきて楽しいです．
---
人名ですね．David Hilbertです．なお，Hilbert基底という用語は数学の中でもその部分分野によって違う意味を持つ用語なので注意が必要です．
-
分かれば楽しいです．
---
ということは，分かった，ということですか？
-
今は授業が始まる1時間くらい前から復習問題を解いているのですが，復習は授業が終わったその日にやった方がいいでしょうか？
---
どちらでもよいと思います．その日のうちにやれば，記憶がフレッシュなときに行う復習なので，記憶として定着しやすいかもしれません．また，授業が始まる前に復習をすれば，授業の事前準備となるので，授業の内容が理解しやすくなると思います．
-
数論だと自然数は1から始まり，それ以外だと0から始まるのは本当ですか？
---
1から始まる分野と0から始まる分野があるというのは本当です．それが数論とそれ以外という形に分かれているのかどうかは知りません．計算機科学 (コンピュータサイエンス) では0から始まることが多いと思います．
-
今日は「休憩を取るということは私がお茶を飲みたい〜」というくだりがなかったような…
---
いつもあるわけではないです ;-)
-
演習の時間に前回の演習のまちがえたところの質問をしてもいいですか？
---
はい，もちろん大丈夫です．ぜひ質問して下さい．
-
次回が楽しみです．
---
1週あきますので，お間違えないように．
-
調布祭の空き時間になんとか理解できるように努めます．
---
はい，復習して臨んで下さい．
- 11/7 (5) 双対性の幾何学
- コメントありがとうございました．
-
数学の美しさ？みたいなものが見れて面白いです．
---
私は出来る限り，いろんなものを理解するときに，図を介して理解しようと努力しています．そうすると直感も湧きやすいですし，説明もしやすくなるからです．実際図に描いてみると，その美しさも実感しやすくなると思います．
-
法錐，法扇から話が難しくなった気がするのでもう少しゆっくりでもよかった．
---
確かにそうでしたね．今日はペース配分にちょっと失敗した気がしました．
-
法扇の考え方は面白いと思いました．何か他にも使えそうですね．
---
法扇は凸多面体を理解するときによく使われる重要な概念なので，最適化以外にも，凸多面体を使って問題を記述できるときには，よく出てきます．
-
法扇が$\mathbb{R}^n$を埋め尽くすということ，パズルのようで面白かった．
---
そうですね．「埋め尽くす」というのはタイリングと呼ばれますが，いろいろなパズルやいろいろな計算問題がそこから生まれてきています．
-
双対問題がどういうものか今まではピンときていなくてイマイチ好きじゃなかったので今回の講義で直感的に理解できて良かったです．
---
私のことは嫌いになっても，双対問題のことは嫌いにならないでください．
-
感動しました．
---
ありがとうございます．
-
前回の内容よりは理解できたと思う
---
前回の内容も大事ですので，復習をしておいて下さい．
-
第三回の事実として，凸多面体の面の面は凸多面体の面と言っていたのですが，これは再帰的に成り立つのでしょうか？
---
再帰的，ということばが何を意味するのか理解することが難しいですが，「面である」という関係は推移的です．つまり，AがBの面で，BがCの面ならば，AはCの面です．(これは講義スライドにも (違う記号で) 書いてあります．) そのため，AがBの面で，BがCの面で，CがDの面ならば，AはDの面です．実際，「面である」という関係は反射的でもあり，反対称的でもあるので，半順序関係になります．
-
出来れば類似例題も多く解説して欲しいです．
---
何の類似例題なのか，分かりかねますが，今回は例が少なかったと思うので，次回は気をつけます．
-
ここ2回レポートを出せていません．内容も難しくなってきているので次回からは絶対に出すようにします．
---
はい，よろしくお願いします．
-
だんだん演習問題がわからなくなってきて困ってます…．
---
ぜひ質問して下さい．何を質問したらよいか分からなくなる，という状況になる前に手を打つことが大事かもしれません．
-
新出単語が多くてなかなか覚えられそうにないのですが，これからも「法錐」のように新しい概念は出てきますか？
---
毎回出てきます．覚えようとせず，忘れたときに調べて思い出せるようにしておければ十分です．
-
ベクトルは太字で書いた方がわかりやすいですけど太字で書くとめんどくさいですよね．私は太字にするのを忘れて太字と太字でないのが混在してます……
---
確かにそうですね．特に，黒板に書くときには，太字をどのように書けばよいのか，ということを考えると，あまりにも汚くなりすぎて，嫌になることがあります．
-
最近やることが多くて大変です
---
暇で暇で困ってしまう，というよりはいいと思います．やるべきことを整理して，1つずつこなしていきましょう．
-
調布祭も講義やりましょう
---
研究室公開を金曜日にもやるので，講義はしません ;-)
- 10/31 (4) 凸多面体の整数性
- コメントありがとうございました．
-
前回，線形包の話題のとき，「原点と$(-1,0,2)^{\top}$の線形包」の「原点と」が間違いと言っていましたが，更新された資料では直っていません．どちらが正しいのかな，と思いました．
---
すみません，訂正し忘れました．修正しておきます．
-
アフィン包のベクトル$p$の値が合わず苦戦しました．プリントミスでほっとしました．
---
間違ってばかりですみませんでした．これは既に訂正してます．
-
他の講義で出している英訳対応表はこの講義ではないのでしょうか？
---
対応表はなく，講義スライドの中で英語を挙げるはずなのですが，何故か今年度は挙げるのを忘れています．次回から気を付けます．
-
かなりいっぱいいっぱいです．がんばります．
---
難しくなってきてますね．次回も多面体のはなしが続きますので，復習をしてきてください．
-
難しくなってきたので，復習をしっかりします．
---
演習問題を通して復習をしてみて下さい．
-
よく理解するために復習します
---
演習問題を通して復習をしてみて下さい．
-
次からレポート出します…．
---
はい，よろしくお願いします．
-
新しい話にすすむたびに新しい用語が増え，まえにでてきた用語をわすれ，それを思いだそうとすると新しい用語を忘れるというループがつらいです
---
用語は覚えようとせずに，調べてすぐに思い出せれば十分です．気楽でいてください．
-
線型の復習をして，ベクトルや空間の表現に慣れたいと思います．
---
そうですね．線形代数はいろんなところに出てくるので，慣れておくのは重要だと思います．
-
模型が見てみたいので，次回忘れなければ持ってきてくれるとうれしいです．
---
はい，忘れなければ持ってきます．
-
PとかLPが出てくると，条件式の部分が理解し難いことがあるので，図があるのはとてもありがたいです
---
図は大事なので，スライドにおいては重視してます．私がスライドを使う理由の1つは図をたくさん描けることです．黒板に図を描くのは難しいですし，それを皆さんがノートにとるのも難しいと思います．そのため，スライドに図を描いておいています．
-
図を色でわけて表現してる部分がよく見られたので，次回からはカラーで印刷してきます
---
本来は，カラーで印刷しなくても分かるようにスライドを作るべきなのですが，それがちょっと大変なので，いまは横着をしています．すみません．
-
面という単語がいっぱいいでていた
---
そうですね．面はとても重要で，とくに頂点とファセットが重要なので，今後もいっぱいでてきます．
-
先生の時々出てくるドヤ顔が気になります．
---
あれ，自覚していませんでした．それでは，あまり気にしないでください ;-)
-
ようやっとスッキリしました．整凸多面体重要ですね．
---
ようやく追いつきましたので，次回からは少しスムーズになるはずです．
-
調布祭で岡本先生の研究室に遊びに行きます
---
はい，ぜひどうぞ．
- 10/24 (3) 凸多面体の基礎
- コメントありがとうございました．1週間空いたので，復習をしっかりお願いします．
-
演習の締切を1週間ではなく2週間にのばせないでしょうか
---
すみませんが，1週間のままにさせて下さい．
-
空間の話は難しい
---
この辺りに慣れていくことがこの講義の主題となっていきます．
-
空間が入ってきて難しそうになってきた
---
3次元の絵を描くのはなかなか大変ですが，実際に扱うのはもっと大きな次元になります．これも今後補足していきます．
-
私にとって新しい概念なので，難しいですががんばります．
---
はい，しっかり復習をして下さい．
-
新しく登場する定義があるとき，わかりやすい説明があるので非常に理解しやすい
---
ありがとうございます．それは心がけていることなので，今後も続けていきます．
-
板書での補足はとてもありがたいので，これからもお願いします．
---
はい，今後もそうしていきます．
-
はじめて聞く定義ばかりで大変でした
---
そうですね．定義ばかりで大変なのですが，使っているうちにだんだん慣れていくので，復習しながら身につけていって下さい．
-
説明はすごく分かりやすいですが，プリントのミス記載が，復習する時に混乱する原因になりそうなので，できるだけ減らしてほしいと思います．
---
すみません．意図的にミスをしているわけではないので，許して下さい．もし見つかったら教えてください．
-
進行が早くなるので構成を調整してください
---
次回に扱うべき内容はそれほどないはずなので，おそらく追いつけます．
-
チョークを立ててガガガ...って点線を書くやつ，難しいですよね...．私も練習した覚えがあります．
---
そうです！それがやりたかったんです．まっすぐ (鉛直方向) なら割と成功するのですが，今回はななめだったので断念しました．
-
アフィンとはどういう意味ですか？
---
アフィンは英語でaffineですが，その名詞形affinityは辞書によると「親和性」，「親近感」，などとあります．なぜアフィン部分空間と呼ばれるのか，知らないのですが，affineは無理に訳さず，カタカナのまま「アフィン」と訳すことになっています．英語での発音は「アファイン」のようになりますが．(注意：普通の文脈でaffineの名詞形はaffinityですが，数学においてaffineの名詞形として使われる単語はaffinenessです．アフィン性と訳します．)
-
アフィン空間という名前の由来はあるのでしょうか
---
上と同じく，すみませんが，知りません．
-
凸多面体の二通りの定義がなかなか面白かった．H表現は自明でしたが，V表現という手法は興味深かったです．
---
そうですね．このように二通りの表現があるということがいろんな分野に現れていて，その分野を豊かにしています．
-
V表現のI=conv({a,b})のconvは{a,b}の凸包という解釈で当っているでしょうか．
---
はい，その通りです．convという記法を定義し忘れていたので，次回，もう一度補足します．
-
最小費用全域木問題の01整数問題としての定式化1のGの閉路の制約は取り除くことができると思いますが，どうでしょうか．(許容解は全域木になるとは限らないのですが，最適解は全域木となっていると思います．)
---
その通りですね．「最小化」なので正しいと思います．実は「最大費用全域木問題」も効率よく解けるのですが，その場合は閉路の制約が必要になります．
-
全域木を定式化していくところがよく分からなかったので復習したいと思う．
---
はい，よろしくお願いします．
- 10/10 (2) 組合せ最適化問題と整数計画問題
- コメントありがとうございました．次回は休講です．
-
学内のパソコンしかスライドは印刷できないのでしょうか
---
どこからでも閲覧できますし，印刷できると思います．少なくとも，私は学外から見られないようにはしていませんので，もし印刷できないようでしたら，再度ご連絡下さい．
-
スライドをもっと早くネットにupしてくだあると助かるのですが，無理でしょうか
---
できる限り努力しますが，確約できるのは当日の昼12:00です．それより早く掲載される場合もありますが，そのときはtwitterでお知らせします．
-
スライドを印刷して持参するのを忘れました．気をつけます．
---
はい，気をつけて下さい．
-
まちがえて第1回を印刷してしまった
---
第1回の残った部分をやったので，「間違っている」とはいいきれないですね．
-
今までのレポートで提出しなかったものをcheckしてもらう為にオフィスアワーで持っていっても大丈夫ですか？
---
レポートの提出は期限内ならば大丈夫です．レポートでない場合，確認のために質問をしてもらうのはいつでも問題ないです．
-
わからなくなったら聞きに行くのでよろしくお願いします．
---
はい，よろしくお願いします．
-
早くもキツクなってきました．がんばりたいと思います．
---
まだ序盤ですので，全く分からない，という状況になる前に質問して下さい．
-
とても頑張りたいです．
---
私も，とても頑張りたいです．
-
前回の演習問題が解けなかった
---
解けない場合は質問して下さい．「質問しないのは損」だと思ってもらってよいです．
-
今日の内容をしっかり理解できたと思う
---
演習問題を通して復習して下さい．
-
スライドが非常に分かりやすく，理解しやすかったです．
---
スライドだけ見てると，何だかわかった気になってしまうので，それをちゃんとわかったというところまで持っていけるようにしてみて下さい．
-
追加問題の文字が多くてわかりにくかったです
---
確かにそうだと思います．この部分は記号を使えばもっと分かりやすく書けるのですが，そうしてしまうと，定式化が簡単になるので (つまり，演習問題が簡単になりすぎるので)，あえて分かりにくく書いているのだと思って下さい．
-
講義の時間配分は増加関数のようにして欲しいです．後ろの方で時間がなくなるのはツライです．
---
後ろの方は無理に速めるのではなくて，時間がなくなったら潔く次回に回すので，あまり気にしないでください．
-
「弧」の字は跳ねない気がします．
---
たしかにそうですね．ありがとうございます．
-
カッコの話はちょっとだけためになった．
---
この辺りは案外重要だと思ってるので，機会があるときには話をしています．ただ，話そうと思うたびにいろんなことを忘れていることにも気づくのですが．
-
⟦ ⟧：二重各括弧，〖 〗：隅付き括弧 (白)
---
そうですね．ありがとうございます．
-
結局 $\langle$ $\rangle$ の意味ってなんだったのか？
---
数学では，内積を表すときによく使います．内積というか，より正確にはduality pairingなのですが，内積だと思ってもらってよいです．
-
どうも金曜の午後はやる気が出ません．何か良い方法はありますか？
---
その後のビールを思い浮かべる，とかどうでしょう．
-
前期の講義で01整数線形計画問題を取り扱っているものがあったので復習になった．
---
同じことが何度も出てくるというのは，それが重要である，ということなので，復習になったのならよかったと思います．
- 10/3 (1) 線形計画問題と整数計画問題
- コメントありがとうございました．以下のように掲載されます．
-
これからよろしくお願いします
---
はい，こちらこそよろしくお願いします．
-
初めて岡本先生の講義を受講しましたが，聞いていて面白いです．履修しようと思います．
---
ありがとうございます．よろしくお願いします．
-
今日は暑かった
---
そうですね．突然暑くなったので，体調を崩してしまいました．
-
教室が暑かったです
---
冷房を入れていたのですが，あまり効かなかったですね．
-
部屋が暑い
---
冷房が効かないので，来週も暑かったら窓を開けましょう．
-
２徹明けで眠気に勝てませんでした．
---
お疲れ様です．次回はしっかりと寝てきてください．
-
講義中学生のお茶タイムはOKですか？
---
はい，OKです．自由に飲んでください．ただ，食事はやめてください．
-
演習問題がんばって解いてきます
---
演習を重視してますので，ぜひやって下さい．
-
模範回答がない理由が具体的によく分かりません．
---
いろいろと理由はあります．(1) 自分で考えぬくことが重要だから．(2) 模範回答のようなものがあると，それだけで勉強をした気になってしまう傾向があるから．(3) 私は模範ではないから．といった感じです．
-
回答には主に何を見ているのか知りたいです．
---
論理展開です．式変形や推論が論理的に行われているか，用語や日本語が正しく使われているか，というところを見ています．
-
数理計画法は学んだことがないですが理解できるようにがんばりたいと思います．
---
数理計画法に関する基礎的な部分や今回扱った内容で十分になるようにこの授業は組み立てていくことになりますが，より深く理解しようとする場合には，『数理計画法』の講義で扱う内容が理解できていると助けになります．その意味では，数理計画法を学んでいなくても，今回扱った内容が分かれば大丈夫です．
-
数理計画，線形計画法，共に講義を履修していないのですが，授業内容を理解できますでしょうか？
---
上の回答と同じく，今回扱った内容ぐらいで大丈夫なはずです．その意味では，今回扱った内容を十分復習して下さい．
-
数理計画法の内容を思い出せてよかったです．毎回レポートを出せるよう頑張りたいです．
---
『数理計画法』を履修した人にとっては，その内容を復習しておくと理解が深まるので，ぜひお願いします．
-
『数理計画法』の講義の要点がきれいにまとまっていて，分かりやすかった．
---
次回以降も『数理計画法』で扱った内容が少し出てくるかもしれませんが，数理計画法の講義を取っていなくても分かるような構成にしていきます．
-
忘れていた部分の復習から入ったので，わかりやすく，おいてきぼりにされなかったので，良い授業でした．
---
ありがとうございます．次回もよろしくお願いします．
-
話し方が早く聞き取りづらい時がありました．もう少しゆっくり話していただけると聞きやすいかもしれません．おもしろい授業でした．
---
ご意見ありがとうございます．今回は時間が足りなくなりそうになって急いでしまいました．気をつけます．
-
資料が分かりやすかった．
---
ありがとうございます．資料を見ただけでは理解できないと思うので，講義に出席して，演習問題を解いて，理解していって下さい．
-
この授業への理解を深めるためには，何を重視して復習するべきですか？
---
演習問題を解くことが一番の復習だと思います．復習問題をぜひやって下さい．何も参照しないで復習問題が解けるようになれば，かなり理解が深まっていると思ってよいと思います．
-
無限の方が怖いのに (許容解がたくさん)，整数性を加えた方が (許容解が有限) の方が恐くなるのは，現実の直観に反している気がして面白いです．
---
その通りだと思います．直観と合わないことが数学ではよく起きるので，気をつけないといけませんね．
-
整数化問題の例で，$x_1=1$，$x_2=1$と$x_1=3$，$x_2=0$は最適解とありました．線形問題のときは方向ベクトル$\begin{pmatrix}1\\2\\\end{pmatrix}$にちかい$x_1=6/7$，$x_2=10/7$を最適解としましたが，$x_1=3$，$x_2=0$の方向は方向ベクトルに近くないので，整数化問題の最適解のときは方向ベクトルは関係ないのでしょうか．
---
整数計画問題，線形計画問題ですね．ベクトルに近いかどうか，というのは直感の話なので，本来は実際に目的関数の値が大きいのかどうかを考える必要があります．$x_1=3$，$x_2=0$のとき，$x_1+2x_2 = 3$であり，$x_1=1$，$x_2=2$のときも$x_1+2x_2 = 3$であるので，どちらも同じ目的関数値を持っているわけです．
-
線形計画問題で，最適解が複数ある場合はあるのですか？
---
あります．例えば，
「maximize $x_1$ subject to $x_1 \geq 0, x_2 \geq 0, x_1 \leq 1, x_2 \leq 1$」という線形計画問題では，$x_1=1$であり，$0\leq x_2 \leq 1$を満たすベクトル $(x_1,x_2)$はすべて最適解です．
試験
- 期末試験により成績評価を行いました．
- 日時：2月13日 (金) 14:40〜16:10 (第4時限)
- 教室：西5号館 214号室 (普段，講義を行っている教室と同じ)
- 出題範囲：第1回の最初から第12回の最後まで
- 出題形式：
- 演習問題と同じ形式の問題を6題出題する．
- その中の4題は演習問題として提示されたものと同一である．(ただし，「発展」として提示された演習問題は出題されない．)
- 全問に回答する
- 配点：1題20点満点，計120点満点 (成績において，100点以上は100点で打ち切り)．
- 持ち込み：A4用紙1枚分 (裏表自筆書き込み) のみ可
- 試験問題
- 得点分布
- 成績報告では，この素点に対して，「min{素点, 100}の小数点以下切り上げ」を用います．
- 得点分布では，未受験者を含めていません．受験者数は14で，Aは13人，Bは0人，Cは0人，Dは1人です．(大学院にSはないので，注意を．)
- 得点掲示 (辞書順に並べています)
| 1725mmm | 85 |
| 24056 | 108 |
| 3jt91 | 106 |
| fbu3g | 99 |
| kogk1 | 92.5 |
| KXY112 | 120 |
| miso-syake | 100 |
| PmSPh | 110.5 |
| sdsbs | 97 |
| wipwip | 91 |
- 念のためお断りしますが，拝んだり頼みこまれたりしても成績が上がることはありません．
- 講評
- 総評：よくできていました．簡単な問題を出題したわけではないと思っていますので，よく準備をして臨んでいただけたのではないかと思います．一方，試験を受けたが不可になってしまった方が1名いらっしゃいますが，答案を見た限り，準備が不足していたのではないかと感じました．
- 問題1：組合せ最適化問題を整数計画問題として定式化する問題．演習2.5と同じ問題．変数とするべきもの，制約とするべきものが明確に特定できていない答案が少なからずありました．
- 問題2：凸多面体と線形計画問題の関係の問題．演習4.1と同じ問題．講義でも扱ったものなので，よくできていました．質問をしていることの逆を解答している答案もありましたが，それには点がついていません．
- 問題3：Hilbert基底を答える問題．演習6.5の類題．よくできていました．x座標とy座標が逆になっている答案もありましたが，反転させれば正しくなることを考慮して，満点の半分を与えました．
- 問題4：全域木の性質に関する問題．演習10.1と同じ問題．これも講義で扱ったものなので，よくできていました．「1⇒2」と「2⇒1」の両方を証明する必要があります．
- 問題5：完全ユニモジュラ行列に関する問題．演習問題8.5と同じ問題．「最小のものを見つけよ」と聞いているので，なぜ最小であるのかという説明が不足しているものは減点しています．
- 問題6：整数性ギャップの下界を示す問題．演習11.5，11.6と似た問題．これは，すんなりできている人はすんなりとできていて，苦しんだ人は苦しかった問題だったようです．整数計画緩和に対して与えているベクトルがその許容解になっていない答案もありました．また，「1よりも真に大きい」ということと「1以上」は異なるので，「1以上」であることを証明しただけでは点を与えていません．
公式シラバス
こちらをご覧ください
スケジュール
- 10/3 (1) 線形計画問題と整数計画問題
- 10/10 (2) 組合せ最適化問題と整数計画問題
- 10/17 休講 (国内出張)
- 10/24 (3) 凸多面体の基礎
- 10/31 (4) 凸多面体の整数性
- 11/7 (5) 双対性の幾何学
- 11/14 (6) 双対問題の整数性
- 11/21 休講 (調布祭)
- 11/28 (7) 完全双対整数性
- 12/5 (8) 完全双対整数性：ネットワークフロー
- 12/12 (9) 完全双対整数性：全域木 (1)
- 12/19 (10) 完全双対整数性：全域木 (2)
- 1/9 (11) 整数性ギャップ：下界
- 1/16 休講 (センター試験準備)
- 1/23 (12) 整数性ギャップ：上界
- 1/30 休講 (海外出張)
- 2/6 (13) 最近のトピック
- 2/13 期末試験
過去の講義
[Teaching Top]
[Top]
okamotoy@uec.ac.jp
