- 生産計画・乗務員配置・車両経路のように 整数単位の意思決定 が必要な最適化問題において、Victor Reis と Thomas Rothvoss が ILP の実行時間を大幅に短縮する新しいアルゴリズムを提示
- ILP は一般の線形計画法より扱いが難しく、1980年代以降は記録的な改善がほとんどなかったため、今回の結果は 数十年ぶりの大きな前進 と受け止められている
- 新しい手法は、格子と凸体の交差を扱う 幾何学的ツール を組み合わせ、取り得る整数解の範囲をより強力に絞り込む
- 核心は、2016年の格子点に関する結果を活用して covering radius の上限を引き下げた点にあり、実行時間は ((\log n)^{O(n)}) の水準まで縮小
- まだ実際の物流システムにすぐ適用されたわけではないが、ILP の理論的な速度限界にほぼ迫る結果であり、実務ソルバー改善の長期的な方向性を示している
整数制約が最適化を難しくする理由
- 巡回セールスマン問題は、複数の都市を巡る最短経路を見つける古典的な計算問題であり、可能な経路をすべて調べると都市数が少し増えただけでも手に負えなくなる
- 線形計画法は、方程式や不等式によって可能な組み合わせを体系的に扱う数学モデルである
- 現実の最適化問題では、小数点を含む答えが役に立たないことが多い
- 工場の最適化計画で 500.7 個のソファを生産せよという答えは、実際の意思決定として使いにくい
- 整数線形計画法（ILP） は、このような整数制約を持つ線形計画法の変種であり、生産計画、航空会社の乗務員スケジュール、車両経路指定のような離散的意思決定問題で広く使われている
- Santosh Vempala は、ILP を理論と実務の両面におけるオペレーションズ・リサーチの中核ツールと見ている
1980年代以降、ゆっくりとしか改善されなかった速度限界
- ILP は 60年以上前に定式化されて以来、さまざまなアルゴリズムが登場してきたが、必要なステップ数という観点では依然として遅い部類だった
- 最も単純な基準点は、変数が 0 または 1 しか取れない 二値変数 の場合である
- 変数 1 個では可能な組み合わせは 2 通り
- 変数 2 個では 4 通り
- 変数 3 個では 8 通り
- 一般に実行時間は変数数、すなわち次元に対して指数的に増加する
- 変数が 0 と 1 を超えるより広い整数値を取り得る場合、実行時間はさらに長くなる
- 研究者たちは、一般の ILP をこの単純な二値の場合の速度により近づけられないか、長年にわたって探ってきた
- 1980年代の記録以降は、漸進的な改善しか続かなかった
Lenstra が切り開いた幾何学的解釈
- 1983年、Hendrik Lenstra は一般の ILP 問題が解けることを証明し、そのための最初のアルゴリズムを提示した
- Lenstra は ILP を 幾何学的問題 に変換して扱った
- ILP の不等式は凸な図形、すなわち 凸体（convex body） として表される
- 図形の内部は、不等式を満たし得るすべての可能な値に対応する
- 変数 2 個の問題では平面多角形、変数 3 個では 3 次元立体というように次元が増えていく
- すべての整数は数学的には 格子（lattice） 上の点として見なせる
- 2 次元では点の海のように見える
- 3 次元では建物の鉄骨が交わる地点のような構造になる
- 結局、ILP を解くとは、凸体と格子の交差、すなわち可能な解が整数点と交わる位置を見つける問題になる
- Lenstra のアルゴリズムはこの空間を探索できたが、効率化のために問題をより低次元の断片に分割しなければならない場合があり、この過程が実行時間を押し上げていた
covering radius が生んだ30年のボトルネック
- 1988年、Ravi Kannan と László Lovász は、誤り訂正符号の研究から持ち込まれた covering radius の概念によって、凸体と格子の交差をより効率的に扱おうとした
- covering radius は、凸体を格子上のどこに置いても少なくとも 1 つの整数点を含むことを保証する大きさに関係する
- この値の大きさが、ILP 問題をどれだけ効率よく解けるかを左右する
- 理想的な covering radius の大きさを見極めること自体が難問だった
- Kannan と Lovász は取り得る値を上限と下限で絞り込み、上限が次元に対して線形に増大することを示した
- しかしこの結果だけでは ILP の実行時間を大幅に減らすには不十分で、その後 30 年にわたり改善幅は限定的だった
Reis と Rothvoss の新アルゴリズム
- Victor Reis と Thomas Rothvoss は、格子に焦点を当てた別の数学的結果を活用して突破口を開いた
- 2016年、Oded Regev と Noah Stephens-Davidowitz は、特定の図形の中にどれだけの格子点が入り得るかを示した
- Reis と Rothvoss はこの結果を別の図形群に適用し、ILP の covering radius に含まれる格子点数をより精密に見積もった
- この見積もりによって 上限が引き下げられ、ILP アルゴリズム全体の実行時間が大きく短縮された
- 新しい実行時間は ((\log n)^{O(n)}) で、ここで (n) は変数数、(O(n)) は (n) に線形比例することを意味する
- この表現は、二値変数問題の実行時間と「ほぼ」同じ水準と見なされている
理論的成果と実用化の距離
- Noah Stephens-Davidowitz は、新アルゴリズムをほぼ40年ぶりの主要な ILP ソルバー改善と見ている
- Daniel Dadush は、この結果を数学、計算機科学、幾何学の交点から生まれた成果だと評価する
- 新アルゴリズムは、まだ実際の物流問題を解くためには使われていない
- 現在のプログラムをこの方式に合わせて更新するには、多くの作業が必要である
- Rothvoss は、今回の結果の焦点は、根本的な応用を持つ問題に対する 理論的理解 にあると見ている
- ILP 計算効率がさらに改善する可能性は残っているが、Vempala は理想的な実行時間により近づくには、根本的に新しいアイデアが必要だと見ている
1件のコメント
Hacker News のコメント
中核的な NP完全問題のアルゴリズム上界を下げるのは常に非常に興味深いが、それが実際の実装でより速く解けることを意味するとは限らない。
混合整数計画法（MIP） ソルバーは、多くのアルゴリズムと大量のヒューリスティックを併用しており、ヒューリスティックと戦略のライブラリを積み上げてきたことが、MIPソルバーの改善がムーアの法則を上回ってきた主な理由である。
https://www.math.uwaterloo.ca/~hwolkowi/henry/teaching/f16/6...によると、1990〜2014年のハードウェア改善は6500倍だったが、ソフトウェア改善は870000倍の性能向上に寄与した。
この論文もMIPソルバーの性能向上を続けるためのパズルのピースになり得るが、そうなるとは保証されない。
新しいアルゴリズムがまだ物流問題の解決に使われていない理由が「今日のプログラムを更新するには作業が多すぎるから」という説明は、よく理解できない。
ほとんどのドメイン特化モデルは、大きな問題では Gurobi、CPLEX、FICO ソルバーを呼び出し、小さな問題では SCIP のようなオープンソースソルバーを使う。
標準の MPS形式でこれらのソルバー間でモデルを交換でき、問題の定式化は変わらず、ソルバー内部の解法だけが変わればよいのではないかと思う。
新しい実装が必要という意味なら、実装したときに世界が得る利益も途方もなく大きいはずだ。
これらのツールは数十年にわたる漸進的改善が積み重なった非常に複雑な工学的産物なので、新しい発見をこうしたエンジンに統合する方法を見つけるだけでも、かなりの研究努力が必要になりそうだ。
MPSのような形式で問題の定式化を交換する標準的な方法があるのは確かで、最近はAMPLのような代数的モデリング言語のほうがよく使われているようだが、そうした形式が提供するのは標準的な数学的定式化だけである。
実際の求解は各ソルバーに非常に特化しており、それぞれ独自のデータ構造、アルゴリズム、ヒューリスティック手法を持っている。
これらは相互に差し替え可能でもなく、意図的に公開されているわけでもなく、ソルバーのコードと全体のプロセスに関する知識なしに、外部からいくつかの数値を途中に差し込むことはできない。
誤解を解きたかった。
可能なら、そうしたもので自分で実装する作業は避けたくなる。
それでも優れた成果であることに変わりはない。
理論的な計算複雑性の観点では、「整数線形計画法」[2]の最良のアルゴリズムは格子に基づいており、最悪ケースのビッグO複雑性が最も良い。
しかし現在の実装はたいてい、(1) gmplib [3] のような任意精度有理数演算が必要でメモリを大量に消費し実際にも遅く、(2) LLL系の格子基底簡約ステップ [4] が必要だが行列の疎性を活用できない。
その結果、こうしたアルゴリズムは通常メモリに収まらず、1000x1000より大きい行列問題は開始すらできず、仮に収まっても遅すぎる。
実務の整数計画ソルバーは代わりに、SAT求解で使われるものに似たバックトラッキングアルゴリズムである 分枝限定法に基づき、各反復で元の問題のすべての変数を連続変数に置き換えた「線形計画法」問題を解く。
各線形計画問題は内点法のような多項式時間アルゴリズムで解けるが、実際には最悪ケースで指数時間の 単体法を使う。
理由は、解くべき線形計画問題同士が非常によく似ていて、単体法が実戦でその点をうまく活用するからである。
また関連アルゴリズムは、ベクトルと行列の疎性を大いに活用する。
そのため、変数数が数百万の整数計画問題でも、数日、さらには数時間以内に解く人もいる。
ソルバー実装者は絶対的に最良の理論複雑性を追っているわけではなく、離散最適化の理論と実務はある程度分かれていると言える。
それでもReis & Rothvossの論文 [1] は深い数学的仕事であり、離散数学に関心のある人にとっては、それ自体が非常に印象的だ。
Dadushの10年来の予想を解決し、昨年11月にコンピュータ科学理論の二大トップ会議の1つである FOCS で発表された。
直接的な実用性が要点ではなく、著者たちも非公式の場ではそう認めるだろう。
もちろん研究費申請書では違う言い方をするだろうが、それもゲームの一部だ。
役に立たないという意味ではなく、数学的知識を前進させるという点だけでも大きな価値があり、数世代後の研究者がこのアイデアを土台に実用的なアルゴリズムを作り、ソルバーの最先端を押し上げる可能性もある。
結局、これらのアルゴリズムは最悪ケースではすべて指数時間である。
理論では最悪ケース複雑性の指数部にある多項式を少し縮めようとするだろうが、実務家は通常、サイズnが大きくなる問題族ではなく、1つの大きな最適化問題を解きたい。
解く時間のトレンドラインの増加率よりも、目の前の大きなインスタンスを1つ解けるかが重要であり、そのインスタンスには通常、同じサイズの最悪ケースにならないようにする構造がある。
そのため工学的な選択も変わる。
[1] https://arxiv.org/abs/2303.14605
[2] min { c^T x : A x >= b, x in R^n, some components of x in Z }
[3] https://gmplib.org/
[4] https://www.math.leidenuniv.nl/~hwl/PUBLICATIONS/1982f/art.p...
要旨のほうが有益: https://arxiv.org/abs/2303.14605
n個の変数を持つ整数計画問題を解く (log(2n))^O(n) 時間の乱択アルゴリズムが得られた、という内容
つまりこの研究は理論的な結果で、R^n の凸体の構造と、それを整数格子で覆う方法の分析に基づき、従来の最良より優れた指数時間アルゴリズムを提示している
実用的な ILP の作業の多くはヒューリスティックと分枝限定法を使い、特定の問題定式化の特殊な構造を活用している
この研究がそのどちらかの役に立つかは明確ではなく、Gurobi などの人が説明してくれない限り、論文を読むだけでは判断が難しそう
些細な指摘だが、タイトルには 整数線形計画法と明記すべき
ここでは「整数」の部分がはるかに大きな違いを生むから
線形計画法については数十年前から多項式時間アルゴリズムが知られており、整数線形計画法が NP 困難
連続線形計画法も難しい
NP 困難という意味ではなく、効率的な現代的 LP ソルバーを作るには、アルゴリズムと工学の面が多く入るという意味
数値計算だけでも十分に複雑
そして多くの整数線形計画法ソルバーは連続線形計画法ソルバーに基づいている
機械学習やアルゴリズムに関心のあるソフトウェアエンジニアなら、線形計画法を学んでみる価値がある
驚くほど多くの問題が線形最適化として定式化できる
例えば大学時代、産業工学を専攻していた友人と、ビリヤード球をラックの三角形内の許容される開始位置に置くのに必要な平均最小交換回数について話したことがある
2人ともモンテカルロサンプリングで解くプログラムを書いたが、私の解法はグラフ状態空間で BFS を行い、友人の解法は線形計画法を使っていた
おそらく友人のほうがより効率的だったと思う
例として、最小全域木、二部グラフまたは一般グラフのマッチング、ネットワークフロー、マトロイド交差、劣モジュラーフローなどがある
ある LP の頂点解は、NP 完全問題の近似アルゴリズムを設計する際に活用できる興味深い性質も持つ
例えば Steiner forest 問題の頂点解には、常に値が少なくとも 1/2 の変数が存在することを証明できるため、変数を反復的に丸めて LP を解き直すと 2 近似アルゴリズムが得られる
大学院の頃は、これがこの問題に対する唯一の 2 近似アルゴリズムだった
もう1つ興味深い点は、多項式時間の 分離オラクルさえあれば、制約式が指数的に多くても LP を解けること
本当に面白く、おすすめできる
現在も オペレーションズ・リサーチの分野では驚くほど重なる部分が多いが、産業工学の卒業生の中にプログラミングをまともにできない人が多すぎて衝撃的
本当に惜しい
通常はセント単位の整数金額でしか取引できないので、整数の部分がかなり重要だったと記憶している
短いが良い記事
まだ数学を深く見てはいないが、プレプリントはこれのようだ: https://arxiv.org/pdf/2303.14605.pdf
対称性や反復を減らして問題の「空間」を一般化し単純化する方法として、空間群を直接見ているようには見えないが、そうした構造を適用できるかを見ると興味深そう
空間群を適用し、その中に分布する点、または点の集合の周囲の Voronoi セルを記述するソフトウェアを使う立場なので、効果が伝播する「不気味な」方式には慣れている [1]
数学者ではなく、ただの建築家なのでこの分野は自分の手に余るが、生成されたハニカム構造を横切る経路を見ている者として、この結果はさらに調べる価値がある
[0] https://arxiv.org/pdf/2303.14605.pdf
[1] このような作業で協業できそうな数学者を知っているなら、連絡してほしい
進行中の作業で、述べた通り数学的には自分の手に余るが、本物の専門家がさらに深く見てみる価値のある興味深い性質に出会っている
巡回セールスマン問題に関連して、Sapolskyの最新著書『Determined: A Science of Life without Free Will』に出てくる引用が興味深い
ソフトウェア開発者にどれほど関係があるかは分からないが、魅力的ではある
アリが8か所を確認しながら餌を探すとき、理想的には各場所を一度ずつだけ訪れ、5,040通りの可能な経路、つまり7!の中から最短経路を選ぶ必要がある
これは、数学者たちが一般解を見つけられないまま何世紀も取り組んできた有名な巡回セールスマン問題の一形態である
1つの戦略は、可能な経路をすべて調べて比較し、最良の経路を選ぶ総当たりだが、訪問先が10か所になるだけで可能な方法は36万を超え、15か所なら800億を超える
ところが、通常のコロニーにいるおよそ1万匹のアリを8つの餌場の問題に放つと、どのアリも自分が通った経路と2つの規則以上のことは知らなくても、総当たりよりはるかに短い時間で、5,040通りの中からほぼ最適に近い解を見つける、という内容だ
この方式はうまく機能するため、コンピュータ科学者も「仮想アリ」でこうした問題を解いており、これが現在群知能として知られているという
そして標準的な反応は「ごく単純なコンピュータアルゴリズムでもそれはできる」だ
巡回セールスマン問題でユークリッド距離、つまり各ノードが固定座標を持ち、経路コストが2点間のユークリッド距離である場合なら、最適解のε倍以内の経路を見つける多項式時間アルゴリズムも与えられる
ただしεに関しては指数的である
序文には見事な免責文言もある
「私たちは個人的に、この分野の文献には有袋類を減らし、数学をもっと増やすべきであり、コミュニティとしてこの比喩に富んだ時期を脱するべきだと考えています。これは化学が錬金術を脱したのと似ています。ただし、この一覧は列挙された論文の科学的品質についていかなる主張もしません。」
[1]: https://fcampelo.github.io/EC-Bestiary/
こうしたアリのコロニー行動をモデルにしたアルゴリズムである
他の人たちが言っているように、これはタブー探索、焼きなまし法、遺伝的アルゴリズムと同様、局所最適解を見つけるのに向いている
記事に出てくる「ソファ生産」の例のような大半のビジネス目的には、この程度で十分である
しかし「一般解」を見つけることとは違う
Sapolskyが、私たちが「一般解」をうまく見つけられないことと、アリが局所最適解を見つける能力を比較するのは、やや誤解を招くように思う
問題の一般形がNP困難ではないという意味ではなく、情報をさらに追加すれば、十分に良い解を近似したり、最適探索を扱えるようにしたりできるという意味だ
こうした見方は最初のAI「革命」のときに特に目立ち、AIを人間の知識で補強された探索問題と見る考え方が流行した
本で言おうとしている「群知能」とはこれのことなのだろうか？
多くの離散最適化問題は線形計画法に翻訳できる
SATソルバーのように、知っておくと本当に強力なツールだ
開発者として「どうして今までこれを見落としていたんだ？」と思った瞬間の1つだった
素晴らしい結果だが、おそらく実用的ではないだろう
線形計画法で内点法が単体法より理論上の計算量は良いものの、現実にはよくチューニングされた単体法がほぼ常に勝つのと似ている
内点法が実際にはたいてい遅いことについて、広く受け入れられている「理由」はあるのだろうか？
境界に縛られているより内部を通ったほうが、良い解により速く近づけそうに思えるが、高次元ではその差はあまり重要ではないのかもしれない
ここで使われている表現が少し混乱する
「彼らが考え出した最良のバージョン、ある種の速度制限は、問題の変数が巡回セールスマンが都市を訪問するかどうかのように二値、つまり0または1だけを取り得る些細な場合から来る」という文があるが、NP完全問題を些細な場合と呼んでいるのだろうか？
すべてのILPは01-ILPに還元でき、その逆も成り立つと理解していた
また「残念ながら、変数が0と1を超える値を取ると、アルゴリズムの実行時間ははるかに長くなる。研究者たちは長い間、この些細な理想にさらに近づけるかどうかを疑問に思っていた」という部分を見ると、この研究が01-ILPの下限を改善したソルバーなのか、それとも01-ILPと一般ILPの間の境界をより近づけたアルゴリズムなのか気になる