離散最適化基礎論

岡本 吉央

テーマ：整数計画法

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

ショートカット： 講義資料 | 演習問題 | コメント | 試験 | 公式シラバス | スケジュール | 参考文献 | 関連リンク | 過去の講義

実施形態

学生の皆さんの受講形態としては，「教室で授業を受ける」形を推奨しますが，自宅や研究室等からオンラインでリアルタイム受講しても構いませんし，オンデマンド型の受講をしても構いません．ただ，オンデマンド型では，質問をする機会が限られることにご注意ください．

内部シラバス (学務情報システムから見ることができるシラバス) で，Google Classroomのコードを確認し，参加をしてください．

講義資料

• 1/24 (14) 前求解
  • スライド (1/25修正)
  • 講義動画
• 1/17 (13) ラグランジュ緩和 (2)：最適ラグランジュ緩和
  • スライド (1/19修正)
  • 講義動画
  • 補足動画
• 1/10 (12) ラグランジュ緩和 (1)：原理
  • スライド (1/10修正)
  • 講義動画
• 12/20 (11) 列生成法
  • スライド (12/20修正)
  • 講義動画
• 12/13 (10) 妥当不等式の追加
  • スライド (12/14修正)
  • 講義動画
  • 補足動画
• 12/6 (9) 切除平面法
  • スライド (12/6修正)
  • 講義動画
• 11/29 (8) 分枝限定法
  • スライド (12/6修正)
  • 講義動画
• 11/22 (7) 整数計画モデリング (3)：離接計画
  • スライド (11/29修正)
  • 講義動画
  • 補足動画
• 11/15 (6) 整数計画モデリング (2)：より複雑な問題
  • スライド (11/29修正)
  • 講義動画
  • 補足動画
• 11/8 (5) 整数計画モデリング (1)：組合せ最適化問題
  • スライド (11/29修正)
  • 講義動画
• 11/1 (4) 線形計画緩和
  • スライド (11/8修正)
  • 講義動画
• 10/25 (3) 線形計画法の復習 (2)：単体法と双対定理
  • スライド (11/8修正)
  • 講義動画
  • 補足動画
• 10/11 (2) 線形計画法の復習 (1)：線形不等式系と凸多面集合
  • スライド (10/11修正)
  • 講義動画
• 10/4 (1) 整数計画法と線形計画法
  • スライド
  • 講義動画
  • 補足動画

• 演習問題 (1月13日掲載)

• 1/24 (14) 前求解
  • 14回の講義ありがとうございました。
    -- はい，こちらこそありがとうございました．
  • 半年間ありがとうございました。非常に勉強になりました。
    -- この講義形態 (講義室とZoomのハイブリッド) を試したのは初めてで，私も勉強になりました．ありがとうございました．
  • 本日の講義ありがとうございました。
    -- こちらこそありがとうございました．
  • 講義ありがとうございました。
    -- こちらこそありがとうございました．
  • 講義ありがとうございました。試験勉強を頑張ります。
    -- はい，試験の準備はしっかりとしてきてください．
  • 最後の授業ありがとうございました。試験も頑張ります
    -- こちらこそありがとうございました．
  • 半年間の講義ありがとうございました。整数計画法のモデリングと解法について学ぶことができてよかったです。
    -- ありがとうございました．整数計画法はいろいろな場面で使えるはずですので，ぜひ使ってみてください．
  • 講義ありがとうございました．期末試験もよろしくお願いします．
    -- こちらこそありがとうございました．
  • (まだテストは残ってますが)半年間の授業ありがとうございました。24ページにおいて双子の定義が他の文献では異なることがあると書いてありましたが、用語の定義の内容が文献によって異なることは他でも起こりうるのでしょうか。
    -- 用語の定義の内容が文献によって異なることは頻繁に起こります．そういうことがあるので，皆さんも，論文に限らず文書を書くときには，用語の定義を (読者が「知っている」ということを仮定せずに) しっかりと行う必要があると思ってください．皆さんが念頭に置いている定義と読者が思い描いている定義が異なることはありえます．よほど標準的である場合を除いて，定義は必ず行ってください．
  • 今学期ありがとうございました。研究のヒントになりそうな内容で大変勉強になりました
    -- 授業の内容が皆さんの研究や生活に活かせられれば，私自身のこの授業における目標が達成できることになります．ぜひ活かしてみてください．
  • 半年間ありがとうございました。研究でネットワークを扱う際にグラフを用いるので何かしらの形で本授業の知識を活かしたいと思います。。
    -- はい，ぜひ実践してみてください．活きた部分があったら，ぜひ教えてください．:-)
  • ソルバーを利用して前求解の威力を実証してくださって非常に分かりやすかったです．14回の授業を通して授業内容だけでなく問題に対してどのように考えていくかも学ぶことができました．ありがとうございました．
    -- どんな技術にも，それを支える理論や思想や哲学があったりします．この授業ではそこまで踏み込めなかったように思いますが，皆さんが何らかの学びを得られたとすれば，私はとてもうれしいです．
  • 14回の講義ありがとうございました。毎年テーマが異なるということで、来年も受講しようと思います。
    -- ぜひぜひ．お待ちしています．
  • 講義の中でも、ビンパッキング問題などは問題特有の性質を使うことによって求解が楽になることがを紹介していただいたのですが、ソルバー側はどのようにしてこういった問題を見分けて前求解などを行っているのでしょうか？
    -- ソルバーが問題を見分けることは，いまの技術においてできていません．現状では，人間がどんな問題なのかソルバーに教えてあげている形になっています．例えば，いま解きたい問題がビンパッキング問題なのだということを性質として用いて，ソルバーのパラメータを調整したり，ソルバーが使うアルゴリズムを変えるということを人力で行っています．ソルバーのパラメータ調整やアルゴリズム選択は，別の最適化問題となり，それを解くための手法がいくつもでてきています (ここで，何をもって「解く」と呼ぶのか，という課題は保留しています)．問題設定としては機械学習のような雰囲気 (未知の入力に対してよい応答をするようにしたい，という動機) を持つものになります．
• 1/17 (13) ラグランジュ緩和 (2)：最適ラグランジュ緩和
  • 今週もとてもわかりやすかったです。最後までよろしくお願いいたします。
    -- はい，よろしくお願いします．
  • 本日の講義ありがとうございました。
    -- こちらこそありがとうございました．
  • 本日の講義ありがとうございました
    -- こちらこそありがとうございました．
  • わかりやすかったです。ありがとうございました
    -- ありがとうございました．
  • テスト勉強頑張りたい。
    -- はい，しっかりと準備をしてください．
  • 劣勾配と劣微分(と劣勾配法)あたりの説明がまだよく理解できなかったため復習しておきたいです。また、演習問題を作成してくれたのはありがたいですが、用語説明問題以外の部分の答えをつけていただくのは難しいでしょうか。
    -- すみませんが，用意している答えはありません．演習問題がそのまま，あるいは，それに似た問題が試験に出題される可能性もありますので，そのつもりで準備をしてください．
  • しっかり理解できてない部分が多いので復習する。
    -- はい，質問がありましたら，ぜひお願いします．
  • 劣勾配法アルゴリズムでは、劣勾配の選び方とステップサイズの２つのパラメータがあるといわれてましたが、実際に使うときにはどちらのほうが決めるのに苦労するのでしょうか？
    -- ラグランジュ緩和を対象とするときには，講義の内容 (補足動画の内容) から，劣勾配はすぐに求められることが分かります．そのため，ステップサイズの選び方の方が問題になることが多いような気がします．どちらかというと，劣勾配は，解こうとしている問題の性質や構造を用いて選ぶことが多く，その部分は解くべき問題を解く前にじっくりと考察することで決めていくような気がします．一方，ステップサイズの方は「実際にやってみないと分からない」ことが多く，試行錯誤を繰り返して決めることになっている気がします．
  • 普段信号処理を勉強しているので，劣勾配法については親近感が湧きました．今回の授業もとても分かりやすかったです．ありがとうございました．
    -- 親近感をもっていただけたのはありがたいです．授業の中でも話しましたが，信号処理や画像処理は最適化問題の宝庫です．この授業の内容を今後の研究や生活に活かせていただけると，授業を担当している私としてはとてもうれしいです．
  • 最強ラグランジュ緩和の求め方の具体例を見て理解が深まりました。
    -- 本当は，劣勾配法の動きも授業の中で紹介できればよかったのですが，その時間をとることはできませんでした．ぜひ，適当な例を作って試してみてください．
  • 劣勾配、劣微分などの劣というのはどのような意味なのでしょうか?
    -- 不等式が「劣」のイメージです．今日の授業では凸関数に対して劣勾配を定義していますが，その場合，$x_0$ に近い $x$ に対して不等式 $s^{T}(x-x_0) \leq f(x)-f(x_0)$ が成り立つとしても，定義としては等価になります．一方で，普通の「勾配」は $x_0$ の近くで $f$ を線形近似したとき，$s^{T}(x-x_0) \approx f(x) - f(x_0)$ となるような $s$ のことであると言えます (Taylor展開を思い出してください)．この「$\approx$」(あるいは極限における「$=$」) を「$\leq$」という不等式で置き換えているのが「劣」のイメージです．
    一方で，不等式を「$\geq$」とした場合，優勾配 (supergradient) と呼ぶことがあるようです．
  • ニュートン法は勾配法の一種でしょうか。
    -- 結論からいうと，ニュートン法は勾配法の一種とは考えないことが多いです．
    ニュートン法は，関数 $f$ に対して，$f(x) = 0$ を満たす $x$ を見つける問題に対する数値解法であると見なすことが多いです．その際，$f$ の勾配 (1次微分) の情報を利用します．ニュートン法を最適化に応用するとき，例えば，凸関数 $f$ の最小値を見つけるために使うときには，導関数 $f'$ に対して，$f'(x) = 0$ を満たす $x$ を見つけることをニュートン法で行う，というステップを踏みます．このとき，$f'(x) = 0$ をニュートン法で解こうとすると，$f'$ の微分，つまり，$f''$ ($f$の2次微分) の情報を使うことになります．
    勾配法自身は，たいてい，$f$ と $f'$ だけが分かれば実行できるものとして理解されます．そのため，$f''$ を必要とするニュートン法は勾配法と見なさないことになります．
