ハクソク

世界を動かす技術を、日本語で。

整数線形計画法の過去50年：最近の実用的な進展

346日前原文(inria.hal.science)

概要

  • Mixed-integer linear programming (MILP) はオペレーションズリサーチの中核技術
  • 現代のソルバーの進化により、以前は困難だった問題も 数秒で最適解 が得られるように進化
  • 輸送・物流・サプライチェーン・金融 など多様な分野で応用実績
  • 本記事は MILP解法の進展 とその計算性能向上の実例を中心に解説
  • 今後の課題や 将来の研究機会 についても言及

MILPの進化と応用分野

  • MILP は整数変数と連続変数を含む線形最適化問題の定式化手法
  • 現代ソルバー の性能向上により、大規模問題の高速解決が可能
  • 輸送、 物流、 サプライチェーン管理 など実務現場での導入事例が増加
  • 収益管理、 金融、 通信、 製造業 への応用拡大
  • 汎用性の高さが多様な産業分野での成功事例を生み出す要因

研究動向と計算性能の進歩

  • 近年は 計算実験 に基づく実用的な性能向上が注目
  • Branch-and-Cut法 による探索効率化の進展
  • Dantzig-Wolfe分解 による大規模問題の分割解法
  • Benders分解 による複雑な構造の問題への対応力向上
  • 各手法の改良が 計算時間短縮 や 解の質向上 に寄与

主な解法：Branch-and-Cut法

  • 分枝限定法 （Branch-and-Bound）と カット生成法 （Cutting Plane）の統合手法
  • 探索空間の効率的な削減 を実現
  • 実問題への適用で ソルバーの実用性能向上 に寄与
  • 新たなカットや分枝戦略の開発が継続的に進行
  • 計算実験 による性能評価が主流

主な解法：Dantzig-Wolfe分解

  • 大規模問題 を複数の部分問題に分割して並列解決
  • 列生成法 を用いた動的な変数追加
  • サプライチェーン や ネットワーク設計 で有効性を発揮
  • 実装の複雑さと 計算効率のバランス が課題
  • 分解手法の進化 が大規模MILPの適用範囲を拡大

主な解法：Benders分解

  • 問題を 主問題 と 従属問題 に分離
  • 大規模かつ複雑な制約構造 への対応力強化
  • 収束性向上 のためのカット生成アルゴリズムの進展
  • 運用計画 や エネルギーシステム設計 での実用例
  • 並列計算 やハイブリッド手法の研究が進行中

今後の課題と研究機会

  • 大規模データ や 不確実性 を含む問題への対応
  • 計算資源の有効活用 と 分散処理技術 の発展
  • 新たなアルゴリズム や ハイブリッド手法 の開発
  • 機械学習 との連携による解法選択やパラメータ調整の自動化
  • 理論的限界の克服 と 実務応用の拡大 が今後の焦点

Hackerたちの意見

Gurobiって結構高いって聞いたんだけど、価格の詳細を教えてくれる人いる？

└

価格の詳細は機密だから共有できないけど、MIPをちょっと試したいだけなら、XPRESS、Gurobi、CPLEXのような高いソフトを買う必要はないよ。学生には無料で使えることが多いけどね。オープンソースで非商用利用に無料のMIPソルバーが少なくとも2つあるよ： https://highs.dev/ https://www.scipopt.org/

└

聞いた話なんだけど、確認はできないけど、彼らの価格設定は「電話して」ってだけらしい。そこで、どれくらいお金を稼いでるかを聞いて、その一部を要求してくるみたい。

└

なんでみんなそんなに秘密にしてると思うのか分からないけど、コア制限ライセンスで約10万だよ。

└

最適じゃない決定をゆっくりするよりはずっと安いよ。小さい問題には無料のソルバーで十分だけど（例えばGLPK）、ビジネスの問題は、プレミアムソルバーにお金を払わないと、必要な時間内に解決するのはほぼ不可能だよ（Gurobiが一番いい）。

└

Gurobiには時間単位で支払うクラウドサービスがあるよ。フルの非学術ライセンスは結構高いけどね。

└

最後に確認したのは約10年前だけど、複数ユーザー用のフルライセンスがサーバー上で約10万ドルだったかな。正確な座席数やサーバー数の制限は覚えてないけど、業界の多くの人にとってはその価格に見合う価値があると思うよ。

└

値段は安くないけど、実際にはかなりリーズナブルで、無料のソルバーと比べて品質もすごくいいよ。MILPが必要な製品を作ってるなら、投資する価値はあると思う。

└

一番良いMIPソルバー（CPLEX、GUROBI、FICO）は、学術関係者でない限り、すごく高いよ。無料のものは小さな問題には十分だけどね。Mosekみたいなものはかなり手頃で、良い中間的な選択肢だよ。ほとんどの組織にとって、そのコストは得られるものに対して妥当だと思う。

└

うちらにとっては、CPLEXの10倍以上の価格だったよ。

