巡回販売員の問題は、知られている最も古い計算問題の 1 つです。特定の都市のリストを通過する理想的なルートを尋ね、走行距離を最小限に抑えます。単純そうに見えますが、この問題は難しいことで知られています。最短経路が見つかるまで、強引にすべての可能なルートをチェックすることもできますが、そのような戦略は、ほんの少数の都市を過ぎると維持できなくなります。代わりに、線形計画法と呼ばれる厳密な数学モデルを適用できます。これは問題を一連の方程式として大まかに近似し、考えられる組み合わせを系統的にチェックして最適な解決策を見つけます。

ただし、場合によっては、整数の量が関係する問題を最適化する必要があります。 500.7 台のソファを製造する工場最適化計画に何の意味があるでしょうか?このため、研究者はしばしば、と呼ばれる線形計画法の変形に頼ることになります。 整数線形計画法 (ILP)。生産計画、航空会社の乗務員のスケジュール設定、車両のルート設定など、個別の決定を伴うアプリケーションでよく使用されます。 「基本的に、ILP は理論的にも実践的にもオペレーションズ リサーチの基礎です」と氏は述べています。 サントッシュベンパラ、ジョージア工科大学のコンピューター科学者。

ILPを最初に策定して以来 60年以上前、研究者は ILP 問題を解決するさまざまなアルゴリズムを発見しましたが、必要なステップ数の点でそれらはすべて比較的遅いものでした。彼らが思いつくことができた最良のバージョン — 一種の速度制限 — は、問題の変数 (セールスマンが都市を訪問するかどうかなど) が 1 進値 (XNUMX または XNUMX) しか想定できないという些細なケースから生まれました。この場合、ILP には、ディメンションとも呼ばれる変数の数に応じて指数関数的にスケールするランタイムがあります。 (変数が XNUMX つだけの場合、考えられるすべての組み合わせをテストして問題を解決するには、わずか XNUMX ステップしかかかりません。XNUMX つの変数は XNUMX つのステップを意味し、XNUMX つの変数は XNUMX つのステップを意味します。)

残念ながら、変数が 1 と XNUMX を超える値を取ると、アルゴリズムの実行時間が大幅に長くなります。研究者たちは、この些細な理想に近づけることはできないか、長い間考えてきました。進歩は遅く、 記録 1980 年代に設定され、増分のみ 改善 それ以来作られました。

しかし最近 by ビクター・レイス、現在高等研究所に在籍しており、 トーマス・ロスボス、ワシントン大学では、ここ数十年で最大の実行時間の飛躍を達成しました。幾何学的ツールを組み合わせて可能な解を制限することにより、自明なバイナリの場合とほぼ同時に ILP を解くための新しい高速アルゴリズムを作成しました。その成果は2023年の論文賞を受賞しました。 コンピューターサイエンスの基礎 会議。

「この新しいアルゴリズムは非常にエキサイティングです」と彼は言いました。 ノア・スティーブンス＝ダビドウィッツ、コーネル大学の数学者およびコンピューター科学者。 「これは、ILP ソルバーにとって、約 40 年ぶりの（大幅な）改善となります。」

ILP は、特定の問題を、いくつかの不等式を満たさなければならない一連の線形方程式に変換することによって機能します。具体的な方程式は、元の問題の詳細に基づいています。ただし、これらの詳細は異なる場合がありますが、ILP 問題の基本的な構成は同じであり、研究者は多数の問題に単一の方法で対処できます。

だからといって楽な仕事というわけではありません。 1983 年になって初めて、数学者は ヘンドリック・レンストラ 証明 一般的な問題は解決可能であると考えられ、それを解決できる最初のアルゴリズムが提供されました。レンストラは ILP を幾何学的に考えました。まず、彼は ILP の中心となる不等式を正多角形などの凸形状に変えました。この形状は、ソファの生産や航空会社のスケジュールなど、解決している個々の問題の制約を表すため、形状の内部は不等式を解決できるすべての可能な値に対応し、したがって問題が解決されます。レンストラはこの形状を凸体と呼びました。問題の次元は、この形状の次元に影響します。2 つの変数を使用すると、平らな多角形の形になります。三次元ではそれは プラトン立体、などなど。

