DeepMind と Google がまた大きな動きを見せました!ニューラルネットワークを使用して NP 困難な MIP 問題を解く

[[414820]]

最近、DeepMind と Google Research チームが共同で、ニューラル ネットワークと機械学習手法を使用して混合整数計画法 (MIP) 問題を解決する研究を発表しました。

論文アドレス: https://arxiv.org/pdf/2012.13349.pdf

現実世界で遭遇する大規模な混合整数計画法 (MIP) インスタンスを解決する場合、MIP ソルバーは数十年にわたる研究を経て開発された一連の複雑なヒューリスティック アルゴリズムに依存しますが、機械学習はデータ内のインスタンス間の共有構造を使用して、データからより優れたヒューリスティック アルゴリズムを自動的に構築できます。

この研究では、MIP ソルバーの 2 つの主要なサブタスクに機械学習を適用し、高品質の共同変数割り当てを生成し、この変数割り当てと最適な割り当ての間の目標値のギャップを狭めました。彼らは、SCIP などの基本的な MIP ソルバーで使用できる、Neural Diving と Neural Branching という 2 つの対応するニューラル ネットワーク ベースのコンポーネントを構築しました。

その中で、Neural Diving はディープ ニューラル ネットワークを学習して整数変数に対して複数の部分割り当てを生成し、SCIP を使用して割り当てられていない変数の結果として得られるより小さな MIP を解決して、高品質の結合割り当てを取得します。 Neural Branching は、小さなツリーを使用して目標値のギャップを狭めるために、分岐と境界で変数選択の決定を行うディープ ニューラル ネットワークを学習します。これは、提案された Full Strong Branching の新しいバリアントをエミュレートすることによって実現されます。

著者チームは、評価のために複数の実際のデータセット（2 つの Google 製品データセットと MIPLIB を含む）でニューラル ネットワークをトレーニングしました。すべてのデータセットにわたって、事前解決後のほとんどのインスタンスには 10^3 ～ 10^6 個の変数と制約があり、これは以前の学習方法よりも大幅に大きいです。

大きな時間制約の下での主問題と二重問題のホールドアウトインスタンスのセットにおけるソルバーギャップの平均を比較すると、学習強化 SCIP は、MIP が最も大きい 3 つのデータセット (合計 5 つのデータセットのうち) で 1.5 倍、2 倍、104 倍優れたギャップを達成し、4 番目のデータセットでは 10% のギャップを 5 倍速く達成し、5 番目のデータセットでは SCIP と同等のパフォーマンスを発揮します。

研究チームによれば、彼らの知る限り、この方法は、大規模な実世界のアプリケーションデータセットと MIPLIB の両方で SCIP よりも大幅な改善を示した初の学習方法だという。

1. コンセプトの紹介

1.1 分岐限定法

MIP を解決するための一般的な手順は、検索ツリーを再帰的に構築し、各ノードに部分整数を割り当て、各ノードで収集された情報を使用して、最終的に最適な (または最適に近い) 割り当てに収束することです。各ステップで、「分岐」するリーフ ノードを選択する必要があります。このノードでは、線形計画法 (LP) 緩和問題を解決して、このノードの固定変数の範囲を指定された値に制限できます。これにより、そのノード内のすべての子の実際のターゲット値の有効な下限が得られます。

この境界が既知の実行可能な割り当てよりも大きい場合、そのノードのサブツリーには元の問題に対する最適な解決策が存在しないため、検索ツリーのこの部分を安全に剪定できます。このノードを拡張することにした場合、そのノードの未固定変数のセットから分岐する変数を選択する必要があります。変数が選択されると、分岐ステップが実行され、現在のノードに 2 つの子ノードが追加されます。ノードには、親ノードの LP 緩和値の上限以上になるように制約された選択された変数のドメインがあります。他のノードは、選択された変数のドメインを LP 緩和値の下限値以下に制限します。ツリーが更新され、プロセスが再び開始されます。

