はじめに

本サイトは，講談社より出版された拙著「しっかり学ぶ数理最適化」のサポートページです．本書の執筆では内容から記述まで十分な時間をかけて検討しましたが，それでも完璧にはほど遠く，読者の皆様には不便をおかけした点も少なからずあると思います．このサポートページを通じて，それらの問題点を少しでも解消したいと思います．

正誤表

正誤表はこちらです．指摘や質問などあれば umetani@ieee.org まで連絡をお願いします．（最終更新：2024/12/14）

ページ順に整列した正誤表をこちらに用意しました．

書評

• 日刊工業新聞，2021/6/29，朝刊19面．

• 藤井浩一，書評「しっかり学ぶ数理最適化 —モデルからアルゴリズムまで—」，オペレーションズ・リサーチ学会機関誌 66 (2021), 321-322.

• 石井一夫，連載ビブリオ・トーク—書評—「しっかり学ぶ数理最適化 モデルからアルゴリズムまで」，情報処理 63 (2022), 442-443.

• 原田耕平，書評「しっかり学ぶ数理最適化 モデルからアルゴリズムまで」，計測と制御 61 (2022), 772.

関連資料

本書に関連するスライド資料やブログ記事を紹介します．更新情報は以下の通りです．

• 2023/5/22，「制約なし非線形計画問題」「制約つき非線形計画問題」を追加しました．

• 2022/6/30，「局所探索法とメタヒューリスティクス」を追加しました．

• 2022/4/13，「最大流問題と最小費用流問題」を追加しました．

• 2021/8/9，「資材切出し問題と列生成法」「「しっかり学ぶ数理最適化」裏話その１」追加しました．

• 2021/3/12，「分枝限定法と切除平面法」を追加しました．

• 2021/2/8，「貪欲法と動的計画法」「組合せ最適化問題の近似解法」を追加しました．

• 2020/12/16，「計算の複雑さとNP困難」を追加しました．

• 2020/10/6, 「60分で学ぶ数理最適化」「線形計画法入門」「整数計画問題の定式化と解法」を追加しました．

Q&A

• 本書が想定する読者はどのような人でしょうか？
  大学1-2年生で微積分，線形代数の授業を受けていれば読みこなせると思います．アルゴリズムとデータ構造の授業を受けていればなお良しです．私自身は大学2-3年生向けの入門書のつもりで執筆しましたが，原稿をチェックしていただいたD先生とT先生には口を揃えて「これは入門書じゃないでしょ？」と言われたので，やや難しいと感じる人がいるかも知れません．

• 本書の特色を教えて下さい．
  数理最適化の基本的な知識を一通り習得できる入門書を目指して，できる限り多くの最適化問題とアルゴリズムを紹介しました．一般的な教科書の約2倍のボリューム(368ページ)あります．また，各章の始めには現実問題を最適化問題にモデル化するための具体的な手法を紹介するように努めました．

• どのあたりが「しっかり学ぶ」なんでしょうか？
  数学から遠い分野を専門とする人には流し読みできる本ではないこと，数理最適化の幅広いトピックを含んでいることから，そのように名付けました．私自身は本書を入門書だと思っていますので，数学から近い分野を専門とする人にはもの足りないのは自然なことだと思います．

• 数学書としては定義や証明など数学的な厳密さが足りないのではないでしょうか？
  本書は直観的な理解を優先しており，多くの数学書のように定義，定理，証明というステップを踏むように構成していません．もちろん数学的な厳密さを維持しつつ話を進めることは大事なのですが，一方で，話のスムーズな流れが失われて初学者がイメージをつかめなくなることが少なくありません（例えば，証明のためだけに数学の高度な手法が必要になり多くのページが割かれるなど）．特に，2章の線形計画はイメージをつかみづらく序盤でつまづき易いところなので，具体例や図を通じて直観的な理解を優先するスタイルで書いています．本書で直観的な理解をつかんだ後に，数学的に厳密に書かれた専門書を読むことをおすすめします．