タイトルに[PDF] [2024]が必要かも

└

そのリンクはPDFじゃなくて、要約に飛んでるよ。

└

論文の参照を追加すればいいよ： https://inria.hal.science/hal-04776866v1/document

整数線形計画って、そんなに複雑そうには聞こえないね。

└

旅行セールスマン問題をILP問題としてエンコードできるから、結構難しい問題だよ。

└

でも、線形計画よりは難しいかな。

└

特定の条件を最もよく満たす整数を見つけなきゃいけないんだ。それは実数とは根本的に違うよ。見た目は他の数値問題と同じだけど、一般的な解はなくて、特定のクラスに対する（とても良い）ヒューリスティックしかないんだ。

└

それはすごくリアルだね。

└

グラフの頂点3色塗り（G3C）はNPかつNPハード、つまりNP完全（NPC）なんだ。一般的なILP問題を解けるなら、一般的なG3Cも解けるという結果がある。充足可能性もNPかつNPハード、つまりNP完全（NPC）だ。だから、ある定義の下ではG3Cと同等なんだ。一般的なILP問題を解けるなら、一般的なG3Cも解けるという結果がある。任意のG3C問題を解けるなら、整数を因数分解できるという既知の結果もある。整数の因数分解（FAC）の問題はNPCではないけれど、今日のコンピュータ環境では整数の因数分解が非常に重要だ。だから、任意のILP問題を解けるなら、現在安全だと思われているいくつかの暗号アルゴリズムを破ることができる。つまり、ILPは解くのがかなり難しい問題だってことがわかる。多くの人を惑わせるのは、NPC問題のランダムなインスタンスは簡単なことが多いってこと。難しいインスタンスの核心は、問題が大きくなるにつれて相対的に小さくなるから、例えばランダムなグラフを選ぶと、頂点3色塗りを見つけるのはたぶん簡単だし、存在しないことを示すのも簡単だろう。

90年代にMapleでGomoryカッティングハイパープレーンのバージョンを実装したのを覚えてるよ（学習用で、実用ではなかったけど）。この分野は進歩したみたいだね… > 1990年代初頭にLPを解くのに2ヶ月かかってたとしたら、今は1秒もかからないだろうね。最近、Bixbyが1990年から2020年までのCPLEXとGurobiという2つのMILPソルバーの機械非依存のパフォーマンスを比較して、約4×10^6倍のスピードアップを報告してたよ。

IBMの「ILOG」混合整数線形計画ライブラリを使ってリソース配分ツールを作ったことをぼんやり覚えてるんだけど、もし20年前にそのツールを作っていたら、今解決している同じ問題を5分で解決できていたと思う。確か、コンピュータの生の処理能力は約1000倍に増え、アルゴリズムも同じくらい改善されて、合計で100万倍の改善があったんだ。未来を予測する時に考える価値があるよね！ちなみに、その「リソース」はダイヤモンドだったんだけど…。

誰か、商用のILPソルバー（例えばGurobi）が無料やオープンソースのものよりもずっと優れている理由をざっくり説明してくれない？ILPが本質的に解くのが難しいからなのか（NP困難なのは知ってるけど）、最良のソルバーは特定のサブ問題に対するヒューリスティックの大規模な組み合わせで、一般的な「良い」戦略が公に出てこないからなのかな？

└

ソルバーは特定のサブ問題に対するヒューリスティックの大規模な組み合わせだ その発言はNP困難なものにはどんなものにも当てはまるんじゃないの？（ILPはSATと同じだからね）

└

スケールとスピードだね。例えば、ほとんどのクオンツトレーディング会社は、できるだけ頻繁に大規模な最適化を行ってる。オープンソースのソルバーは、問題を解けないことが多い（OOM例外とか）。

└

最良のソルバーは特定のサブ問題に対するヒューリスティックの大規模な組み合わせだ 大手の商用ソルバーは、リアルワールドの問題に合わせて解を調整するのに多くの時間を投資できるリソース（そしてその手助けをしたいクライアント）がある。ヒューリスティックもその一部だし、シンプルなサブ問題や近似を認識して、それを全体の問題にフィードバックすることも含まれてると思う。OSSソルバーは、いくつかの問題の組み合わせによって制約を受けているのが大きいと思う：（1）最先端の最適化開発の参入障壁が非常に高くて、数学やプログラミングに有用に貢献できる研究者や開発者がほとんどいないこと、（2）もし（1）ができるなら、たくさんお金を稼げるキャリアパスがOSSへの貢献から遠ざけること、（3）OSSプロジェクトの性質上、「顧客」が本当に必要な例やパフォーマンスデータ、プロファイリングを提供してくれる可能性が低いこと。もちろん（2）には例外もあるけど、伝統的な商用ソルバー開発の外にいるからといってOSSである保証はない（例えば、スタンフォードで開発されたSNOPTは商用ライセンスのままだし）。多くの学術的なソルバーの研究は特定のアプリケーションの文脈で行われる（例えばClarabel）ため、特定の問題クラスにより狭く焦点を当てる傾向がある。他の多くの分野は、大手テクノロジー企業が既存の商用プロジェクトを買収したり（例えばMujoco）、OSSプロジェクトに資金を提供して競合を下回る手段として進展している。このようなソルバーの狭い例もあるけど（例えばCeres）、全体的な汎用ソルバーのスタックをゼロから開発するための投資は高すぎると考えられているんじゃないかな。

