分枝のためのスパース学習による混合整数計画ソルバの高速化

arXiv cs.LG / 2026/4/2

💬 オピニオンSignals & Early TrendsIdeas & Deep AnalysisModels & Research

共有:

要点

本論文では、分枝限定（branch-and-bound）ソルバにおける強分枝（SB）スコアを近似する、解釈可能で軽量なMLモデルを構築するためにスパース学習を用いることを提案する。
得られたモデルは、最先端のグラフニューラルネットワーク（GNN）のパラメータの4%未満でありながら、分枝決定の予測において競争力のある精度を維持する。
報告された速度向上では、CPUのみのモデルがSCIPのデフォルトに組み込まれた分枝ルールよりも優れており、GPUで加速したGNNアプローチよりも高速であることが示されている。
著者らは、実運用における利点を強調している。すなわち、モデルは学習が簡単で、小規模な学習データセットでも有効であり、大規模なGPU並列化を必要としない低リソース環境にも適している。
分枝に対するスパース学習アプローチの効率性と頑健性を示すために、複数の問題クラスにわたる大規模な実験が行われている。

要旨: 機械学習は、混合整数計画法の分枝限定（branch-and-bound）アルゴリズム内での意思決定を改善するために、ますます広く使われています。既存の多くの手法は深層学習に依存しており、しばしば非常に大規模な学習データセットと、学習およびデプロイの双方において大きな計算資源を必要とし、典型的にはGPUの並列化を伴います。本研究では、単純だが効果的な解釈可能なモデルを開発することで、別の方針を取ります。我々は、有効性が高い一方で計算コストのかかる分枝規則である強分枝（Strong Branching: SB）スコアの近似に焦点を当てます。疎学習手法を用いて、最先端のグラフニューラルネットワーク（GNN）のパラメータ数の4%未満でモデルを構築し、競争力のある精度を達成します。SCIPに組み込まれた分枝規則およびGNNベースのモデルと比べて、我々のCPUのみのモデルは、既定のソルバおよびGPU加速されたGNNよりも高速です。これらのモデルは学習およびデプロイが容易で、小さな学習セットでも有効性を維持するため、低リソース環境で実用的です。多様な問題クラスにわたる大規模な実験により、本アプローチの効率性が示されます。