分枝限定法における変数選択のためのマルコフ決定過程

この研究は、混合整数線形計画法（MILP）を用いた複雑な組合せ最適化問題に対して、分枝限定法（B&B）において変数選択のためのマルコフ決定過程（MDP）を提案しています。B&Bソルバーの性能を左右する要因として、ブランチング決定を管理する変数選択ヒューリスティックが重要です。本研究では、BBMDPというMDPモデルを導入し、最適なB&Bヒューリスティックを学習するために幅広い強化学習アルゴリズムを活用できます。計算実験の結果、このモデルは従来の最先端強化学習エージェントを上回る性能を示し、MILPの標準ベンチマークでの優れた結果を確認しました。