└

彼らはクライアントと密に連携して、問題特有のスピードアップを実現するために非常に実践的に取り組んでいるんだ。これを10〜20年も続けている。MILPの世界では、良いヒューリスティクス（ブランチ＆バウンドの良いスタート地点を見つけたり、B&Bツリーを効果的に剪定するためのもの）や、カスタムカット（分数解を切り捨てて、目的関数や解の整合性を効果的に改善する方法）が重要なんだ。オペレーションズリサーチの研究者が問題を選ぶと、独自のカットやヒューリスティクスを書くことで、Gurobiや他のソルバーに簡単に勝てることが多い。ソルバー会社は、PhDや研究者のチームを雇って、一貫してこれを行い、クライアントの問題を追跡して改善を見守っている。

└

商業用ソルバーは、問題に役立ちそうなトリックを見つけるためのたくさんのテクニックと良いパターン検出メカニズムを持ってる。問題の構造を理解していれば、それを利用して商業用ソルバーの性能を超えることも可能なんだ。でも、ランダムな問題に対しては、全く勝ち目がないね。

こういう問題に「ML/AI」ベースのアプローチがあまり使われていない気がする。RLやGNNを使った小さな問題を解こうとする論文はたくさん見たけど、結局一番いいのはGurobiのライセンスを買ってしまうことだと思う。最近、スケジューリングの最適化（ジョブショップスケジューリングに近い）をやっていて、RLを使った例もあるけど、あまり効果的に感じない。大きな問題に対しては進化的アルゴリズムを使って、そこそこ良い解を得てる。問題をうまく定式化できるなら、OR系のアプローチを使う方が常に効率的なのかもしれないね。

└

SATは標準的なGOFAIの問題で、もちろんML系のプログラミング言語を使ってSATソルバーを書くこともできるよ。だから「ML/AI」アプローチは、むしろかなり適用可能だと思う！

└

問題によるね。セキュリティを含むユニットコミットメント問題（どの発電所をいつ稼働させるかを決める）は、MILPソルバーのGurobiがグローバル最適解をすぐに見つけられるほど、信じられないくらい複雑な問題なんだ。遺伝的アルゴリズムを作ることはできるけど、ローカルミニマにハマらない答えが得られる保証はないよ。それに、速く動かせるかどうかも問題だしね。ニューラルネットワークも最適解にはならないだろう。

実際にこれがどのように使われているか、誰か教えてくれない？なんとなく、数値最適化の実装は、データ駆動型アプローチの通常の問題（信頼性や悪いデータなど）で失敗することが多い気がするし、最終的には誰か重要な人が感覚でどうするか決めちゃうんじゃないかな。

└

うちは業務でソルバーをフル活用してるよ。家庭のバッテリーやEVの最適なスケジュールを組むためのソルバー、何十万件もの家庭をポートフォリオとして最適にスケジュールするためのソルバー、そのポートフォリオを最適に取引するためのソルバー。EUの電力スポット価格は、毎日一回の巨大なソルバー実行で決まるんだ。Euphemiaを調べてみて、どうやって機能するかの解説があるよ。明確な目標があって、実際にお金がかかる分野では、ソルバーがたくさん使われてる。

└

FMCG企業だけど、実際に使ってるのは以下の通り。1. 営業マンと配達の旅行計画 2. 生産のための機械、人、資材のリソーススケジューリング 3. 倉庫の流通センターの在庫レベル。この在庫レベルは完全自動じゃないけど、需要予測が難しいからね。

└

ケーススタディを読んでみて：Gurobiのケーススタディ：https://www.gurobi.com/case_studies/ CPLEXのケーススタディ：https://www.ibm.com/products/ilog-cplex-optimization-studio/... Hexaly（以前のlocalsolver）のケーススタディ：https://www.hexaly.com/customers

「1988年から2004年の間に、ハードウェアは1600倍速くなり、LPソルバーは3300倍速くなったおかげで、累積のスピードアップファクターは5 × 10^6を超えたんだ。それがもう20年前の話だって！」 「著者たちは、2001年から2020年の間に商業用MILPソルバーの間で1000倍のスピードアップを観察した（アルゴリズムによるものが50倍、より速いコンピュータによるものが20倍）。」 こういうスピードアップの要因を、アルゴリズムの改善と速いコンピュータの貢献に分けて、計算分野全体で集められたら面白いな。コンパイラの世界では「プロエブスティングの法則」があって、コンパイラの進化が18年ごとに計算能力を2倍にするんだよね。