このアルゴリズムは分岐限定アルゴリズムと呼ばれます。このプロセスでは、各ノードでの二重境界を導出することと、より複雑な分岐ヒューリスティックの一部に対する分岐変数を決定することの両方で、線形計画法が作業の大部分を占めます。理論的には、探索ツリーのサイズは問題の入力サイズに応じて指数関数的に大きくなりますが、多くの場合、探索ツリーは非常に小さくなる可能性があり、ツリーを可能な限り小さく保つためのノード選択と変数選択のヒューリスティックを提案する研究が活発に行われています。

1.2 オリジナルのヒューリスティック

プリミティブ ヒューリスティックは、実行可能ではあるが必ずしも最適ではない変数への割り当てを見つけようとする方法です。このような実行可能な割り当ては、MIP の最適値の上限を保証します。 MIP ソリューション中の任意の時点で見つかったこのような境界は、「プリミティブ境界」と呼ばれます。

元のヒューリスティックは分岐限定法とは独立して実行できますが、分岐限定ツリーで実行して、検索ツリー内の特定のノードから固定されていない変数への実行可能な割り当てを見つけようとすることもできます。より低いプライマル境界を生成するより優れたプライマルヒューリスティックにより、分岐限定法のプロセス中により多くのツリーを剪定できるようになります。単純な丸めは、基本的なヒューリスティックの例です。もう 1 つの例はダイビングです。ダイビングでは、指定されたノードから深さ優先方式で検索ツリーを探索して、実行可能なソリューションを見つけようとします。

1.3 プライマル・デュアルギャップ

分岐限定法を実行する際、グローバル プライマル境界 (実行可能な割り当ての最小の目的値) とグローバル デュアル境界 (分岐限定法ツリーのすべてのリーフの最小のデュアル境界) を追跡します。これらを組み合わせて、最適でないギャップを定義できます。

• ギャップ = グローバルな主境界 - グローバルな二重境界

構築されたギャップは常に非負です。それがゼロであれば、問題は解決しており、主境界に対応する実行可能点は最適であり、双対境界は最適性の証明です。実際には、相対的なギャップ（つまり、何らかの方法で正規化されたもの）がアプリケーションに依存する数値を下回ると、分岐限定法を終了し、見つかった最良の主解をほぼ最適な解として生成します。

図のキャプション: ニューラル ネットワークへの入力として使用される MIP の二部グラフ表現。 n 個の変数のセット {x1,...,xn} と m 個の制約のセット {δ1,...,δm} は、二部グラフ内の 2 つのノード セットを形成します。係数はノードとエッジの特徴としてエンコードされます。

2. 論文紹介

混合整数計画法 (MIP) は、NP 困難問題の一種です。その目的は、一部またはすべての変数を整数値にしながら、線形制約の下で線形目的を最小化することです。これは、キャパシティ プランニング、リソース割り当て、ビン パッキングなどの実際のシナリオで広く使用されています。

この分野での多くの研究とエンジニアリングの取り組みは、SCIP、CPLEX、Gurobi、Xpress などの実用的なソルバーの開発に重点を置いてきました。これらのソルバーはすべて、複雑なヒューリスティック アルゴリズムを使用して、MIP を解決するための検索プロセスをガイドします。特定のアプリケーションにおけるソルバーのパフォーマンスは、主にソルバーのヒューリスティック アルゴリズムがアプリケーションにどれだけ適合しているかによって決まります。

この研究では、機械学習を使用して、MIP インスタンスのデータセットから効果的なヒューリスティック アルゴリズムを自動的に構築できることを実証しています。機械学習は、アプリケーションが異なる問題パラメータを持つ同じ高レベルのセマンティック問題の多数のインスタンスを解決する必要がある場合に役立ちます。