• 1/10 (12) ラグランジュ緩和 (1)：原理
  • コメントありがとうございました．本年もよろしくお願いします．
  • あけましておめでとうございます.残り少ないですが本年もよろしくお願いします.
    -- 本年もよろしくお願いします．
  • 本日の講義ありがとうございました。
    -- こちらこそありがとうございました．
  • 本日の講義ありがとうございました。
    -- こちらこそありがとうございました．
  • 講義ありがとうございました、非常にわかりやすかったです。
    -- こちらこそありがとうございました．
  • 講義ありがとうございました．ラグランジュ緩和について非常にわかりやすかったです．
    -- こちらこそありがとうございました．
  • ラグランジュ緩和を用いることで整数計画問題がとても簡単に解けるようになっていて感動しました
    -- ちょっと誤解があったかもしれないので補足します．整数計画問題を解くには，いままでの講義で説明したとおり，分枝限定法などを用いることになります．そこで考える緩和問題や下界としてラグランジュ緩和が使えるというのが今日の内容です．ラグランジュ緩和を1回解いただけで整数計画問題が解けるとは限らないのでご注意ください．
  • ラグランジュの復習を忘れないようにする。
    -- ラグランジュの未定係数法 (未定乗数法) は微分積分学で学んだことがあるかと思います．基本的な考え方はそこで扱ったものと同じなので，その観点からも復習をしてみてください．
  • 除去した制約を満たさない場合は目的関数値にペナルティを与えるように目的関数を再設定するという方法は思いつきそうで思いつかなかった。
    -- これはかなり汎用性のある考え方です．最適化問題としてモデル化する，ということを現実問題の解決に対して行おうと思うとき，「ある条件を満たさなくてはならない」ということを制約として表現するか，目的関数に対するペナルティとして表現するか，皆さんには選択肢があることになります．「必ずしも満たす必要はないが，できれば満たしてほしい条件」というものがあるとするならば，最適化問題として，それを制約として表すのではなく，目的関数に対するペナルティとすることで，柔軟なモデル化ができるようになります．
  • ラグランジュ緩和の計算方法を覚える
    -- 覚える必要なないので，必要となったときに思い出せるようにしてください．
  • 最強ラグランジュ緩和という名前が面白いと思いましたが、日本語訳する際にそのような名前にするしかなかったのでしょうか？
    -- 「最強」は「strongest」に対応する訳語になっています．自然な訳語だと思います．ラグランジュ緩和の強さをその最適値で評価しているわけです．
  • 7/35のラグランジュ緩和の例のページで、下のグラフ内の青矢印は何を表しているのでしょうか。また、これは今日の授業の質問からは少し外れるのですが、期末試験ではどのようなことが主に聞かれるのでしょうか。
    -- ちゃんと説明していませんでした．すみません．青い矢印は左の図でも右の図でも目的関数の方向ベクトルを表しています．ラグランジュ緩和において，目的関数の方向ベクトルはλに依存するので，それを複数の矢印で表していたつもりです．
    期末試験について，皆さんが勉強しにくい気がするので，演習問題のようなものを作ってみます．
  • 線形計画問題のラグランジュ双対が元の線形計画問題の双対問題と等価になるというのは驚いた。
    -- 実をいうと，これは線形計画問題の双対問題を導出する方法としては割と標準的なものとなっています．授業では等式標準形でやりましたが，ぜひ不等式標準形でもやってみてください．同じような手順で，不等式標準形の双対問題が得られるはずです．
• 12/20 (11) 列生成法
  • コメントありがとうございます．期末試験について下の方に書き加えました．ご覧ください．
  • 授業ありがとうございました。
    -- ありがとうございました．
  • 本日の講義ありがとうございました。
    -- ありがとうございました．
  • 本日の講義ありがとうございました.来年もよろしくお願いいたします.
    -- 来年もよろしくお願いいたします．
  • テストに向けて1からやり直したい。
    -- はい，しっかりと復習をしてください．
  • 次回の講義までに今までの復習をしておきたい
    -- 質問がありましたら，ぜひお願いします．
  • 本日の講義ありがとうございました。列生成法の内容をしっかり復習します。
    -- はい，よろしくお願いします．
  • 列生成法にて変数を減らした時にsという文字が(配布資料のP25から)出てきましたが、sがどういうものなのかがよく分かりませんでした。この文字はどのような役割を持っているのでしょうか？
    -- 不等式制約を等式制約に書き換えるために新しい変数を導入し，それをsで表しています．スラック変数と呼ばれます．第1回講義スライドの28ページ (PDFのページでは49ページ) をご覧ください．単体法は等式標準形の線形計画問題に対して考えるので，このような書き換えを行っています．
  • 授業ありがとうございました。例の部分は理解できたのですが、一般論になるといつもついていけなくなるため、家で式変形を追って復習します。列生成法はソルバーなどでも実装されて使われているのでしょうか？
    -- 自動的に列生成法を行うことは難しいです．授業でも述べたとおり，列生成法の途中で出てくる価格付け問題を解くためには，個々の問題の特徴や構造を用いる必要がでてくるからです．
    実際には，列生成法を実装する場合，多くのソルバに備わっている「変数を追加する」「制約を追加する」といった機能を使うことが多いと思います．切除平面法や分枝切除法でも同様です．
  • 一般論から入っていたら100%何を言っているのかわからなかったと思います。例を先に見たことで、一般論の話がなんとなく理解できました。
    -- 私もそう思います．この授業ではできるかぎり例から先に説明するようにしようと思っています．もしかしたら，一般論の部分はいらないのかもしれません (授業で説明しなくてもよいのかもしれません)．例をしっかりと理解できれば，一般論の部分は自分で導けるかもしれないからです．そうであっても，一般論を自力で導出するのは難しいと思うので，スライドに書いてあることをヒントだと思って，自分で式変形を実際にやってみると理解が進むかと思います．
  • 列生成法と切除平面法は似ているなと思っていたので、関係性を理解してスッキリした。次の授業まで時間が空くので、これまでの復習をしておきたい。
    -- 私もスッキリしました．:-) 私自身も今日の授業を行うまで，自分で式変形や導出を行っていなかったので，私自身も勉強になりました．
  • 列生成法を学ぶことで，切除平面法についての理解も深まった気がしました．次の授業が年明けなので，それまでにこの授業までの知識を整理したいと思います．
    -- 切除平面法と列生成法を組み合わせることもできます．変数も制約も多い問題を解くときにどうするか，と考えると，組み合わせたくなるのです．実際に，大規模な巡回セールスマン問題を解くときには，切除平面法と同時に，辺に対応する変数を追加するような列生成法を考えているようです．
  • 列生成法と双対問題における切除平面法の対応関係に驚きました。線形計画問題において変数と制約が深い関係にあることを感じました。
    -- 私自身，最適化の奥義は「緩和と双対性」だと思っています (私見なので異論はもちろん認めます)．この2つはとても簡単な原理なのですが，非常に強力です．この2つが使いこなせるかどうかで，最適化に対する見方や考え方がかなり変わってきます．双対性は次回以降のラグランジュ緩和のはなしでも重要になってくるので，お楽しみに．
