AIを活用したオペレーションリサーチで「描画機」を最適化！中国科学技術大学などは、数理計画法の解決効率を大幅に向上させる階層シーケンスモデルを提案した。

数理計画法ソルバーは、その重要性と多用途性により、オペレーションズ リサーチと最適化の分野では「リソグラフィー マシン」として知られています。

その中でも、混合整数線形計画法 (MILP) は数理計画法ソルバーの重要なコンポーネントであり、工業生産スケジューリング、物流スケジューリング、チップ設計、パスなどの多数の実用的なアプリケーションをモデル化できます。計画、金融投資、その他の主要分野。

最近、中国科学技術大学MIRA研究所のWang Jie教授のチームとファーウェイのノアの方舟研究所は共同で、混合整数の解法効率を大幅に向上させる階層シーケンスモデル(HEM)を提案しました。線形計画法ソルバーと関連結果は ICLR 2023 で発表されました。

現在、このアルゴリズムはファーウェイのMindSpore ModelZooモデルライブラリに統合されており、関連するテクノロジーと機能は今年中にファーウェイのOptVerse AIソルバーに統合される予定です。このソルバーは、オペレーションズ リサーチと AI を組み合わせて、業界のオペレーションズ リサーチ最適化の限界を突破し、企業の定量的な意思決定と洗練されたオペレーションを支援し、コスト削減と効率向上を実現することを目的としています。

著者リスト: Wang Zhihai*、Li Xijun*、Wang Jie**、Kuang Yufei、Yuan Mingxuan、Zeng Jia、Zhang Yongdong、Wu Feng

ペーパーリンク: https://openreview.net/forum?id=Zob4P9bRNcK

オープンソースデータセット: https://drive.google.com/drive/folders/1LXLZ8vq3L7v00XH- Tx3U6hiTJ79sCzxY?usp=sharing

PyTorch バージョンのオープン ソース コード: https://github.com/MIRALab-USTC/L2O-HEM-Torch

MindSpore バージョンのオープン ソース コード: https:// gitee.com/mindspore/models/tree/master/research/l2o/hem-learning-to-cut

Tianchiou (OptVerse) AI ソルバー: https://www.huaweicloud.com/product/modelarts/ optverse.html

図 1. HEM とソルバーのデフォルト戦略 (デフォルト) 間のソリューション効率の比較. HEM ソリューション効率は最大で改善できます。 47.28%

1 はじめに

切断面 (カット) は、混合整数線形計画問題を効率的に解くために重要です。

切断面の選択 (カット選択) は、MILP を解く効率を向上させるために選択される切断面の適切なサブセットを選択することを目的としています。切断面の選択は、(P1) どの切断面を優先するか、(P2) 選択する切断面の数という 2 つの副次的な問題に大きく依存します。

最新の MILP ソルバーの多くは、手動で設計されたヒューリスティックを通じて (P1) と (P2) を処理しますが、機械学習手法には、より効率的なヒューリスティックを学習できる可能性があります。

しかし、多くの既存の学習方法は、どの切断面を優先すべきかを学習することに焦点を当てており、いくつの切断面を選択すべきかを学習することは無視されています。さらに、多数の実験結果から、別の下位問題、つまりどの切断面順序を優先するかという (P3) も MILP を解く効率に大きな影響を与えることが観察されました。

これらの課題に対処するために、新しい階層シーケンス モデル (HEM) を提案し、強化学習フレームワークを通じて切断面の選択戦略を学習します。

私たちが知る限り、HEM は (P1)、(P2)、(P3) を同時に処理できる最初の学習方法です。実験の結果、HEM は、人工的に生成された大規模な実世界の MILP データセットに基づいて手動で設計および学習されたベースラインと比較して、MILP を解く効率が大幅に向上することが示されています。

2 背景と問題の紹介

2.1 切断面 (カット) の紹介

混合整数線形計画法 (MILP) は、さまざまな分野で広く使用されている一般的な最適化モデルです。サプライチェーン管理 [1]、生産計画 [2]、計画と発送 [3]、工場の場所の選択 [4]、梱包問題 [5] など、さまざまな実践的な応用分野。