この研究におけるこのような「均質な」データセットの例には、1) 需要を満たすために電力網内の発電所の選択を最適化すること (O'Neill 2017) があり、電力網トポロジは一定である一方、需要、再生可能エネルギーの生成などはケースごとに変化します。2) Google のプロダクション システムにおけるパッキング問題を解決すること (パッキングされる「アイテム」と「ビン」のセマンティクスはほぼ一定ですが、そのサイズはケースごとに変化します)。

MIPLIB 2017 などの意味的に異なる多くの問題を組み合わせた「異種の」データセットであっても、より優れたヒューリスティックを学習するために使用できるインスタンス間の構造を持つことができます。既製の MIP ソルバーでは、この構造を活用するためのヒューリスティックを自動的に構築することはできません。困難なアプリケーション シナリオでは、ユーザーは専門家に頼ってこのようなヒューリスティックを手動で設計するか、パフォーマンスの大幅な向上を諦めることになります。機械学習は、アプリケーション固有の専門知識を必要とせずに大幅な改善を実現する可能性を秘めています。

この研究は、機械学習によって、最先端の非商用ソルバー SCIP 7.0.1 を含む MIP ソルバーで使用される従来の方法を大幅に上回る、特定のデータセットに合わせたヒューリスティック アルゴリズムを構築できることを実証しています。

彼らのアプローチは、MIP ソルバーの 2 つの主要なサブタスクに機械学習を適用します。a) 制約を満たすすべての変数への割り当てを出力する (そのような割り当てが存在する場合)。b) 変数の割り当てが最適なターゲット値にどれだけ近いかを証明する。これら 2 つのタスクによって、この方法の主なコンポーネントである Neural Diving と Neural Branching が決定されます (図 1 を参照)。

キャプション: 私たちのアプローチでは、MIP ソルバーで使用される 2 つのニューラル ネットワーク ベースのコンポーネント (Neural Diving と Neural Branching) を構築し、これら 2 つを組み合わせて、特定の MIP データセットに合わせて調整されたニューラル ソルバーを取得します。

ニューラル ダイビング: このコンポーネントは、高品質のジョイント変数の割り当てを見つけます。これは、効率的な MIP ソルバー (Berthold 2013) の鍵となる検索ヒューリスティックのクラスである基本ヒューリスティック (Berthold 2006) の例です。

著者らは、MIP に入力される整数変数の複数の部分割り当てを生成するためにディープ ニューラル ネットワークをトレーニングしました。残りの値のない変数は、割り当てを完了するために市販の MIP ソルバー (SCIP など) を使用して解決される、より小さな「サブ MIP」を定義します。計算予算が許せば、サブ MIP を並列に解くことができます。このモデルは、既製のソルバーによってオフラインで収集されたトレーニング例を使用してトレーニングされ、より適切なターゲット値による柔軟な割り当ての確率が高まります。モデルは、最適な割り当てではなく、利用可能なすべての実行可能な割り当てに基づいて学習され、最適な割り当てを使用する必要はありません (最適な割り当てを収集するコストが非常に高額になる可能性があるため)。

ニューラル分岐: このコンポーネントは、最適な割り当てと最適な割り当てのターゲット値との間のギャップを狭めるために主として使用されます。

整数変数の場合、MIP ソルバーは「分岐限定法」と呼ばれるツリー検索形式を使用します。これにより、境界が徐々に狭まり、実行可能な割り当てを見つけるのに役立ちます。特定のノードでは、分岐変数の選択が検索効率を決定する重要な要素となります。

彼らは、専門家のポリシーによる選択を模倣するために、ディープ ニューラル ネットワーク ポリシーをトレーニングしました。模倣の目標は、「Fully Strong Branching」(FSB) と呼ばれるよく知られたヒューリスティック アルゴリズムであり、小さな検索ツリーを生成することが示されています。実際の MIP 解決には計算コストが高すぎることが多いですが、模倣学習データのオフライン生成には、低速でコストのかかる 1 回限りの計算として使用できます。一度トレーニングすると、ニューラル ネットワークはテスト時にわずかな計算コストでプロフェッショナルなパフォーマンスに近づくことができます。オフライン データ生成の場合でも、CPU ベースの FSB 実装は大規模な MIP にはコストがかかりすぎる可能性があります。彼らは、必要な計算を GPU 上でバッチ方式で実行することで大規模な MIP に拡張できる、交互方向乗算法 (ADMM) を使用する FSB のバリアントを開発しました。

