過去50年間の整数線形計画法：最近の実用的進歩 — Anubis保護ページが表示される

• 論文本体の代わりに Anubisのボット確認ページ が表示され、このURLでは実際の論文内容をすぐに確認できない
• 保護ページでは、AI企業による 攻撃的なWebスクレイピング がサーバーのダウンタイムやリソースへのアクセス遮断につながり得ると案内している
• AnubisはHashcashに類似した プルーフ・オブ・ワーク を要求し、個人利用者の負担は小さい一方で、大量スクレイピングには累積コストが大きくなるよう設計されている
• この方式は暫定的な解決策であり、長期的にはフォントレンダリングのような手がかりによって ヘッドレスブラウザ を識別することに重点が置かれている
• 最新のJavaScript機能が必要なため、JShelterのようなプラグインが有効になっている場合は、そのドメインで無効化しなければアクセスできない

---

Anubis保護ページが表示される

• ページタイトルは「Making sure you're not a bot!」で、画面には 計算中 の状態が表示される
  • 難易度は 4
  • 速度は 0kH/s
• サーバー管理者がAI企業の攻撃的なスクレイピングからサーバーを保護するために Anubis を設定しており、このページが表示されている
• 大量スクレイピングはWebサイトのダウンタイムを引き起こす可能性があり、その結果すべての利用者がリソースにアクセスできなくなることがある

プルーフ・オブ・ワーク方式とアクセス制約

• AnubisはHashcash系の プルーフ・オブ・ワーク 方式を使用している
  • 個々の利用者に生じる追加負荷は無視できる水準である
  • 大量スクレイパーは累積コストが増大し、スクレイピングコストが高くなる
• 現在の方式は 暫定的な解決策 に近い
  • 目的は、フォントレンダリング方式のような手がかりによってヘッドレスブラウザを識別するための時間を確保することにある
  • 正当な利用者である可能性が高い場合には、プルーフ・オブ・ワークページを表示しない方向を目指している
• Anubisは最新の JavaScript 機能を要求する
  • JShelterのようなプラグインが必要な機能を無効化することがある
  • このドメインではJShelterまたは類似のプラグインをオフにする必要がある

[GN⁺]

Hacker News のコメント

• 商用の整数線形計画法（ILP）ソルバーが、Gurobi のように無料／オープンソースのものよりはるかに優れている理由を大枠で知りたい。
  ILP は本質的に難しすぎる問題なので、最高のソルバーは特定の部分問題向けヒューリスティックを大規模に集めた形になっており、公開領域には一般に有効な戦略がまだないのか気になっている。

  • 主な理由は、顧客と非常に密接に協力しながら問題別の高速化を実装してきたから。そしてそれを 10〜20 年続けてきた。
    混合整数線形計画法（MILP）では、分枝限定法の良い開始点を見つけてツリーを効果的に枝刈りするヒューリスティックや、分数解を切り落として目的値と整数性を改善するカスタム切除平面が重要になる。
    オペレーションズ・リサーチの研究者が特定の問題に取り組むと、自分で切除平面やヒューリスティックを書いて、Gurobi のような汎用ソルバーをかなり簡単に上回ることもある。ソルバー企業は博士号取得者や研究者のチームを雇ってこの作業を継続し、顧客の問題群で改善と回帰を追跡している。
  • 大手の商用ソルバーには、実問題に合わせて解法プロセスのあらゆる部分を調整するために多くの時間を投じられるリソースと協力的な顧客がある。ヒューリスティックもその一部だし、より単純な部分問題や近似を認識して全体問題に再び反映することも含まれる。
    オープンソースのソルバーはいくつかの要因が重なって足を引っ張られているように見える。最新の最適化開発は参入障壁が非常に高く、数学とプログラミングの両方で意味のある貢献ができる研究者／開発者がそもそも少ない。そうした能力があると、収益につながる進路がオープンソースへの貢献から離れさせるし、オープンソースプロジェクトの性質上、「顧客」がソルバー改善に必要な例、性能データ、プロファイリング結果を返してくれる可能性も低い。
    例外もあるが、従来型の商用ソルバー開発の外にあるからといって、すぐにオープンソースというわけではない。たとえば Stanford で開発された SNOPT も、いまだに商用ライセンスだ。学術界のソルバー開発は Clarabel のように特定の応用文脈で行われることが多く、問題群が狭くなりがちだ。
    他分野では、大手テック企業が既存の商用プロジェクトを買収したり、競合を牽制するためにオープンソースプロジェクトへ資金提供したりしてボトルネックを越えたこともある。ソルバーにも Ceres のような狭い例はあるが、汎用ソルバースタック全体をゼロから開発する投資は大きすぎると見なされた可能性が高い。
  • 商用ソルバーは膨大な手法のコレクションと、現在の問題にどの手法が役立つかを検知する優れたパターン検出メカニズムを持っている。
    問題構造を知っていれば、それを活用して商用ソルバーの性能を上回ることもできる。だが任意の問題なら、その可能性はほとんどない。
  • 「ソルバーは特定の部分問題向けヒューリスティックの大きなアンサンブル」という言い方は、ILP のように SAT と同等のNP困難問題なら、ほとんど自明に当てはまるのではないかと思う。
  • 核心は規模と速度だ。たとえば多くのクオンツ取引会社は、可能な限り頻繁に巨大な最適化を回している。オープンソースソルバーは、こうした問題をそもそも解けないことも多い。メモリ不足例外のような形だ。

• IBM の「ILOG」混合整数線形計画法ライブラリでリソース配分ツールを作った記憶がうっすらある。自分たちが 5 分以内に解いていた同じ問題を 20 年前に作っていたら、今でも実行中だっただろうと気づいた。
  純粋な計算性能が約 1000 倍になり、アルゴリズムも同じくらい改善されて、合計で 100 万倍ほど良くなっていたと記憶している。
  未来を予測するときに噛みしめる価値がある。ちなみにその「リソース」はダイヤモンドだった。