• 12/13 (10) 妥当不等式の追加
  • ありがとうございました
    -- ありがとうございました．
  • 本日の講義ありがとうございました。
    -- ありがとうございました．
  • 本日の講義ありがとうございました。
    -- ありがとうございました．
  • 本日の講義ありがとうございました。
    -- ありがとうございました．
  • 1から復習していきたい
    -- はい，ぜひ復習してください．
  • 後半ついていけない部分が多かったので、よく復習しておきます。
    -- 私自身がうまく説明できなかったので，それがよくないと思います．精進します．
  • 講義ありがとうございました．とても分かりやすかったです．
    -- ありがとうございます．分からないところがでてきたら，ぜひ質問してください．
  • 今日もありがとうございました。だいぶ理解が深まってきました。復習頑張ります
    -- 今回の内容は，わりとクライマックスです．ぜひ身に付けてください．
  • 大事なところを繰り返し説明していただけるので大変わかりやすいです。復習頑張ります
    -- はい，よろしくお願いします．
  • グラフの色分けなどの工夫によって証明がわかりやすかったです.
    -- ありがとうございます．本来はあまり色に依存しない方がよいのですが，ついつい依存してしまいます．
  • 櫛不等式や巡回セールスマン問題の分枝切除など、今回の範囲は今まででも難しいと思ったので復習をしっかりしておきたいです。
    -- 私も難しいと感じました．次回以降もこんな雰囲気の話が続くので，ぜひ復習してください．
  • 櫛不等式のところは家できちんと復習しようと思います。ありがとうございました。
    -- 冷静に考えると，それほど難しくないはずなので，考えてみてください．
  • 櫛や櫛不等式について初めて知ったが、名前の面白さに反して扱いが難しい考え方だと思いました。
    -- 難しく感じるのは私の説明がまずかったからだと思います．すみません．
  • 櫛不等式の三つの方程式の和を取る部分が理解しきれなかったのでもう一度録画で見ようと思います。
    -- はい，よろしくお願いします．
  • 1000兆以上の制約が十数個の制約に置き換えられるのが印象的でした
    -- アルゴリズムの威力ですね．といっても，今日の話はだいたい20年ぐらい前の技術なのだということもご注意ください．
  • 年末は、diyで巡回セールスマン問題を解いてみようと思いました
    -- こちらになります．ぜひ試してみてください．
  • ありがとうございました。DIYやってみます。
    -- 分枝限定法もDIYでできます．ぜひやってみてください．
  • 部分巡回路除去制約の追加の例が視覚的に分かりやすく面白かったです。楽しそうなので後で遊んでみます。
    -- 櫛不等式もDIYでできます．ぜひやってみてください．
• 12/6 (9) 切除平面法
  • 講義ありがとうございました。
    -- こちらこそありがとうございます．
  • 本日の講義ありがとうございました
    -- こちらこそありがとうございました．
  • ありがとうございました。分かりやすかったです。
    -- それはよかったです．分からないところがでてきたら，ぜひ質問をしてください．
  • 講義ありがとうございました.
    -- こちらこそありがとうございました．
  • 本日の講義ありがとうございました。切除平面法をしっかり復習します。
    -- はい，ぜひ復習をしてください．
  • 授業ありがとうございました。後半すこし理解に時間がかかったので、講義動画を見てもう一回復習したいと思います。
    -- そうですね．まずは例を理解して，自分でも適当な例を作って，アルゴリズムの動きを追ってみるとよいかと思います．
  • Gomoryの小数カットアルゴリズムの一般論がややこしかったためそこを復習しておきたいです。
    -- 確かにややこしいですね．このアルゴリズムでは，「変数が整数値を取る」という性質をかなり使っています．そのフレーバーをぜひ味わってください．
  • 単体法の授業の時に学んだ端点最適解を求める方法と，今回の切除平面法を利用して端点最適解を求める方法でそれぞれどのようなメリットがあるのか復習をして確かめたいと思いました．
    -- メリットやデメリットを考えることはとても重要だと思いますので，ぜひ考えてみてください．
  • 今までの内容も絡んできたので、全体を関連させて復習する
    -- そのとおりですね．やはり1学期間を通して行う授業というのは，そのストーリーが重要だと思います．ここまでの部分の復習を通じて，ストーリーも感じてみてください．
  • 線形計画問題で得られた最適解からの距離が大きくなるような切除平面が良い切除平面ということになるのでしょうか?
    -- 「良い切除平面」であることの評価方法にはいろいろなものがあります．「線形計画問題で得られた最適解からの距離が大きくなる」というのは1つの評価尺度になり，よく用いられます．「距離」と言われると図形における意味合いを考えてしまうと思いますが，よく用いられる量は整数ギャップ (整数性ギャップ, integrality gap) と呼ばれるものです．これは，整数計画問題の最適値とその線形計画緩和の最適値の差 (の絶対値) によって表されます．これが小さいほど，線形計画緩和は元の整数計画問題に「近い」と考えることができますし，線形計画緩和の最適値を整数計画問題の最適値の下界 (最小化問題のとき) と見るとき，その下界の良さを表す指標でもあります．切除平面を追加したときに，整数ギャップがどれだけ0に近くなるのか，ということで良さを評価することが多いような気がします．
    他の尺度としてあるのは，整数計画問題の許容領域の凸包をCとするとき，追加する切除平面がCのファセットを定義するかどうかという指標です (ファセットの定義は第2回講義資料を参照)．Cはそのファセット (を定義する不等式) によって完全に記述できるので，それが切除平面として得られることはとても有用だからです．この観点については次回少し説明します．
    尺度に関しては，DeyとMolinaroの論文に様々なものが詳しく書いてあります．
  • 切除平面法という1つの考え方に対して複数の切除平面が提案されている点が興味深かった。最適な切除平面というのはあるのでしょうか。
    -- 尺度を固定すれば，その尺度を最大にする (最小にする) 切除平面という概念を定義できます．そして，そのような切除平面を実際に見つける問題やアルゴリズムも考えられています．
    最近の研究トレンドは，よい切除平面を見つけるために機械学習を用いるという方向です．切除平面だけではなく，分枝切除法におけるよい戦略を見つけるために機械学習を用いるという話もあります．授業でも言及したように，これらはいわゆるパラメータ選択なので，機械学習の考え方と相性がよいようです．
  • 今日もありがとうございました。復習が間に合わなくなってきました。年末年始の期間でしっかりおさらいしたいと思います。
    -- はい，ぜひ復習をお願いします．