DeepMind と Google Research のチームは、Google の運用システムからの 2 つのデータセットと、異種データセットおよび標準ベンチマークである MIPLIB を含む、大規模な MIP を含む多数のデータセットでこの手法を評価しました。

すべてのデータセットからの MIP 組み合わせのほとんどのセットには、事前解決後に 10^3-10^6 の変数と制約があり、これは以前の研究 (Gasse et al. 2019、Ding et al. 2020) よりも大幅に大きくなっています。 Neural Diving モデルと Neural Branching モデルが特定のデータセットでトレーニングされると、それらは SCIP に統合され、そのデータセット専用の「Neural Solver」が形成されます。 SCIP はベースラインであり、主要なパラメータは各データセットのグリッド検索を通じて個別に調整され、これを「調整された SCIP」と呼びます。

ホールドアウト インスタンス セット (図 2 を参照) でのニューラル ソルバーと調整済み SCIP のプライマリ問題とデュアル問題の平均ギャップを比較すると、評価した MIP が最も大きい 4 つのデータセット (合計 5 つのデータセット) で、ニューラル ソルバーは同じ実行時間で大幅に優れたギャップを提供するか、より短い時間で同じギャップを提供し、5 番目のデータセットでは調整済み SCIP のパフォーマンスと一致しました。彼らは、自分たちの知る限り、大規模な実世界のアプリケーション データセットと MIPLIB で SCIP を大幅に改善するために機械学習を使用したのはこれが初めてであると紹介しました。

図 2: 論文の主な結果: 彼らの方法 (Neural Branching + Neural Divin) は、主問題と双対問題の間のギャップにおいて SCIP と同等かそれ以上であり、保持されたインスタンスの点でも同等です。

学習ヒューリスティック アルゴリズムを統合するための基本ソルバーとして SCIP を使用しているため、調整された SCIP が比較の基準となります。

SCIP は基本ソルバーとして、a) アンサンブル学習モデルの内部状態への詳細なアクセス、および b) 大規模な評価のために多数のソルバーインスタンスを並列に実行する権限を提供します。

著者らは、これらの機能を備えた市販のソルバーは使用できなかったため、事実上使用できないと述べています。彼らは、サブ MIP ソルバーとして Gurobi を使用した 2 つのデータセットで、Gurobi と Neural Diving を部分的に比較しました。一連の保留インスタンスの生のギャップの平均を比較すると、並列サブ MIP 解決を備えた Neural Diving は、両方のデータセットで Gurobi よりも 3 倍と 3.6 倍短い時間で平均生のマージンの 1% に到達します。

また、研究者らは、Neural Diving の修正版を MIPLIB の「オープン」インスタンスのサブセットに適用し、商用ソルバーを上回る 3 つの新しい最もよく知られたタスクを発見しました。初期の研究のいくつかは、基本的なヒューリスティックの学習に焦点を当てていました。それらとは異なり、Neural Diving は予測変数の割り当ての問題を生成モデリングの問題として定式化し、利用可能なすべての実行可能な割り当てを学習し、テスト時に部分的な真理値を生成するための原理的なアプローチを提供します。