• 数理最適化と数理計画は異なるのでしょうか？
  数理最適化はもともと数理計画と呼ばれていました．2010年に国際学会Mathematical Programming Society (MPS)がMathematical Optimization Society (MOS)に名称変更したことを受けて，国内でも数理計画を数理最適化と呼ぶことが増えました．

• 組合せ最適化を勉強したいのですが大丈夫でしょうか？
  はい．組合せ最適化の基本的な知識が一通り習得できるように構成したつもりです．組合せ最適化を勉強したい人は，まず，2章「線形計画」を勉強した後に，4章「整数計画と組合せ最適化」に進むと良いと思います．

• 表紙のモチーフはサグラダ・ファミリアでしょうか？
  はい．本書の執筆が遅々として進まない様子を，ある学生に「サグラダ・ファミリアのようだ」と揶揄された話を編集者のYさんに披露したところ，それで行きましょうという話になりました．さらに後で他の学生から「サグラダ・ファミリアでさえ完成の目処が立ったのに」と止めを刺されました．

• 2章「線形計画」で初めの定式化が不等式制約の最大化問題になっているのはなぜでしょうか？
  はじめの不等式制約の最大化問題は，原点が自明な実行可能解となる例を図に描きたかったことが理由です．ちなみに，双対定理で定式化を等式制約に切り替えたのは，単体法で得られた最適解を用いて強双対定理を証明したかったことが理由です．私自身も大いに悩んだところなのですが，説明のし易さを優先して途中で定式化を切り替えました．

• 2.2.5節の線形計画問題の例は無限ループに陥るのでしょうか？
  いいえ．この問題は無限ループには陥りません．無限ループに陥る自明でない例を作成することは容易ではなく，少なくとも6個の変数(3個以上の非基底変数)と2本の制約条件が必要であることが知られています．無限ループに陥る線形計画問題の例は以下の論文にまとめられています．
  S.I.Gass, S.Vinjamuri, Cycling in linear programming problems, Computers & Operations Research, 31 (2004), 303-311.

• 大域的収束性は，どのような初期解からアルゴリズムを開始しても最適解に到達することを指すのでしょうか？
  いいえ．大域的収束性は，どのような初期解からアルゴリズムを開始しても「局所最適解」（正確には停留点）に到達することを指します．

• NP完全問題は多項式時間では解けない問題を指すのでしょうか？
  いいえ．NP完全問題はクラスNPの中で最も難しい問題を指します．多くの研究者の長年の努力にも関わらず多項式時間アルゴリズムが見つかったNP完全問題がないため，NP完全問題は多項式時間では解けないだろうと予想されていますが，未だに証明はされていません．ちなみに，NPは non-deterministic polynomial time の略であることに注意して下さい．非決定性計算機(non-deterministic computer)と呼ばれる計算途中で生じる全ての分岐の中で正解にたどり着く経路があればそれを実行できる仮想的な計算機を用いて解ける問題の集合をクラスNPと呼びます．

• なぜ組合せ最適化問題ではNP完全ではなくNP困難と呼ぶのでしょうか？
  ある問題QがNP完全問題であるとは（1）問題QがクラスNPに含まれかつ（2）クラスNPに含まれる全ての問題が問題Qに帰着可能であることを指します．（2）しか満たさないものはNP困難問題と呼ばれます．計算量理論では，人工的に作られた難しい問題を議論から排除するためにクラスNPを導入しました．クラスNPは，アルゴリズムの出力が問題の解であるかどうか多項式時間で判定できる問題の集合を指します．組合せ最適化問題では，アルゴリズムが出力する解が最適解であるかどうかを多項式時間で判定する必要があるわけですが，多くの場合では最適解を求めることとほぼ同義なのでクラスNPに含まれるとは言えそうにありません．そのため，組合せ最適化問題はNP完全問題ではなくNP困難問題と呼ばれています．