レンストラは次に、すべての整数を、数学では格子として知られる無限の格子点の集合として想像しました。 2次元では点の海のように見えますが、3次元では建物の鉄骨の接続点のように見えます。格子の次元は、特定の問題の次元にも依存します。

与えられた ILP 問題を解決するには、考えられる解が整数のセットを満たす場所、つまり凸体と格子の交点を探すだけであることを、Lenstra は示しました。そして彼は、この空間を徹底的に検索できるアルゴリズムを思いつきました。しかし、効果を発揮するには、問題をより小さな次元に分割し、ランタイムに多くのステップを追加する必要がある場合がありました。

その後数年間、数人の研究者がこのアルゴリズムをより高速に実行する方法を研究しました。 1988 年に、Ravi Kannan と László Lovász は、カバー半径と呼ばれる概念を導入しました。 借りた の研究から 誤り訂正符号、凸ボディと格子がより効率的に交差するのを助けます。大まかに言うと、カバー半径により、凸状ボディをラティス上のどこに配置しても、常に少なくとも 1 つの整数点が含まれるようになります。その結果、カバー範囲の半径の大きさによって、ILP 問題をどれだけ効率的に解決できるかが決まります。

結局のところ、理想的なカバー半径のサイズを決定することになりました。残念ながら、これだけでは難しい問題であることが判明し、Kannan と Lovász ができる最善のことは、上限と下限を検索して可能な値を絞り込むことでした。彼らは、上限 (カバー半径の最大サイズ) が寸法に応じて線形にスケールアップすることを示しました。. これはかなり高速でしたが、ILP ランタイムを大幅に高速化するには十分ではありませんでした。その後 30 年間、他の研究者はわずかに優れた成果を上げることしかできませんでした。

最終的にレイスとロスボスの突破を助けたのは、純粋に格子に焦点を当てた無関係な数学的結果でした。 2016 年、オデッド・レゲブとスティーブンス・ダビドヴィッツ 示されましたつまり、特定の形状内に格子点がいくつ収まるかを表します。 Reis と Rothvoss はこれを他の形状に適用し、ILP カバー半径に含まれる格子点の数をより適切に推定できるようになり、上限を下げました。 「最新の進歩は、実際には他の種類の形状も作成できるという認識から来ました」と Regev 氏は言います。

この新しく厳しくされた上限は大幅な改善であり、Reis と Rothvoss は ILP アルゴリズム全体の劇的な高速化を達成することができました。彼らの働きにより、ランタイムは (ログ n)^O(n)ここで、 n は変数の数であり、 O（N）線形にスケールすることを意味します n。 (この式は、二項問題の実行時間と「ほぼ」同じであると考えられます。)

「これは数学、コンピューターサイエンス、幾何学の交差点における勝利です」と彼は言いました。 ダニエル・ダドゥシュ オランダの国立研究機関 CWI の博士であり、レイス氏とロスボス氏が ILP 実行時間を測定するために使用したアルゴリズムの開発に貢献しました。

今のところ、新しいアルゴリズムは、実際にはロジスティック上の問題を解決するために使用されていません。これを利用するには、現在のプログラムを更新するのに多大な労力がかかるためです。しかしロスボスにとって、それは問題ではない。 「それは、基本的な応用ができる問題を理論的に理解することです」と彼は言いました。

ILP の計算効率をさらに改善できるかどうかについては、研究者らは依然として理想的な実行時間に近づき続けることを期待していますが、すぐにはそうではありません。 「それには根本的に新しいアイデアが必要になるだろう」とベンパラ氏は言う。