いくつかの研究では、分岐戦略の学習にも焦点が当てられています。彼らの多くは、DeepMind チームのように、FSB を模倣する方法を学習することに重点を置いています。これらとは異なり、Neural Branching は GPU を使用してターゲット ポリシーを計算するために、よりスケーラブルなアプローチを使用します。これにより、CPU ベースの FSB 実装と比較して、同じ時間制限内でより大きなインスタンスからより多くの模倣データを生成できます。この研究は、学習した元のヒューリスティックとソルバーで学習した分岐戦略を組み合わせることで、個々のヒューリスティックを学習することに関する以前の独立した研究を超え、大規模な実世界のアプリケーション データセットと MIPLIB で大幅に優れたパフォーマンスを実現しました。

3. 論文の貢献

この研究の主な貢献は次のとおりです。

• ニューラルダイビングが提案されました。これは、MIP の高品質な結合変数割り当てを生成できる新しい学習ベースのアプローチです。同様のデータセットでは、Neural Diving は、保持されたインスタンスで平均 1% のオリジナル ギャップを達成し、Tuned SCIP よりも 3 ～ 10 倍高速です。あるデータセットでは、Tuned SCIP は制限時間内に 1% の平均オリジナル差異を達成できませんでしたが、Neural Diving は達成できました。
• Neural Branching は、ADMM に基づく新しいスケーラブルなエキスパート戦略を模倣することにより、分岐限定アルゴリズムで使用される分岐戦略を学習するために提案されています。評価に使用した 2 つのデータセットでは、インスタンス サイズ (例: 105 を超える変数) または反復時間が長いために FSB は遅く、ADMM Expert は同じ実行時間で 1.4 倍と 12 倍のトレーニング データを生成します。学習した戦略は、4 つのデータセットで SCIP の分岐ヒューリスティックを大幅に上回り、大きな時間制約の下でのホールドアウト インスタンスの平均双対性ギャップを 2 ～ 20 倍改善し、他のデータセットでも同等のパフォーマンスを実現します。
• Neural Diving と Neural Branching を組み合わせると、MIP が最大の 4 つのデータセット (5 つのデータセットのうち) の平均プライマル デュアル ギャップに関して SCIP よりも大幅に優れたパフォーマンスが実現され、5 番目のデータセットでは SCIP と同等のパフォーマンスが実現されます。

さらに、彼らはニューラル ネットワーク検証用のデータセット (セクション 4 および 12.6) をオープンソース化し、MIP の新しい学習手法に関するさらなる研究を促進することを期待しています。

4. 結論

この研究は、大規模な実世界のアプリケーション データセットと MIPLIB における MIP ソルバーのパフォーマンスを大幅に向上させる機械学習の長期的な可能性を示しています。モデルとアルゴリズムのさらなる改善により、この方法はさらに改善されると考えています。

将来的に有望な研究の方向性としては、以下のものが挙げられます。

• カットの学習: 機械学習を使用してカットをより適切に選択および生成することは、パフォーマンスを向上させるためのもう 1 つの潜在的な手法です。
• ウォーム スタート モデル: MIPLIB で学習したモデルのパフォーマンスが優れていることから、さまざまな MIP で適切に機能するヒューリスティックを学習できることがわかります。これは、アプリケーションの初期段階で利用できるトレーニング データの量が少なすぎて適切なモデルをトレーニングできない可能性があるアプリケーション シナリオでの「コールド スタート」問題を克服するために使用できます。まず、異種のデータセットでトレーニングされたモデルを使用して、アプリケーション用にさらにデータを収集するにつれて、それらをより特化したモデルへの橋渡しとして使用することができます。
• 強化学習: 蒸留または動作のクローン作成を使用して達成されるパフォーマンスは、既存の専門家の最高のパフォーマンスですが、強化学習 (RL) はそれを上回る可能性があります。効率的な探索、長期的なクレジットの割り当て、学習の計算スケーラビリティは、RL を大規模 MIP に適用する際の重要な課題です。これらの問題を修正すると、パフォーマンスがさらに向上する可能性があります。

この記事はLeiphone.comから転載したものです。転載する場合は、Leiphone.com公式サイトにアクセスして許可を申請してください。