ドイツのzib研究所の設立者であられるマーティン・グレッシェル先生は、しばしば講演でクイズを出されます。以下はその抜粋です。回答は生成AI（Gemini 2.0 Flash Thinking Experimental）に作ってもらいました。
最初の整数方程式系は？
最初の整数方程式系を考えた「人」を特定するのは非常に難しい問題です。なぜなら、数学の歴史は長く、アイデアは徐々に発展していくものだからです。しかし、いくつかの重要なポイントを考慮することで、より良い理解が得られます。
初期の段階:
- 古代バビロニア: 紀元前2000年頃の粘土板には、複数の未知数を含む連立一次方程式を解く問題が記録されています。これは、整数解を求めるものではありませんでしたが、複数の関係式を扱うという考え方の萌芽と言えるでしょう。
- 古代ギリシャ:
イスラム黄金時代:
- アル・カラジ (10世紀): 彼はディオファントスの研究を発展させ、より複雑な不定方程式を扱いました。彼の著作には、複数の未知数を含む問題を解く例があり、連立方程式の概念に近づいています。
- アブー・カーミル・シュジャー (9世紀): 彼の著作には、複数の不定方程式を組み合わせたような問題も含まれており、連立ディオファントス方程式の初期の例と見なせるかもしれません。
ヨーロッパ中世以降:
- レオナルド・フィボナッチ (13世紀): 彼の『算盤の書』には、複数の条件を満たす数を求める問題が含まれており、現代的な連立ディオファントス方程式の考え方に近いものが見られます。
結論:
特定の「最初の人物」を断定することはできません。しかし、以下のように考えるのが妥当でしょう。
- 古代バビロニア人 は、複数の未知数を含む関係式を扱うというアイデアの初期の萌芽を示しました。
- ディオファントス は、個々の整数解を求める方程式（ディオファントス方程式）を体系的に研究した最初の重要な人物です。
- イスラム黄金時代の数学者たち (特にアル・カラジやアブー・カーミル・シュジャー) は、ディオファントスの研究を発展させ、複数の不定方程式を組み合わせた問題に取り組み、連立ディオファントス方程式の概念をより明確にしました。
したがって、「最初の整数方程式系を考えた人」を一人に絞ることは難しいですが、ディオファントスとイスラム黄金時代の数学者たちが、この分野の発展に大きく貢献したと言えるでしょう。 彼らの業績が、後の数学者たちが連立ディオファントス方程式を体系的に研究する基礎となりました。
ディオファントスの墓碑銘はクイズになっています。
ディオファントスの人生は、6分の1が少年期、12分の1が青年期であり、その後に人生の7分の1が経って結婚し、結婚して5年で子供に恵まれた。ところがその子はディオファントスの一生の半分しか生きずに世を去った。自分の子を失って4年後にディオファントスも亡くなった。
正解は84歳です。
整数最適化の最初の解法は？
整数最適化の最初の体系的な解法として一般的に認識されているのは、ラルフ・ゴーモリー (Ralph Gomory) によって開発された 切除平面法 (Cutting Plane Method) です。
ゴーモリーは1958年に、「Algorithm for Integer Solutions to Linear Programs」 という論文を発表し、混合整数線形計画問題を解くための最初の有限ステップアルゴリズムを提示しました。このアルゴリズムは、線形緩和問題を解き、その解が整数でない場合に、実行可能領域を狭めるような線形不等式（切除平面）を繰り返し追加することで、最終的に整数最適解を得るというものです。
それ以前にも整数最適化の問題は認識されていましたが、体系的な解法は存在しませんでした。ゴーモリーの切除平面法は、その後の整数最適化の研究における基礎となり、多くの改良や派生アルゴリズムを生み出しました。
ただし、歴史的な観点から見ると、以下のような点も考慮に入れる必要があります。
- 総当たり法: 最も単純なアプローチとして、実行可能な整数解をすべて列挙し、その中で最も良い解を選ぶという方法がありますが、これは実用的ではありません。
- 分枝限定法 (Branch and Bound): この手法も整数最適化の基本的な解法ですが、ゴーモリーの切除平面法とほぼ同時期に開発が進められました。Land と Doig によって1960年に発表された論文が有名です。
したがって、最初の「解法」 という点で言えば、総当たり法が概念的には最も古いかもしれませんが、最初の「体系的な解法」 としては ゴーモリーの切除平面法 が最も有力な候補となります。
その後、分枝限定法も非常に重要な解法として発展し、現代の整数最適化ソルバーでは、切除平面法と分枝限定法を組み合わせた 分枝カット法 (Branch and Cut) が主流となっています。
まとめると、整数最適化の最初の体系的な解法は、ラルフ・ゴーモリーによる切除平面法（1958年） であると考えるのが妥当です。
整数最適化の最初の商用ソルバーは？
整数最適化の最初の商用ソルバーを特定するのは、厳密には難しい問題です。なぜなら、「商用ソルバー」の定義や、初期のソフトウェアの記録が完全ではないためです。しかし、有力な候補としてよく挙げられるのは、ケトロン (Ketron) 社の Mathematical Programming System (MPS) です。
ケトロン MPS (1970年代初頭)
ケトロンは、1970年代初頭に Mathematical Programming System (MPS) というソフトウェアを開発しました。このMPSは、当初は主に線形計画問題 (LP) を解くためのものでしたが、比較的早い段階で整数計画問題 (IP) を解く機能も搭載されました。
重要なポイント:
- 初期の代表的なソルバー: ケトロン MPSは、初期の商用最適化ソルバーとして非常に有名で、多くの企業や研究機関で利用されました。
- 線形計画と整数計画の両方に対応: 当初はLPが中心でしたが、早い段階でIP機能が追加された点が重要です。
- 商業的な成功: ケトロンは、MPSの成功によって最適化ソフトウェアの主要なベンダーの一つとなりました。
他の候補や注意点:
- IBMのMPSX: IBMも同時期に Mathematical Programming System Extended (MPSX) というソルバーを開発していました。こちらもLPとIPの両方に対応していましたが、ケトロンMPSとどちらが先かという点については議論があります。一般的には、ケトロンMPSの方が、独立したソフトウェアベンダーとしての成功を収めた最初の例として認識されています。
- 時期の曖昧さ: 初期のソフトウェアのリリース時期や機能追加の時期は、明確な記録が残っていない場合があり、厳密な「最初」を特定するのが難しい理由の一つです。
- 定義の問題: 「商用ソルバー」の定義も重要です。大学の研究室で開発されたソフトウェアが、後に企業にライセンス供与された場合など、線引きが曖昧なケースも考えられます。
結論として、整数最適化の最初の商用ソルバーとして最も有力な候補は、ケトロン社の Mathematical Programming System (MPS) であると言えるでしょう。 IBMのMPSXも重要な初期のソルバーですが、独立したソフトウェアベンダーとしての商業的な成功という点で、ケトロンMPSがよく引き合いに出されます。
初期の最適化ソルバーの開発は、計算機資源の制約やアルゴリズムの発展段階など、多くの困難を伴いましたが、これらのソルバーの登場が、その後の整数最適化の発展を大きく加速させました。
グレッシェル先生の正解は、LP/89/94 for IBM 7094 (1963/64) で分枝限定法を搭載しているとのことでした。
Ketron, Inc. の設立は1970年のようなので、グレッシェル先生の方が歴史については正しいようです。
巡回セールスマン問題の解法の歴史は？
巡回セールスマン問題 (Traveling Salesman Problem, TSP) は、その単純な記述にもかかわらず、計算複雑性の理論において非常に難しい問題として知られています。都市の集合と都市間の移動コストが与えられたとき、すべての都市をちょうど一度ずつ訪問し、出発地に戻るような総移動コストが最小の経路（巡回路）を見つける問題です。この問題の解法研究は、その難しさから多くの数学者や計算機科学者を魅了し、様々なアプローチが開発されてきました。以下にその歴史を概説します。
初期 (19世紀 – 1950年代): 問題の認識と定式化
- 19世紀: TSPの原型となる問題は、数学者 ウィリアム・ローワン・ハミルトン によって考案された ハミルトン路問題 と関連があります。ハミルトン路問題は、グラフ上のすべての頂点をちょうど一度ずつ通る経路を見つける問題で、TSPの制約の一部と共通しています。
- 1930年代: TSPは、現代的な形で初めて数学的な問題として認識されました。カール・メンガー がこの問題を研究し、その重要性を指摘しました。
- 1954年: ダントツィヒ、フルカーソン、ジョンソン が、49の米国の都市を巡るTSPインスタンスを初めて最適に解きました。彼らは、線形計画法と切除平面法を組み合わせた手法を用い、その後の厳密解法の基礎を築きました。
厳密解法 (Exact Algorithms) の発展 (1960年代 – 現在)
厳密解法は、必ず最適解を見つけることを保証するアルゴリズムです。しかし、TSPはNP困難な問題であるため、都市数が増加するにつれて計算時間が指数関数的に増加します。
- 動的計画法: リトル、ムール、スウィーニー、キャロル によって開発された動的計画法 (Held-Karpアルゴリズム) は、時間計算量 O(n2 2n) でTSPを解くことができます。これは総当たり法よりはるかに効率的ですが、大規模な問題には適用できません。
- 分枝限定法 (Branch and Bound): 1960年代から発展してきたこの手法は、探索空間を系統的に探索し、途中で不要な部分を枝刈りすることで効率化を図ります。TSPにおける分枝限定法では、下界値の計算に割当問題の緩和などが用いられます。
- 切除平面法 (Cutting Plane): ダントツィヒらの研究に端を発するこの手法は、線形計画緩和を用いて解を求め、整数制約を満たさない場合に、実行可能領域を狭めるような線形不等式（切除平面）を追加していくことで最適解に到達します。TSPに特化した切除平面として、サブツアー制約などが知られています。
近似解法 (Approximation Algorithms) の発展 (1970年代 – 現在)
近似解法は、必ずしも最適解を見つけるわけではありませんが、現実的な時間内で「そこそこ良い」解を見つけることを目指します。
- 貪欲法 (Greedy Algorithms): 最も単純な近似解法の一つで、例えば、現在の都市から最も近い未訪問の都市へ移動する最近傍法などがあります。しかし、一般的に精度の良い解が得られるとは限りません。
- 最小全域木に基づく近似法: 最小全域木を利用して巡回路を構築する方法です。例えば、最小全域木の辺を2回ずつ通る巡回路を作り、重複を解消する 2近似アルゴリズム や、より洗練された クリストフィードのアルゴリズム (Christofides algorithm) (1.5近似) などがあります。
メタヒューリスティクス (Metaheuristics) の発展 (1980年代 – 現在)
メタヒューリスティクスは、局所探索法や進化計算など、問題に依存しない汎用的な枠組みを利用して、良い解を探索する手法です。厳密解法や近似解法が苦手とする大規模な問題や複雑な制約を持つ問題に対して有効です。
- 局所探索法 (Local Search): 現在の解を少しずつ改善していく方法で、例えば、山登り法、焼きなまし法 (Simulated Annealing)、タブー探索法 (Tabu Search) などがあります。
- 進化計算 (Evolutionary Computation): 生物の進化の過程を模倣した手法で、遺伝的アルゴリズム (Genetic Algorithm) などが代表的です。
- 群知能 (Swarm Intelligence): 蟻のコロニーや蜂の群れの行動を模倣した手法で、蟻コロニー最適化 (Ant Colony Optimization)、粒子群最適化 (Particle Swarm Optimization) などがあります。
大規模問題への挑戦と現状
コンピュータの性能向上とアルゴリズムの進化により、TSPは数千から数万の都市数を持つインスタンスでも最適解を求めることができるようになってきました。特に、Concorde というソルバーは、切除平面法と分枝限定法を高度に組み合わせた実装であり、大規模なTSPインスタンスの解決において驚異的な成果を上げています。
現在も、TSPの研究は活発に行われており、より効率的な厳密解法や、より精度の高い近似解法、実用的なメタヒューリスティクスの開発が進められています。また、現実世界の様々な問題（物流、配送計画、配線設計など）への応用も重要な研究テーマとなっています。
まとめ
巡回セールスマン問題の解法研究は、その歴史を通じて、計算複雑性理論、最適化アルゴリズム、メタヒューリスティクスなど、多くの分野に影響を与えてきました。初期の数学的な定式化から始まり、厳密解法、近似解法、メタヒューリスティクスといった様々なアプローチが開発され、それぞれに進化を遂げてきました。今日では、大規模な問題も解決可能となり、実社会への応用も広がっています。今後も、計算機の進化や新しいアイデアの登場によって、TSPの解法研究はさらに発展していくことが期待されます。
拙著「巡回セールスマン問題への招待」（朝倉書店）によると、以下が歴史的に重要であると書かれています。
切除平面法 Dantzig, Fulkerson and Johnson (1953) 確率的解析 Beardwood, Halton and Hammersley (1959) 動的最適化 Bellman, Held and Karp (1962) 分枝限定法 Little et al. (1963) ラグランジュ緩和（劣勾配法） Held and Karp (1970) NP-完全性 Karp (1972) 最悪値解析 メトリックTSP Christofildes (1976) 多項式時間近似スキーム ユークリッドTSP Arora (1998)