標準 MILP の形式は次のとおりです。

(1)

問題を考慮すると、 ( 1) では、整数制約をすべて破棄し、次の形式の線形計画緩和 (LPR) 問題を取得します。

(2)

問題 (2) は問題 (1) の実行可能なセットを拡張するため、LPR 問題の最適値は元の MILP 問題の下限であることがわかります。

(2) の LPR 問題を考慮すると、切断面 (カット) は法的な線形不等式の一種であり、線形計画緩和問題に追加されると、LPR 問題の領域空間の実現可能性が縮小する可能性があります。元の MILP 問題の実行可能な整数解をすべて削除します。

2.2 カット選択の概要

MILP ソルバーは、MILP 問題を解くプロセス中に多数の切断面を生成することができ、連続ラウンドで元の問題に切断面を追加し続けます。

具体的には、各ラウンドには 5 つのステップが含まれます:

(1) 現在の LPR 問題を解決する;

(2) 選択される一連の切断面を生成する;

(3) 選択する切断面から適切なサブセットを選択します;

(4) 選択したサブセットを (1) の LPR 問題に追加して、新しい LPR 問題を取得します;

(5) このサイクルが繰り返され、新しい LPR 問題に基づいて次のラウンドに進みます。

生成されたすべての切断面を LPR 問題に追加すると、問題の実行可能領域スペースが可能な限り最大限に縮小され、下限が最大化されます。

ただし、切断面を追加しすぎると、問題に制約が多くなり、問題解決の計算オーバーヘッドが増加し、数値的不安定性の問題が発生する可能性があります[6、7]。

したがって、研究者らは、MILP 問題解決の効率を可能な限り向上させるために、候補切断面の適切なサブセットを選択することを目的とした切断面選択 (カット選択) を提案しました。切断面の選択は、混合整数線形計画問題を解く効率を向上させるために重要です [8、9、10]。

2.3 ヒューリスティック実験 - 切断面の追加順序

RandomAll と RandomNV という 2 つの切断面選択ヒューリスティック アルゴリズムを設計しました (詳細については、元の論文の第 3 章を参照)。

これらはすべて、カットのバッチを選択した後、選択したカットをランダムな順序で MILP 問題に追加します。図 2 の結果に示されているように、同じ切断面が選択されている場合、これらの選択された切断面を異なる順序で追加することは、ソルバーの解決効率に大きな影響を与えます (結果の詳細な分析については、元の論文の第 3 章を参照してください)。

図 2. 各列は、ソルバーで選択された切断面の同じバッチを表しており、これらは異なる順序で 10 ラウンドで追加されます。選択された切断面、ソルバーの最終的な解効率の平均値、列内の標準偏差線は、さまざまな次数での解効率の標準偏差を表します。標準偏差が大きいほど、ソルバーの解決効率に対する次数の影響が大きくなります。

3 手法の紹介

切断面選択タスクでは、選択すべき最適なサブセットを事前に取得することができません。

ただし、ソルバーを使用して選択したサブセットの品質を評価し、この評価を学習アルゴリズムへのフィードバックとして使用できます。

したがって、強化学習 (RL) パラダイムを使用して、試行錯誤を通じて切断面の選択戦略を学習します。

このセクションでは、私たちが提案する RL フレームワークについて詳しく説明します。

まず、切断面選択タスクをマルコフ決定プロセス (MDP) としてモデル化します。次に、提案する階層シーケンス モデル (HEM) を詳細に導入します。最後に、効率的にトレーニングできる階層型ポリシー勾配を導出します。裾。全体的な RL フレームワーク図を図 3 に示します。

図 3. 私たちが提案する全体的な RL フレームワークの図。 MILP ソルバーを環境としてモデル化し、HEM モデルをエージェントとしてモデル化します。エージェントと環境間の継続的な対話を通じてトレーニング データを収集し、階層的なポリシー勾配を使用して HEM モデルをトレーニングします。

3.1 問題モデリング