• 11/29 (8) 分枝限定法
  • 本日の講義ありがとうございました。
    -- こちらこそありがとうございました．
  • 本日も抗議ありがとうございました
    -- すみません，抗議はしていないつもりです．
  • 講義ありがとうございました。
    -- こちらこそありがとうございました．
  • 授業ありがとうございました。わかりやすかったです。
    -- ありがとうございます．分からないところが出てきたら，ぜひ質問をお願いします．
  • 今日も興味深い授業でした。ちょうど半分を過ぎたのでしっかりふくしゅうしていきたいとおもいます
    -- はい，しっかりと復習をお願いします．
  • 本日の講義ありがとうございました。分枝限定法の部分は分かりやすいです。
    -- ありがとうございました．ぜひ，自分で例をつくって動きを確認してみてください．
  • アルゴリズムの話が本格的に始まったので置いていかれないようにしたい
    -- 先週までの内容とフレーバーが異なると思うので，ちょっと戸惑う部分もあったかと思いますが，こんな感じであと数回は進んでいきます．宜しくお願いします．
  • 分枝限定法の流れを理解する.
    -- 一般論はややこしいかもしれないので，まず例で流れを理解してください．
  • 分枝限定法の一般論の説明がやや理解するのに手間取った為ここの部分の復習、特に線形経過緩和の性質などをもう一度見ておこうと思いました。
    -- 線形計画緩和はどんどん使っていくので，その性質などの復習をしておいてください．
  • 一般論よりも先に，例を紹介していただいたのが非常にわかりやすかったです．
    -- これは励行しています．「一般論→例」という順番よりも「例→一般論」の方がわかりやすいと思っているので，今後もそうしていきます．(前回のコメントでもその話をしてますね (^^;))
  • 分枝限定法の説明が分かりやすかったです。　貪欲の貪を今まで貧しいの貧だと思っていました…
    -- 漢字の間違いは思いのほか起きています．ここで気が付けたのなら，それはよかったと思います．
  • スライドの表や図などさまざまな工夫がされていて参考になります
    -- フローチャートを描くことによって，余計に分かりにくくなってしまうという例を，今日はお見せしてしまったかもしれません (-_-;
  • これまで受けてきた講義で木構造はよく扱ってきたので分枝限定法はとても理解しやすかったです。
    -- 分枝限定法はある意味で再帰的なアルゴリズムであると見ることができます．再帰的なアルゴリズムの動きは木構造で表現できるため，その表現を使ってみました．一方で，分枝限定法は上界や下界が1つの再帰呼出において改善されたとき，それが他の再帰呼出の方に影響を与える可能性があります．その意味で，分割によって作られた複数の問題は独立なのではなく，一方を解く際に得られた情報が他方を解く際に使われて，その点も面白い特徴となっています．しかし，この特徴のため分枝限定法は「並列化が難しい」という側面を持っていたりします．効率よく分枝限定法を並列化するための研究はよく行われていて，最適化問題を実践的に解くことを目指すときには重要なテーマとなります．
  • 分枝限定法で解いても限定操作がほとんど行えず、結局総当たりとあまり変わらない、というような問題はありますか。
    -- Jeroslowの論文 (1974) は，分枝限定法における「葉の数」が$2^{n/2}$個になってしまうような，ナップサック問題の例を構成しています ($n$ は商品数)．$2^{n/2}$ は $\sqrt{2}^n$ と書くこともできますが，これは $n$ に関して指数関数的に大きいことを意味します．Chvátalの論文 (1980)やJuknaとSchnitgerの論文 (2011) も参考になります．
    ただ，これは「総当たりとあまり変わらない」といっていよいのかどうか，微妙な点もあります．なぜならば，総当たりにおける「葉の数」は $2^n$ ですが，$2^n$ と $\sqrt{2}^n$ を比べると $\sqrt{2}^n$ の方が圧倒的に小さいからです．例えば，$2^n$ 時間のアルゴリズムで解ける問題の規模が $n \leq 20$ だとすると，$\sqrt{2}^n$ 時間のアルゴリズムで解ける問題の規模は $n \leq 40$ になります($\sqrt{2}^n = 2^{n/2}$ だから)．
  • 切除平面法は以前論文で出てきて理解が曖昧なまま終わってしまった記憶があるので、次の授業が楽しみです。
    -- はい，ご期待ください．
• 11/22 (7) 整数計画モデリング (3)：離接計画
  • 本日もありがとうございました
    -- ありがとうございました．
  • ありがとうございました
    -- ありがとうございました．
  • 本日の講義ありがとうございました。
    -- ありがとうございました．
  • マイクを無線から有線に変えてくださったおかげで前回の授業より聞き取りやすくなって良かったです。
    -- それはよかったです．それでは今後は有線のマイクにします．
  • ビンパッキング問題の2個目の定式化の方が変数が多くて解くのが大変そうなのに、さらに変数を追加してとくことで解きやすくなるというのが不思議に感じた。列生成法を学ぶのが楽しみです。
    -- そうですよね．これが最適化モデリングの面白さの1つだと思います．「よいモデリング (モデル化，定式化)」というものと「よいアルゴリズム」が密接に関連しているところも重要です．つまり，現実問題を解決しようとするとき，アルゴリズムに関する理解が役立ち，ソフトウェアを単にブラックボックスとして使うだけではうまくいかないことになります．
  • ビンパッキング問題の2つ目のモデルの線形計画緩和を解くのは容易ですか？もし未解決問題が正しければ、緩和問題を解くだけで強力な近似解を得られると思ったのですが。
    -- この線形計画緩和に対する $\epsilon$近似最適解は多項式時間で見つけられることが知られています (Karmarkar, Karp 1982)．ただし，そのアルゴリズムは複雑である (というか，実用的ではない) ため，実践においてめったに使われません．実をいうと，列生成法はこの手の線形計画緩和を解くための実用的な手法で，それを使って整数計画問題自体も解くということを行います．
    また，未解決問題が正しい場合の話ですが，実をいうと，線形計画緩和の最適値が分かっても，よい近似解ができるとは限りません．なぜかというと，近似解においては，ビンへの詰め方まで決める必要があるからです (最適値と最適解を明確に区別しているのと同じように，近似値と近似解を明確に区別しています)．ビンへの詰め方を決めるには，いわゆる「丸め」(rounding) という操作を行うことになり，近似解構成法として，様々な方法が研究されています．
  • パターン集合を使ったビンパッキング問題のモデリングにおいて、多くの入力で整数切り上げ性が成立するのが興味深かったです。
    -- まず，一つの問題に対して複数のモデリングが可能であるということが重要ですね．その上で，integer round-up propertyに関する研究はビンパッキング問題以外にも行われていて，「性質のよい」整数計画モデリングの探究において重要な役割を果たしています．
  • だんだんと難しくなってきているので復習を忘れないようにしたい
    -- はい，動画もありますので，ぜひ復習に活かしてください．
  • 離接計画についての話が難しくて混乱したので、よく復習しておきます。
    -- はい，よろしくお願いします．
  • 数式や証明が十分に理解しきれなかったので復習する
    -- 式については，自分で例を作って書き下してみると，よく分かるかもしれません．試してみてください．
  • 数式についても具体的に説明をしてくれ、どの部分をどのように書いているのかわかりやすかったです。
    -- ありがとうございます．説明の順番として「例→一般論」を採用しています．数学の教科書などは「一般論→例」で説明していることが多いのですが，「例→一般論」の方がわかりやすいと思っています．
  • 離接計画について初めて学んだので興味深い内容でした。
    -- 一見，数理最適化手法でモデリングができないように見えるものも，モデリングできたりします．そのような例として離接計画をご紹介しました．今回扱ったのは，その最初の一歩の部分で，その先にもまだまだ理論が広がっています．興味がありましたら，ぜひ勉強してみてください．
  • 離接計画について初めて知りましたが，どうして単純に解けないのか，どうしてこのアイデアで解くことができるのかについて理解できたので，しっかりと復習をしたいと思います．
    -- はい，実際に自分で例を作って考えてみるとさらに理解できると思います．試してみてください．
  • 講義ありがとうございました。混合整数線形モデルの部分はちょっと複雑です。
    -- そうですね．整数計画モデルを作成するということ自体が興味深い内容になりうること，そして実際そうであることをまず感じていただくことが重要だと思います．
  • 離接計画問題が興味深かったです。今回の設定では、k個の線形計画問題を考えていましたが、k個の整数計画問題でも同じような議論ができるのでしょうか?
    -- はい，k個の整数計画問題でも同じような議論ができて，k個の整数計画問題を「または」でつなげた問題を1個の整数計画問題としてモデリングできます．ただ，その線形計画緩和に関する性質はk個の線形計画問題のときと同じようには成り立たないので注意が必要です．
  • 離接計画の線形計画緩和を解けば十分ということは、「または」の間にある領域は、問題を解く上で存在してもしなくても変わらないというようなイメージでしょうか。
    -- はい，実際そのようになります．実はスライドの4ページ目にある図はその雰囲気を表しているものです．(全然説明していませんでしたが．)
    もう少し詳しくこの図を説明します．3つの凸多面体が平面上にあって，それらの「または」で表される最適化問題があったとき，それを授業の方法で整数計画問題としてモデリングすると，変数の数が増えるので，高次元空間の凸多面体を許容領域とする問題となります．それを元の空間 (この場合は平面) に射影すると，右の図のようにもともとあった3つの凸多面体の凸包が得られます．
    「間にある領域が存在してもしなくても変わらない」という事実は割とすんなり受け入れられると思います．なぜならば，目的関数が線形関数であるため，最適解は必ず「端」にあることになるからです．そのため，「間にある領域」に最適解が存在することはありえないことが分かります．ポイントとなるのは，問題を実際にそのような形で表現することが簡単にできる，ということで，それによってソルバ等で簡単に解くことができるようになります．
• 11/15 (6) 整数計画モデリング (2)：より複雑な問題
  • 本日の講義ありがとうございました!
    -- こちらこそありがとうございました．
  • わかりやすかったです。ありがとうございました。
    -- それはよかったです．分からないところがでてきたら，ぜひ質問をしてください．
  • 今日は暖房がついていたのか、教室が暖かくて快適でした。
    -- そうでしたね．11月の中旬になったので，もしかしたら，暖房運転が始まったのかもしれません．
  • すこし理解が遅れている部分があるので復習していきたい
    -- 復習しやすいように演習問題を準備しようかと考えています．
  • 授業ありがとうございました。復習頑張ります
    -- はい，よく復習してみてください．
  • 今回初めてzoomから視聴したのですが、こちらの環境が悪いのか聞き取り辛い場面があったので、もう少し遅めに説明してくださると助かります。
    -- ありがとうございます．注意してみます．ただ，UEC Wirelessの通信状態に大きく依存しているため，私の手元ではなんともできない場合もあります．ご了承ください．おそらく，元も子もない解決法は，教室で授業を受けることだと思います．
  • ナップサック問題について理解が深まった
    -- ナップサック問題は典型的な組合せ最適化問題なので，よく理解できると今後いろいろな場面で役立つと思います．
  • 実用的ではないけど理論上可能ではあるような表現方法は、勉強してて楽しいです
    -- 現状では実用的でなくても，将来実用的になる可能性がある，ということは気に留めておくとよいかもしれません．実際，最適化モデリングではそのようなことがおきたりします．何事においても成り立つと思うのですが，現状のあり方と，将来あるべき姿は異なるはずです．現状だけにとらわれていろいろなことを考えると，思わぬ落とし穴に陥る可能性もあるので，ご注意ください．
  • 図を用いた説明がとてもわかりやすかったです
    -- 図は重視しています．一方で，図は直感でしかないので，図を助けとして，定義に基づく理解も試みるようにしてください．
  • 一つの問題に対して複数のモデルを説明していただくことで，より多角的に問題を見ることができていると思いました．まずはそれぞれのモデルのアイデアを理解し，簡単な問題は解けるようになりたいと思っています．
    -- モデルの良さとして今までちゃんと述べていなかったことがありますが，その1つとして，モデルの拡張が容易であることがあります．例えば，巡回セールスマン問題に似た問題を解きたいと思ったとき，巡回セールスマン問題の整数計画モデルに変数や制約を追加することで，その似た問題の整数計画モデルを得ることができる場合があります．そのとき，巡回セールスマン問題の整数計画モデルとして最初に採用するものによっては，そのような追加が容易であるか困難であるか，変わってくる可能性があります．(そして，実際にあります．) 皆さんが手持ちの問題を解決しなくてはならないときに，そのような点にも注目してみてください．
  • 過去にTCP問題を解くことに苦戦したことがあり、そのときに今回学んだ整数計画モデルの発想があれば！と感じました。
    -- TCPではなくてTSPでしょうか．一般に「問題解決法」と呼ばれるものにはいろいろなものがあります．何でもできる「銀の弾」はないと思って，様々な視点を学び，困難に直面したとき，適切な解決法を選べるようになることが重要なのかもしれませんね．
  • 巡回セールスマン問題について,身の回りで用いられているか調べてみたい
    -- 下の関連リンクでも紹介しているTraveling Salesman Problemのページでは，TSP Applicationsとしてどのような応用があるか，説明しています．ただ，ここに挙げられている応用は割と古いものなので，それには注意してください．
  • 現在行っている研究は非循環有向グラフ を対象にしているのですが、整数計画法を用いた 論文で部分閉路除去制約が出てきたので非常に タイムリーな話題で集中して聴けました。 この論文の著者は巡回セールスマン問題の 解き方を参考にしたのかなと考えました。
    -- 参考にしたのかもしれませんね．部分閉路除去制約の考え方は広く適用可能で，いわゆる「連結性」を要求する場合には同じような制約を考えることが多いと思います．
• 11/8 (5) 整数計画モデリング (1)：組合せ最適化問題
  • 本日の講義ありがとうございました。
    -- こちらこそありがとうございました．
  • 講義ありがとうございました
    -- こちらこそありがとうございました．
  • 本日の講義ありがとうございました.
    -- こちらこそありがとうございました．
  • ありがとうございました。毎回わかりやすい講義ありがとうございます
    -- こちらこそありがとうございました．
  • ありがとうございました。
    -- ありがとうございました．
  • 問題を解くには定義を明確にすることが大切だと学んだ。
    -- そうですね．「問題を解く」ときに，まず「問題」が何であるか，そして「解く」とは何を意味するのか，ということを明確にするよう，こころがけて下さい．これは数学を使った問題解決だけではなく，ソフトウェア工学における要件定義や仕様策定においても重要なこころがけです．定義が明確になることによって，用語に対する共通認識ができあがり，コミュニケーションもスムーズに行うことができるようになります．ぜひ励行してください．
  • シグマの知らない表記が出てきて集合でも使えることを知った。
    -- そうですね．集合を使いこなせるようになることは，様々な場面で重要になります．例えば，ジョブをいくつかの機械で処理することを考えるようなスケジューリングに関する問題では，ジョブを $1, 2, ..., n$，機械を $1, 2, ..., m$ で表すようなことをすると，「$1$」と言われただけでは，ジョブを指すのか機械を指すのか分からなくなります．一方で，ジョブの集合は $J$，機械の集合は $M$ というような記号を導入できれば，ジョブに関する和は $\displaystyle \sum_{j \in J}$，機械に関する和は $\displaystyle \sum_{m \in M}$ というような記法を使って書くことができるようになります．混乱も少なくなり，とても便利です．
  • 線形計画緩和はどのような事を求められた時に使えば良いのでしょうか。
    -- いろいろな場面で使えます．(1) 整数計画問題を解くためのアルゴリズム (プログラム) の中で使う．これについては，今後の授業の中で，実際にどのように使うのか説明します．(2) 整数計画問題の許容解の良さを評価するときに使う．これは今日の授業で説明した内容になります．同じ方法で，ヒューリスティックな解法の良さを評価することもできます (ヒューリスティックな解法で得られた許容解の良さを評価すればよいから)．(3) 整数計画問題の近似解を得るためのアルゴリズム (プログラム) の中で使う．これはこの講義では扱いませんが，非常に重要なアルゴリズム設計技法として知られています．(4) 「線形計画緩和の最適値＝元の整数計画問題の最適値」となるような都合のよい整数計画問題を解くために使う．これも今日の授業で少し説明しました．実をいうと，このように都合のよい整数計画問題は案外たくさん存在していて，例えば，割当問題や輸送問題と呼ばれるような問題 (に対する自然な整数計画モデル) はこの性質を満たすことが知られています．
    
  • スライド23ページで、下の図は(緩和問題の最適解)=(元問題の最適解)という嬉しい状況ですが、代わりに上の図より制約式が増えています。下の問題の方が解くのに時間がかかりそうですが、元問題の最適値が得られるという意味で下の図の方が良いモデリングなのでしょうか。
    -- 様々な観点を分けてモデルの評価をすることになります．例えば，モデルAとモデルBがあるとき，制約の数という観点ではモデルAの方がモデルBよりもよいが，線形計画緩和の観点からはモデルBの方がモデルAよりもよい，といった感じです．この意味で言えば，23ページの例では，制約の数という観点では，上の方が下よりもよい，となり，線形計画緩和の許容領域の包含関係の視点からは，下の方が上の方よりもよい，となります．
  • モデルの良さを数値で表すことができれば、明確に比較ができると思いました。また、モデルの良さについて問題の規模と許容領域の大きさが挙げられていましたが、許容領域を小さくするためには制約の数を増やす必要があるのではないかと思いました。つまり、問題の規模と許容領域の大きさとの間にトレードオフのような関係があるのではないかと考えましたが、どうなのでしょうか?
    -- 一般的なことを言うのは難しいのですが，多くの場合にはトレードオフのような関係があります．また，問題の規模が大きい (例えば，制約の数が多い) からといって，解きにくい，と一概には言えないという側面があります．これはちょっと話に出した「A, b, cの特徴・構造」にも関係しており，また，整数計画問題を解くためのアルゴリズムのはなしとも関係があります．アルゴリズムの説明をする際に，紹介することになると思います．
  • 最大独立集合問題の整数計画モデルが思ったより単純な形になることを知り驚きました。各問題の整数計画モデルをソルバで解く際にどんな要素がネックになるのかを知りたいです。
    -- 実際は，アルゴリズムに依存することになります．ただ，多くの場合に重要なことは「線形計画緩和の許容領域が小さい」ことです．これが重要であるということは，変数の数や制約の数が多いことがボトルネックとなることよりも，線形計画緩和の性質がボトルネックになることが頻繁に起こりやすい，ということです．そのため，研究者は「線形計画緩和の性質がよりよい整数計画モデル」を開発・設計することを目指すことが多く，実際にそのような論文がたくさん出版されています．
  • 授業ありがとうございました。第4回の最後の整数計画モデルの良さについての話が面白かったです。
    -- 次回は実例で整数計画モデルの良さを体感する予定です．お楽しみに．
  • ナップサック問題などを今まで学んできた整数計画法により解くことを体験できて非常に楽しかったです．また，選択するような問題では変数で01を利用するなど，立式において大事なことも学べたので，過程も大事にしながら復習をしたいと思います．
    -- 01変数をうまく利用することが，整数計画モデリングにおいて重要なので，ぜひ身に付けてください．
  • ナップザック問題に関して未だ苦手意識が強く、内容を理解するのに時間がかかってしまいます。しっかり復習していきたいと思います。
    -- はい，分からないところがでてきたら，ぜひ質問をして下さい．
  • 本日の講義ありがとうございました。ちゃんと復習します。
    -- はい，しっかりと復習をよろしくお願いします．
  • ナップザック問題を復習しながら、どのように応用できるか自分でも考えてみたい
    -- そうですね，どのように応用できるのか考えるのは重要なので，いろいろと考えて，ぜひ皆さんの研究や生活の中に活かしていってください．
  • ある整数計画問題を解くときに分枝限定法がよく利用されると思うのですが，そのアルゴリズムの中で緩和問題の許容領域を小さくするために追加される切除平面について勉強してみたいと考えています
    -- 切除平面法は第9回の授業のテーマとなる予定です．しばしお待ちください．
• 11/1 (4) 線形計画緩和
  • 毎回毎回，次週に残りが持ち越されるようになってすみません．とうとう「持ち越し」の方が本題になってしまいました．第7回の授業の辺りで追いつくと思います．ご了承ください．
  • 講義ありがとうございました。
    -- こちらこそありがとうございました．
  • 来週もよろしくお願いします。
    -- はい，よろしくお願いします．
  • 分からない部分が出てきたので復習をしていきたい
    -- はい，ぜひ質問もお願いします．
  • 双対法の使い方と単体法の解き方がどうやれば良いのか少し理解に手間取ったので、そこを重点的に復習しようかと思います。
    -- はい，分からないところはぜひ質問してください．
  • 休憩を挟むことで全体的に集中して講義を受けられてよかったです.
    -- 休憩は重要なので死守しています ;-)
  • 整数計画問題を久しぶりに自分で解いたがとりあえず覚えててよかった。忘れないように復習したい。
    -- それはよかったです :-)
  • 今日の授業はボリューミーでした。途中置いてかれそうになったときがあったので、ちゃんと復習します。
    -- そうですね．普通の最適化の授業では2, 3回かける内容を1回でやってるような感じになってます．一応「復習」の立場をとっているのでそうなっていますが，初見の場合はしっかりと復習が必要になりますね．よろしくお願いします．
  • 強相対定理に対して謎の感動を覚えました。
    -- 「双対」定理ですね．「そうつい」と読みます．一方で「相対」は「そうたい」なので，区別してください．ちなみに，感動できるのはすばらしいと思います．ぜひ他の人とその感動を共有してください．
  • 単体法の説明が丁寧でとても分かりやすかったです。
    -- 単体法の説明のしかたはいろいろとあるのですが，私の説明法では次の2つを重視しています．(1) 図形によって意味が捉えられること，(2) 「辞書」や「タブロー」を使う機械的な処理にせず，式のまま扱うこと．いろいろな教科書では「辞書」や「タブロー」といった表のようなものを使うことで単体法を説明することが多いです．しかし，それだと何をやっているのか，意味をつかむことが難しくなり，結局，すぐに忘れてしまうことになります．そうならないようにするため，まずは図のイメージを大事にして，そこから式変形によって単体法が導出できるような流れを感じられるようにしているつもりです．
  • 本日も講義ありがとうございました。端点最適解を求める手順について、順を追って説明してくださったのが非常にわかりやすかったです。一般論でも理解できるように、復習をしたいと思っています。
    -- 一般論はなかなか難しいですね．一般論の式変形などを見るときには，例を思い浮かべながら，何をしているのか理解するとよいと思います．
  • 本日の講義ありがとうございました。単体法は面白いです。
    -- 単体法はいまなお研究される重要なトピックです．いまだに単体法の周辺で分かっていないことは多くあります．
  • 線形計画問題を「解く」とは非有界非許容の判定も含めるとは知りませんでした。最適解の有無だけだと思っていたので勉強になりました。
    -- 最適化を使う場面によっては，非許容であることを判定することが重要であることがあります．例えば，システムが故障する条件を制約として書くことができれば，制約をすべて満たす点 (つまり許容解) が存在することと，故障する可能性があることが対応することになります．つまり，問題が非許容であることと故障する可能性がないことが対応することになります．そのような使い方もあるのだと思うと，最適化の応用が広がりますね．
  • 本日の講義で、線形計画問題を解くということは、三態のうちのどれかであることを判定し、最適解が存在するならば、最適解を一つ求めることであると学びました。単体法は、最適解が存在するとき、最適解を一つ求めることを保証するのでしょうか?また、非有界、非許容の場合、必ず判定できるのでしょうか?
    -- 単体法では，最適解が存在するとき，最適解を一つ求めることができます (保証されます)．ただし，いくつか注意が必要です．授業で説明した方法では，目的関数値を減少させる非基底変数を1つ選んで，その変数の値を大きくすることで，ある基底変数を新たに非基底変数にする，という操作を繰り返していました．ここで，「どの非基底変数を選んで，その値を大きくするのか」という部分と「どの基底変数を選んで新たに非基底変数にするのか」という部分にはいろいろな選択がある場合があります．実をいうと，この選択をうまく行わないと，最適解にたどり着けない場合があることが知られています (その現象はよく「巡回 (cycling)」と呼ばれています)．この選択をうまく行う規則がいろいろと知られていて，それに従って選択を行うと，最適解が存在する場合に，必ず最適解を見つけられます．
    一方で，非有界であることや非許容であることの判定もできます．しかし，これも注意が必要です．そもそも単体法は「許容領域の頂点から出発する」ということを行っているので，許容解を持つ問題だけを対象としたアルゴリズムになっています．許容解を持つ場合には，それが非有界であるか，最適解を持つかということを判定することができます．それは第3回のスライドで今日とばしたところに雰囲気が書いてあります．
    そのため，単体法には次の問題点があります．(1) 非許容な問題を扱えない，(2) 許容領域の頂点を1つ見つけなくてはならない．しかし，この問題点を克服する方法が実は知られています．それは次の性質を持つ線形計画問題を元の問題から作るという方法です．その性質とは (a) 最適解が存在する，(b) 許容領域の頂点の1つを簡単に見つけられる，(c) その問題の最適解を知ることで，元の問題が非許容か許容解をもつか判定でき，なおかつ，許容解を持つ場合は，許容領域の頂点の1つも簡単に見つけられる，というものです．このように作られた問題に対して(b)の性質から単体法を実行でき，(a)の性質から，単体法は最適解を見つけて停止します．そして，(c)の性質からその最適値を見ることで，元の問題が非許容か分かり，そうでなければ，元の問題の許容領域の頂点を1つ見つけることができます．これでまず，非許容かどうかの判定ができるようになり，非許容でなければ，元の問題に対して単体法が実行できるようになり，それによって，元の問題に最適解が存在するか，非有界か分かるようになります．これで授業で述べた意味のもとで「線形計画問題が解ける」といえるようになります．
  • 線形計画緩和は研究で使っていたものの，ちゃんと定義を確認せずになんとなくで使っていました．私が思っていたのと同じ定義でしたが，ちゃんと勉強します．
    -- ちゃんと定義する，ということはこの講義で強調したい側面だと思います．線形計画緩和の定義もそうですが，「解くこと」の定義も行いました．実をいうと，「解く」ことをちゃんと定義しないために，「アルゴリズム」と呼ばれるものが何を目的としているのか，わけがわからない研究や製品というものが多く存在します．そういうのは困ると思っているので，できる限り明確な定義を与えるように努めています．
    一方で，この講義で与えた線形計画緩和の定義は少し限定的であって，本来はもう少し緩やかな定義を行うことが多いような気もします．(つまり，この講義で与えた定義の意味では線形計画緩和と呼べないが，他の人や文献は線形計画緩和と呼ぶ可能性があるものもあると思います．) これについては，この講義が進んでいくにつれて，雰囲気が分かるようになるかもしれません．
  • 整数計画問題Pの許容領域 = 線形計画緩和Rの許容領域となるとき、Pの許容領域はある1点のみになるのでしょうか。
    -- その場合には，Pの許容領域がある1点のみになるか，あるいは，Pの許容領域が空集合であるかのいずれかが成り立ちます．
  • 線形計画緩和で整数以外を扱えるようになるのは大きなメリットだと思いました。
    -- 実際に，線形計画緩和を使って整数計画問題を解いていきます．その様子は次回以降扱っていきます．
  • 線形計画緩和を踏まえて、線形計画法についてまとめ直したい
    -- 線形計画緩和の性質は次回詳しく扱うことになります．お楽しみに．