• 実際にこういうものがどう使われているのか気になる。数値最適化を実装すると、データ駆動型アプローチでよくある問題、たとえば信頼と悪いデータのせいで頻繁に失敗し、結局は重要人物が勘でどうするか決める構図が思い浮かぶ。

  • 職場ではスタック全体でソルバーを使っている。家庭の蓄電池と電気自動車を最適にスケジューリングするソルバー、そうした家庭数十万軒をポートフォリオとして最適スケジューリングするソルバー、そのポートフォリオを最適に取引するソルバーがある。
    EU の電力スポット価格は、毎日 1 回の巨大なソルバー実行で決まる。Euphemia を調べると、その仕組みに関する記事がある。
    最適化すべき明確な目標があり、実際のお金がかかっている分野のほとんどはソルバーだらけだ。
  • FMCG 企業では実際にこうした用途で使っている。営業担当者と配送の移動計画、生産のための機械・人員・資材リソースのスケジューリング、倉庫物流センターの在庫水準最適化がある。
    在庫については需要予測が難しく、完全自動化はされていない。
  • ケーススタディを読めばよい。
    Gurobi のケーススタディ: https://www.gurobi.com/case_studies/
    CPLEX のケーススタディの一部: https://www.ibm.com/products/ilog-cplex-optimization-studio/...
    Hexaly、以前の LocalSolver、ケーススタディ: https://www.hexaly.com/customers

• Gurobi はかなり高いと聞いた。価格情報を共有できる人がいるのか気になる。

  • 価格情報は機密なので共有できないが、単に MIP で遊びたいだけなら、非常に高価な 3 大ソルバーである XPRESS、Gurobi、CPLEX を買う必要はない。通常、学生には無料で提供される。
    オープンソース、または非商用利用なら無料のまともな MIP ソルバーが少なくとも 2 つある。
    https://highs.dev/
    https://www.scipopt.org/
  • 聞いたところでは、もちろん確認はできないが、価格帯は実質的に「お問い合わせください」の 1 つだけで、そのときにどれだけ儲けているかを把握したうえで、その一部を要求する方式らしい。
  • なぜそこまで深く隠された秘密だと思うのか分からない。コア制限付きライセンスなら、1 シートあたりおよそ1万ドルだ。
  • 遅くて間違った意思決定をするよりはずっと安い。GLPK のような無料ソルバーは小さな問題には問題ないが、多くのビジネス問題はプレミアムソルバーにお金を払わないと、必要な時間内にはほとんど解けない。Gurobi はその中で最高だ。
  • 約 10 年前に最後に確認したとき、複数ユーザーがサーバーで使うフルライセンスが約10万ドルだった。正確なシート数やサーバー数の制限は覚えていない。
    業界の多くの人にとっては十分にその価値がある、と付け加えておきたい。

• 1990年代に学習用として、Mapleでゴモリーの切除超平面の何らかのバージョンを実装した記憶がある。実用向けではなかった。この分野はかなり進歩したようだ
  「1990年代初頭にLPを解くのに実行時間が2か月必要だったとすれば、今日では1秒もかからない。最近、Bixbyは1990年から2020年までのCPLEXとGurobiという2つのMILPソルバーの機械非依存の性能を比較し、約4×10^6倍の高速化を報告した」

• こうした問題に対する機械学習/人工知能ベースのアプローチはかなり不足しているように感じる。小さな問題を解こうとする強化学習/グラフニューラルネットワークの論文例は多く見てきたが、結局はGurobiのライセンスを買って走らせるのが最善に見えることが多い
  最近、ジョブショップスケジューリングに近いスケジューリング最適化に取り組んでいたが、強化学習を使う例はあるものの、十分ではないように見える。大きな問題でそれらしい解を得るために、進化的アルゴリズムに頼ることになった
  問題をうまく定式化できるなら、オペレーションズリサーチ的なアプローチを使うほうが常に効率的なのかもしれない

  • 問題による。セキュリティ制約付きユニットコミットメント問題は、どの発電所をいつ起動するかを決める問題で、信じがたいほど複雑だが、GurobiのようなMILPソルバーはMIPギャップの範囲内で大域最適解を素早く見つけられる
    遺伝的アルゴリズムを作ることもできるだろうが、局所最小値にはまっていない答えを返す保証はない。高速に実行できるように作れるという前提も必要になる。ニューラルネットワークもやはり最適解には及ばないだろう
  • SATは標準的な**古き良き人工知能（GOFAI）**の問題であり、当然ながら機械学習系のプログラミング言語でSATソルバーを書くこともできる。その意味では、機械学習/人工知能アプローチはかなり適用可能だと思う

• 「1988年から2004年までにハードウェアは1600倍速くなり、LPソルバーは3300倍速くなって、累積の高速化係数は5 × 10^6を超えた。しかもそれはすでに20年前の話だ！」
  「著者らは2001年から2020年の間に、商用MILPソルバーで1000倍の高速化を観察した。そのうち50倍はアルゴリズム、20倍はより高速なコンピュータによるものだ」
  コンピューティングのサブ分野ごとにこうした高速化係数を集め、アルゴリズム改善とより高速なコンピュータの寄与に分解できるのか気になる
  コンパイラには「Proebstingの法則」がある。コンパイラの進歩は18年ごとに計算性能を2倍にする、という法則だ

• タイトルに [pdf] [2024] を付けるとよさそう

  • 論文リンクをそのまま付ければよい: https://inria.hal.science/hal-04776866v1/document
  • リンクはPDFではなく、概要を指している