状態空間: 現在の LP 緩和と生成されたカット候補には切断面選択の中核情報が含まれているため、状態を定義します。ここでは、現在の LP 緩和の数学的モデルを表し、候補切断面のセットを表し、LP 緩和の最適解を表します。状態情報をエンコードするために、その情報に基づいて切断面候補ごとに 13 個の特徴を設計します。つまり、状態 s を 13 次元の特徴ベクトルで表現します。具体的な詳細については、元の記事の第 4 章を参照してください。

アクション空間: 選択したカットの割合と順序の両方を考慮するために、アクション空間を候補カットのセットの順序付けられたすべてのサブセットとして定義します。

報酬関数: MILP の解法に対するカットの追加の影響を評価するために、解時間、主双対ギャップ積分、および双対限界改善を使用できます。具体的な詳細については、元の記事の第 4 章を参照してください。

遷移関数: 伝達関数は、現在の状態と実行されたアクションに応じて次の状態を出力します。切断面選択タスクの伝達関数は、ソルバーによって暗黙的に提供されます。

モデリングの詳細については、元の記事の第 4 章を参照してください。

3.2 戦略モデル: 階層シーケンスモデル

図 3 に示すように、環境として MILP ソルバー、エージェントとして HEM をモデル化します。モデル。読みやすくするために、メソッドの動機を単純化し、メソッドの実装を明確に説明することに重点を置いています。興味のある読者は、関連する詳細について元の論文の第 4 章を参照してください。

図 3 のエージェント モジュールに示すように、HEM は上位ポリシー モデルと下位ポリシー モデルで構成されます。上位層モデルと下位層モデルはそれぞれ上位層ポリシー（ポリシー）と下位層ポリシーを学習します。

まず、上位レベルのポリシーは、適切な割合を予測することによって、選択されるべきカットの数を学習します。状態長が 、予測率が であると仮定すると、予測のために選択されるべきカットの数は

になります。ここで、 は切り捨て関数を表します。 を定義します。

2 番目に、下位レベルのポリシーは、指定されたサイズの順序付けされたサブセットを選択することを学習します。下位レベルのポリシーでは を定義できます。 は、状態 S と比率 K を考慮したアクション空間上の確率分布を表します。具体的には、基礎となるポリシーをシーケンスツーシーケンスモデル (シーケンスモデル) としてモデル化します。

最後に、カット選択戦略は全体確率の法則、つまり

3.3 トレーニング方法: 階層型戦略勾配

与えられた最適化目的関数

##図 4. 階層型ポリシー勾配。この確率的勾配降下法で HEM モデルを最適化します。

4 実験の紹介

私たちの実験には 5 つの主要な部分があります:

実験 1. 人工的に生成された 3 つの MILP 問題と 6 つの問題について 私たちの方法は、難しい MILP 問題で評価されます。基準。

実験 2. HEM についての深い洞察を得るために、慎重に設計されたアブレーション実験を実施します。

実験 3. 問題のサイズについて HEM の汎化パフォーマンスをテストします。

実験 4. 私たちの方法とベースラインによって選択された切断面の特性を視覚化します。

実験 5. ファーウェイの実際の生産スケジュール問題に私たちの手法を適用して、HEM の優位性を検証します。

この記事では実験 1 のみを紹介します。その他の実験結果については、元の論文の第 5 章を参照してください。私たちの論文で報告されているすべての実験結果は、PyTorch バージョン コードを使用したトレーニングに基づいて得られた結果であることに注意してください。

実験 1 の結果を表 1 に示します。HEM の結果と、9 つのオープンソース データセット上の 6 つのベースラインを比較しました。実験結果は、HEM が解決効率を平均して約 20% 向上させることができることを示しています。

図 5. イージー、ミディアム、ハードのデータセットに対する戦略の評価。最適なパフォーマンスは太字でマークされています。 m が制約の平均数を表し、n が変数の平均数を表すものとします。解時間と主双対ギャップ積分の算術平均 (標準偏差) を示します。

以上がAIを活用したオペレーションリサーチで「描画機」を最適化！中国科学技術大学などは、数理計画法の解決効率を大幅に向上させる階層シーケンスモデルを提案した。の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。