• 10/25 (3) 線形計画法の復習 (2)：単体法と双対定理
  • ありがとうございました。
    -- こちらこそありがとうございました．
  • 本日の講義ありがとうございました。
    -- こちらこそありがとうございました．
  • 授業ありがとうございました
    -- こちらこそありがとうございました．
  • なんとなくこの科目の目指すところが見えてためになった
    -- それはよかったです．おそらく，この授業では，最適化に対する直感を養うことを目指しているのだと思います (自分で授業をしておいて，他人事みたいにいってますが…)．特に，変数の数が多い場合を想像するには，幾何学的 (図形的) なイメージを持つことが重要だと思います．数式の上の操作を図形的なイメージに重ね合わせることができるようになると，最適化に対する直感がかなり養われたことになると思います．
  • だんだん難しくなってきたので復習します
    -- はい，分からないところはなんでも聞いてください．
  • 今回の内容に関して復習しっかり行っていきます。理解に苦しんだ部分が多くありました
    -- 理解に苦しんだ部分が具体的にわかりましたら，教えてください．そのような部分については，補足などもしていきたいと思います．
  • 今回出てきた定理や集合が自分の中で整理できていないので復習して次に臨みたい.
    -- そうですよね．いろいろな概念がどんどん出てくるので，理解するのは大変かと思います．定理を用いるときには，復習しながら使うようにしようと思うので，覚えようとはしないで下さい．
  • 第二回スライドの等式標準形の頂点特定問題が例題付きで理解しやすかったので、今後のスライドも例題を多くつけてくださると助かります。
    -- ご提案ありがとうございます．そうしていきます．
  • (この授業に限らず)右肩に添字がついている文字をよく見かけますが、指数との見分けがつきません。文脈で判断するしかないのでしょうか。
    -- 文脈で判断します．右肩に数字がつく他のパターンとして，他にも脚注記号として用いる場合があります．それも文脈で判断します．
  • 今日のスライドで27ページに「性質：凸結合による頂点の特徴づけ」というものがありました。図のイメージの通りにxを中点とするようなx'とx''をとったとすると、x=x'=x''が成り立たない気がするのですがどうなんでしょうか。
    -- 図はxが頂点ではない状況を表していますので，図は正しいです．xが頂点である場合には，x=x'=x''が成り立たないようにx', x''をとれないのです．一方で，x=x'=x''のとき，x=(x'+x'')/2は成り立つので，つまり，「xが頂点であること」と「x=(x'+x'')/2となる x', x''∈Pが，x=x'=x''に限られること」が同値となります．
  • ありがとうございました。習った定理や性質がどのように整数計画問題を解く上で役立つのか、今後の授業で学ぶのが楽しみです。
    -- これは今後のはなしになりますね．お楽しみに．
  • だんだんと昔受けた数理計画法の講義が思い出せてきました.
    -- それはよかったです．ひとつのことについてもいろいろな説明の仕方があるはずなので，違う説明を通して，多様な理解ができるとよいと思います．
  • 今回学んだ定理が今後どのように活用されるのか、次回が楽しみです。
    -- すいません，ちょっと授業計画が悪くて，次回にいきなり活用されるということはないかもしれません…．
  • 一般論は理解が難しいですが，丁寧に図を利用して説 明してくださっているので，流れやイメージはつけることができました．
    -- 図は重視しています．「目で見て分かった気になる」というのは割と大事だと思っています．一方で，図はあくまでもイメージであったり，例であったりするので，一般的な事項はことばによってできる限り正確に理解できるように努めてください．
  • 図表を用いて説明してくれるのでとても理解が深まります.
    -- 皆さんもぜひ，図を描いてみてください．
  • 小学校や中学校でやった，頂点の定義や頂点を特定するといったことが，数学的な定義を感覚的に理解できるように書かれているのに驚きを感じました
    -- そうですね．特に，高次元 (多変数) のものを理解しようとする場合には，数学の用い方が重要になってきます．直感として頭の中に思い浮かべていることを，しっかりと数学を用いて書き下すことができるというのは，数学的なリテラシーとして重要な技術ですので，ぜひ身につけてください．
  • 図があることでイメージを先に頭に入れることができ、数学的な表現が理解しやすかったです
    -- 説明のしかたとして，「一般法則 → 具体例」という順番よりも「具体例 → 一般法則」の方がわかりやすいと思っています．多くの数学書は「一般法則 → 具体例」という順番で書かれていますが，具体例を先に挙げる方が，定理や定義のイメージがしやすいと思うので，私の授業ではできる限りそうしています．
  • 村松先生の数理最適化で双対問題への変換をかなり練習したので、わかりが良かった。
    -- それはよかったです．次回も双対問題を扱いますので，復習しておいてください．
  • 主問題と双対問題の関係の理解を完璧にしたい
    -- この授業で完璧な理解まで到達できないかもしれませんが，双対問題を考えることは最適化の奥義のようなものなので，ぜひ身につけてください．最適化の専門家を自称している人でも双対性を使えない場合がよくあるような印象を受けます (暴論かもしれませんが)．どのような場面で役立つのかという一端しかこの授業ではご紹介できないかと思いますが，最適化を用いる様々な場面で双対問題は役立ちます．今後最適化問題を扱うことがある場合に，双対性をぜひ頭の片隅においてみてください．
  • 双対問題は院の受験で勉強したが少し抜けてきたところがあるので復習頑張りたい。
    -- はい，重要な概念なので，ぜひ復習してください．
• 10/11 (2) 線形計画法の復習 (1)：線形不等式系と凸多面集合
  • コメントをありがとうございました．次回は残った部分からはじめます．
  • ありがとうございます
    -- ありがとうございます．こちらのコメントは10:46に投稿されてました．できれば授業後に提出してください．
  • ありがとうございました．
    -- ありがとうございました．こちらのコメントは12:03に投稿されてました．
  • 講義ありがとうございました。
    -- こちらこそありがとうございました．
  • 本日もためになる講義ありがとうございました
    -- こちらこそありがとうございました．
  • 丁寧な説明で分かりやすかったです．ありがとうございました．
    -- 分からない部分が出てきたら，ぜひ質問をお願いします．
  • 講義教室があまりにも寒く，休憩中に撤退してしまいました
    -- 授業開始時にも述べたのですが，調整できませんでした．すみません．空調について，いま問合せをしてますので，次回以降は対処できると思います．
  • 今日の講義は内容がちょっと多いです。確かに全部覚えるのは難しいです。ありがとうございました。お疲れ様でした。
    -- そうですよね．線形計画法は復習のつもりでやっていますが，はじめての方には多かったと思います．ぜひ見直してください．
  • 第2回ありがとうございました。問題が難しいためか細分化され分類項目が多いなと感じました。
    -- もう少しうまくまとめられるとよかったのですが，それもなかなか難しく，ひととおりのものをすべて定義してしまう形になってしまいました．ただ，定義はひととおりしているので，注意深く理解すれば，あいまいなところはないと思います．
  • 用語が多くて疲れました......よく復習しておきます。
    -- はい，私も疲れました (-_-;
  • 線形部分空間やアフィン部分空間の部分が理解するのに少し時間がかかったのでそこを復習したいと思います。
    -- 実際に自分で例を作ってみると，理解が進むと思います．試してみてください．
  • 凸多面体集合について理解しきれていないので,復習しておきたい.
    -- 「凸多面集合」か「凸多面体」ですね．用語は正しく使えるようにしてください．
  • 本日の学習も大変興味深く勉強になりました。凸多面集合に関してあまり深い知識がなく勉強したりない部分が多く感じたのでしっかり復習を行っていきたいと感じました。
    -- はい，ぜひ復習をしてください．
  • 単語としては知ってたけど、定義までは知らなかった内容が多かったので面白かったです
    -- 定義を通して理解することが重要ですね．何事にも定義があると思って接してみてください．
  • たくさんの定義が出てきたので、整理のためにざっと復習しておきます。
    -- はい，ぜひ復習をしてください．
  • 今回の授業では用語を多く学ぶことができました．今後授業内でよく使う用語だけでも覚えておけるように整理して復習しておきたいと思います．
    -- はい，ぜひ整理しておいてください．
  • 4次元立方体は想像できなかった。
    -- 次回，想像の仕方を少し述べます．お楽しみに．
  • 面は平面のことを言うものかと思っていましたが、次元に関わらず面と呼ぶんですね。
    -- そうですね．皆さんが想像する凸多面体は3次元凸多面体が多いと思います．そのときは，2次元面のみを面と呼ぶことが多いと思います．一方で，高次元の凸多面集合を考えるときは，授業で定義したものはどれも同じく「面」と呼びます．用語法が普段の生活の場とは異なるので，注意してください．
  • 最適化の分野だと，他の分野ではあまり聞かない「妥当〇〇」のような言葉がでてきて面白いのですが，ニュアンス的には十分含むみたいな感じなのでしょうか？
    -- 「妥当不等式」の場合は，「必ず満たされる」といったニュアンスのように感じます．凸多面集合の点によって「必ず満たされる不等式」なので，妥当不等式と呼ばれる，といった雰囲気です．英語では valid inequalityと呼びます．
  • 非常に丁寧な解説でよく理解することができた。凸という字の形が凸集合ではないのは矛盾している気がした。
    -- よく言われます．:-) 「凸」という漢字を3つ組み合わせると「凹」ができます．試してみてください．
  • 錐線形計画を研究しているところで，線形不等式系に錐制約(ただし凸)を含めた系に対しても面などを定義しても良いのではないかと考えました．
    -- 実際，任意の凸集合に対して面が定義できます．ただし，授業で紹介したような形とは違う定義をします．この辺りは細かい話がたくさんあるのですが，それによって凸集合の理論は面白くなっています．
• 10/4 (1) 整数計画法と線形計画法
  • コメントをありがとうございました．以下のように掲載されます．
  • ありがとうございました．
    -- 今後ともよろしくお願いします．
  • 4,5年ぶりの内容で懐かしさを感じた
    -- ということは，おそらく今回の内容は復習だったのだと思います．もしかしたら，ずっと復習が続いてしまうかもしれませんが，1つの事項を様々な方法で説明する (理解する) のは，多面的な視点を養うのに重要なので，ぜひ理解を深めてください．
  • 休憩助かりました。
    -- 私も助かります．;-)
  • 最適化問題を解くような授業は初めて受講しているのですが，非常にわかりやすく，興味を惹かれる内容でとても楽しく学ぶことができました．専門外ではありますが，考え方は非常に勉強になるので，今後も身につけるために頑張りたいと思いました．本日はzoomで受講させていただきましたが，時折接続が悪く，言葉が聞こえなくなってしまう時間がありました．問題なく受講することはできましたが，一応報告させていただきます．
    -- ネットワーク接続は教室からUEC Wirelessで行っています．UEC Wirelessはつながりにくくなることがあるので，その不運に遭遇したのかもしれません．その点はご了承ください．(なお，教室で受講すれば，接続の問題は解消します．気になる場合は，ぜひ教室で受講してみてください．)
  • 整数計画法は知識を深めたいと思っていた分野なので今後の授業が楽しみです。
    -- はい，楽しんでいただけるように進めていきます．:-)
  • スライドも非常にわかりやすく、先生の説明も密度が高くとても充実した授業でした.
    -- よく「早口だ」といわれるのですが，どうせ皆さんは動画とか倍速で見るわけなので，早口であることはあまり気にしないことにしています．ただ，早すぎて分かりにくいこともあるかもしれません．そのときは，部分は質問などをしてください．
  • オンデマンド形式で受けようと思うのですが授業動画は授業日(火曜日)のうちに公開されますか？
    -- できる限り授業日のうちに公開しようと思っていますが，いろいろな都合でうまくいかないこともあるかもしれません．その点はご了承下さい．
  • 講義内容が濃く,整数計画法の考え方や線型計画法との関係が興味深かった.
    -- 次回以降，この視点を深堀りしていきます．お楽しみに．
  • 線形計画問題で3変数以上になった場合、図を書いても中々分かりづらいのかと思いますが解けるものなのでしょうか？
    -- 図を書かずに解くことになります．次回以降の内容になります．
  • 私の取り組んでいる研究の手法では、整数計画法を用いた手法が最も有力です。今後整数計画法を提案する手法に用いたいので、この講義で整数計画法のアルゴリズムをより理解したいと思います。
    -- はい，皆さんの生活や研究に活かしていっていただけると，私としてもうれしいです．
  • スライドのページの振られ方がよくわからない箇所がありました．例えば，45枚目と46枚目にはいずれにもp.24と割り当てられていますが，ページを別々にしたほうが良いと思いました．
    -- PDFファイルになっているので，いわゆる「パラパラマンガ」のようになっている部分は，ページ番号が同じになっています．「どこでページを分けるのか」という点について，あまり統一的な見解を私が持っていないので，もしかしたら分け方が場合によって異なっているかもしれません．分け方についてよい方法 (見解) がありましたら，教えていただけるとありがたいです．
  • 整数計画問題をとくソルバーはgurobiが現時点で最も速いですか?
    -- 速さの測定には様々な方法があるので，それに依存します．しかし，一般的には「gurobiが現時点で最も速い」と認識されることが多いです．Hans Mittelmannという研究者が，最適化ソフトウェアのベンチマーキングを精力的に行っていますが，整数計画法のソフトウェアも対象になっています．こちらをご覧ください．「MILP Benchmark - MIPLIB2017 (6-30-2022)」というところを見ていただくと，この中ではgurobiがよい成績を残していることが分かります．
  • 今まで整数計画問題を、とりあえずとく問題として扱っていたが、どのようなものに使われているかがよくわかってとても興味が湧いた。自分達の身近でどう役立つかもっと知りたい。
    -- いろいろなところで使われています．例えばこちらをご覧いただくと，整数計画法に限らず，最適化手法やオペレーションズ・リサーチが様々な場面で使われる (あるいは，使える) ことが分かります．ただ，こちらの情報は割と古いので，その点はご注意ください．
  • 答えを整数に限定すると難しくなるのは、この分野に触れない限りは中々に非直観的なことだなと思いました
    -- そうですね．たしかに直観的ではないと思います．何事に関しても「正しい直観を養う」というのは重要だと思います．正しい直観があれば，細かい議論をせずに，大まかな意思決定を行うことができるようになります．
  • 整数制約がある方が解の候補が減って計算は速くなると予想していたので、逆に難しくなると知り驚きました。
    -- 「なぜ難しくなるのか」という気分は今後の授業の中で分かってくるかもしれません．
  • 整数計画問題のような離散的な問題が計算困難となるのは剰余演算と関係があるのでしょうか？
    -- 根本的な理由は分かっていないと思います．「剰余演算と関係があるのか？」という視点は重要かもしれません (整数全体の集合は四則演算で閉じていないので)．ちなみに，2つの自然数の最大公約数を計算するアルゴリズムとして「ユークリッドの互除法」というのがありますが，これと整数計画法が深く関係していることは知られています．この考察を追究すると，特殊な整数計画問題に対するアルゴリズムが得られることも知られています．ただ，そのようなアルゴリズムが現実的な整数計画問題を解くために使われていることはないように思います．
  • 今日の講義はありがとうございました。スライドも流れも非常にわかりやすいです。
    -- それはよかったです．何か分からないところがでてきたら，ぜひ質問をしてください．
  • 「良い」モデル化について、モデルの「良さ」がどのように定量的に評価できるのかどうか、強い関心があります。
    -- その一端はこの講義の中で触れられることになると思います．一方で，一つの尺度でモデルの良さを定量化するのはなかなか難しく感じます (つまり，研究課題としてはとてもよいものだと思います)．現状では，「実際に速く解ける」ようなモデル化がよいモデル化であると考えられることが多い気がします．そして，経験則として「このようなモデル化を行うと，速くとける」という観察がたくさんある，といった状況であると思います．しかし，この考え方はアルゴリズムやソフトウェア，ハードウェアに依存するものになります．そういうものに依存せず，しかも有効である (つまり，確かにモデルの良さを測っているような) 尺度ができると，モデルの比較を定量的に行えるようになり，とても有用だと思います．
  • 変数のとりうる範囲が整数のときは「整数計画問題」と呼びますが，その他にも変数のとりうる範囲によって特別な呼称のある線形計画問題はありますか？ (例えば「01整数計画問題」なんかは知っています)
    -- 最適化問題の分類は，たいてい「目的関数の形状」と「制約の形状」で行われます．線形計画問題に限定すると，例えば，各変数 $x_i$ に対して，「$\ell_i \leq x_i \leq u_i$」という制約があり，つまり，変数 $x_i$ の取りうる値に対する下界 $\ell_i$ と上界 $u_i$ が定められているような問題はbox制約つき線形計画問題 (box-constrained linear program) と呼ばれることがあります．
  • 等式標準形にはstandard form、不等式標準形にはcanonical formという訳が与えられていて、standardとcanonicalをどのように使い分けるのか気になりました。
    -- 英語を日本語に訳しているので，standard formを等式標準形に，canonical formを不等式標準形に訳していると捉えてください．ただ，直訳をすると，standard formは「標準形」，canonical formは「規準形」とすべきなのかもしれません (実際に，そのような訳語を充てる文献を見たことがあるような気もします)．ただ，これは分かりにくいですし，何がstandardで何がcanonicalなのかという判断もあいまいであるように思いますので，私としては「不等式標準形」と「等式標準形」という用語を推しています．