• 2.1節の「等価な最適化問題に変形できる場合も少なくない」の「等価な最適化問題」は何を意味するのでしょうか？
  「等価」と呼ぶのは正確ではなかったと思います．変形後の問題の最適解から容易に（ほぼ自明に）原問題の最適解が導けることを指します．

• 図4.55，図4.65，図4.67の頂点が青色のネットワークと頂点が黄色のネットワークはそれぞれ何を指しているのでしょうか？
  前者は元のネットワーク，後者は残余ネットワークを表しています．説明が抜けて大変申し訳ありませんでした．

• 表2.2の相補性条件は定理2.3の相補性定理を指しているのでしょうか？
  いいえ．表中の相補性条件は式(2.126)を指しています．単体法や双対単体法は探索途中で式(2.126)を満たすものの，それぞれ双対問題と主問題の解が実行可能ではないため定理2.3の相補性定理を満たしません．記述が紛らわしくて申し訳ありませんでした．

• 式(4.22)の y1+y2=1 は y1+y2 >=1ではないでしょうか？
  どちらでも大丈夫です．実行可能領域が狭まり分枝限定法の計算効率が良くなることを期待して前者を採用しました．脚注に説明を追加すべきでしたね．

• 「A ⊃ B」は「A = B」の場合を含むのでしょうか？
  本書では「A = B」を含みません．「A = B」を含む場合には「A ⊇ B」と書いています．私自身は「A = B」を含まない流儀が一般的だと思い込んでいましたが，実際には意見が分かれるようで全く一般的ではありませんでした．申し訳ありませんでした．

• 4.2.2節や4.5.1節に現れる「問題」と「問題例」の違いはなんでしょうか？
  「問題」と「問題例」は英語でそれぞれ「problem」と「instance」と呼びます．例えば，一口に巡回セールスマン問題と言っても，都市数や各都市の配置を変えることで無数の入力データを作成できます．この入力データ(input data)のことを問題例(instance)と呼びます．オブジェクト指向プログラミングにおけるクラスとインスタンスの関係とほぼ同じだと考えると分かりやすいでしょうか．

• 4.5.2節のFF法の計算手間はO(n log n)ではないでしょうか？
  セグメント木(segment tree)と呼ばれるデータ構造を用いて各箱の残り容量を管理すれば，各反復で荷物を詰め込む箱をO(log n)時間で見つけられるので，全体の計算手間はO(n log n)になります．ただし，この実装は自明ではないので，本書では単純な実装による計算手間のO(n^2)を書きました．

• 3.3節のペナルティ関数法，バリア関数法，拡張ラグランジュ関数法において，制約なし最適化問題を解く際に，直前の反復で得られた解x^(k)を初期点に使う必要がない気がします．
  適当な解を初期点にするよりも直前の反復で得られた解の方が局所最適解に近く，制約なし最適化問題を解くアルゴリズムの収束が速くなることが期待できます．そのようなわけで，直前の反復で得られた解を使うことは合理的だと思います．

• クイックソートの最悪計算量はO(n^2)ではないでしょうか？
  たしかに，多くの教科書で紹介されている代表的なピボット(軸要素)の選択方法だと最悪計算量はO(n^2)になります．ところが，中央値をピボットに選ぶと最悪計算量をO(n log n)に抑えられることが知られています．この話題は，茨木俊秀『Cによるアルゴリズムとデータ構造』(オーム社)の4.4節および問題5.3に解説がありますので興味がある方はご参照下さい．

• 式(2.13)(2.16)の z_i >= 0 および式(2.17)の z >= 0 は必要でしょうか？
  たしかに，1-2行目の制約条件から -z_i <= z_i となり z_i >= 0 が常に成り立ちますね．誤差は非負の値を取るので z_i >= 0 と書きましたが冗長でした．

その他

• 数理最適化のウェブサイト 

• 数理最適化の参考書