• 1回の期末試験により評価を行う予定でいますが，社会情勢により変更となる可能性もあります．
• 期末試験
  • 日時：1月31日 (火) 2限 (10:40-12:10)
  • 教室：西8-132 (対面授業を行っている教室と同じ)
  • 注意：A4用紙2枚両面に自筆記入したもののみ持ち込み可

• こちらをご覧ください

• 10/4 (1) 整数計画法と線形計画法
• 10/11 (2) 線形計画法の復習 (1)：線形不等式系と凸多面集合
• 10/18 休み (体育祭)
• 10/25 (3) 線形計画法の復習 (2)：単体法と双対定理
• 11/1 (4) 線形計画緩和
• 11/8 (5) 整数計画モデリング (1)：組合せ最適化問題
• 11/15 (6) 整数計画モデリング (2)：より複雑な問題
• 11/22 (7) 整数計画モデリング (3)：離接計画
• 11/29 (8) 分枝限定法
• 12/6 (9) 切除平面法
• 12/13 (10) 妥当不等式の追加
• 12/20 (11) 列生成法
• 12/27 お休み (国内出張)
• 1/3 休み (冬期休業)
• 1/10 (12) ラグランジュ緩和 (1)：原理
• 1/17 (13) ラグランジュ緩和 (2)：最適ラグランジュ緩和
• 1/24 (14) 前求解 まとめ
• 1/31 (15) 期末試験 予備日 (試験日となるかもしれない)

• M. Conforti, G. Cornuejols, G. Zambelli. Integer Programming. Springer, 2014.
• B. Korte, J. Vygen. Combinatorial Optimization (Sixth Edition). Springer, 2018.
• S. Martello, P. Toth. Knapsack Problems. John Wiley & Sons, 1990.
• H. Kellerer, U. Pferschy, D. Pisinger. Knapsack Problems. Springer, 2004.
• G. Desaulniers, J. Desrosiers, M. M. Solmon (eds.), Column Generation. Springer, 2005.
• D. L. Applegate, R. E. Bixby, B. Chvátal, W. J. Cook. The Traveling Salesman Problem: A Cumputational Study. Princeton University Press, 2006.

• Traveling Salesman Problemに関する情報源 (William Cookによる．W. Cookは巡回セールスマン問題を厳密に解く研究における第一人者．)
• Robert Bixbyの講演 (2021)「Optimization: Past, Present, Future」 (YouTube動画．Robert Bixbyは整数計画問題を解くアルゴリズム設計とソフトウェア開発における第一人者．)

• 離散最適化基礎論 (2021年度) テーマ：グラフの準同型
• 離散最適化基礎論 (2020年度) テーマ：マッチング
• 離散最適化基礎論 (2019年度) テーマ：離散最適化における計算困難性
• 離散最適化基礎論 (2018年度) テーマ：理想グラフに対する組合せ最適化
• 離散最適化基礎論 (2017年度) テーマ：幾何的被覆問題
• 離散最適化基礎論 (2016年度) テーマ：グラフの木分解
• 離散最適化基礎論 (2015年度) テーマ：組合せ最適化におけるマトロイドの役割
• 離散最適化基礎論 (2014年度) テーマ：組合せ最適化における線形計画法の利用
• 離散最適化基礎論 (2013年度) テーマ：局所探索法の理論的側面
• 離散最適化基礎論 (2012年度) テーマ：ゲーム理論における離散構造とアルゴリズム