論文の概要: Towards An Unsupervised Learning Scheme for Efficiently Solving Parameterized Mixed-Integer Programs
- arxiv url: http://arxiv.org/abs/2412.17623v1
- Date: Mon, 23 Dec 2024 14:48:32 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-12-24 15:55:59.908332
- Title: Towards An Unsupervised Learning Scheme for Efficiently Solving Parameterized Mixed-Integer Programs
- Title(参考訳): パラメータ化混合整数プログラムの効率的な解法のための教師なし学習手法の提案
- Authors: Shiyuan Qu, Fenglian Dong, Zhiwei Wei, Chao Shang,
- Abstract要約: 教師なし学習方式でバイナリ変数の自動エンコーダを訓練する。
オフライン学習AEのデコーダパラメータから平面制約を切断するクラスを構築する戦略を提案する。
原始的なMIP問題への統合は、実現可能な領域を縮小したMIPの強化につながる。
- 参考スコア(独自算出の注目度): 6.1860817947800655
- License:
- Abstract: In this paper, we describe a novel unsupervised learning scheme for accelerating the solution of a family of mixed integer programming (MIP) problems. Distinct substantially from existing learning-to-optimize methods, our proposal seeks to train an autoencoder (AE) for binary variables in an unsupervised learning fashion, using data of optimal solutions to historical instances for a parametric family of MIPs.By a deliberate design of AE architecture and exploitation of its statistical implication, we present a simple and straightforward strategy to construct a class of cutting plane constraints from the decoder parameters of an offline-trained AE. These constraints reliably enclose the optimal binary solutions of new problem instances thanks to the representation strength of the AE. More importantly, their integration into the primal MIP problem leads to a tightened MIP with the reduced feasible region, which can be resolved at decision time using off-the-shelf solvers with much higher efficiency. Our method is applied to a benchmark batch process scheduling problem formulated as a mixed integer linear programming (MILP) problem. Comprehensive results demonstrate that our approach significantly reduces the computational cost of off-the-shelf MILP solvers while retaining a high solution quality. The codes of this work are open-sourced at https://github.com/qushiyuan/AE4BV.
- Abstract(参考訳): 本稿では,混合整数プログラミング (MIP) 問題の解を高速化する新しい教師なし学習手法について述べる。
提案手法は,既存の学習・最適化手法とは大きく異なるが,従来のMIPのパラメトリックなファミリに対する最適解のデータを用いて,教師なし学習方式でバイナリ変数の自動エンコーダ(AE)を訓練することを目的としており,AEアーキテクチャの意図的な設計と統計的意味の活用により,オフライン学習されたAEのデコーダパラメータから平面制約のクラスを構築するためのシンプルで簡単な戦略を提案する。
これらの制約は、AEの表現強度のおかげで、新しい問題インスタンスの最適二項解を確実に囲む。
さらに重要なことは、それらの原始的なMIP問題への統合により、実現可能な領域を縮小したMIPが強化され、より効率のよいオフ・ザ・シェルフ・ソルバを用いて決定時に解決できるということである。
本手法は,混合整数線形プログラミング(MILP)問題として定式化されたベンチマークバッチプロセススケジューリング問題に適用する。
総合的な結果から,本手法は解法の品質を維持しつつ,市販MILPソルバの計算コストを大幅に削減することを示した。
この作業のコードはhttps://github.com/qushiyuan/AE4BVで公開されている。
関連論文リスト
- Integrating Reinforcement Learning and Model Predictive Control with Applications to Microgrids [14.389086937116582]
本研究では,強化学習とモデル予測制御(MPC)を統合し,混合力学系における最適制御問題の解法を提案する。
提案手法は, MPC手法のオンライン計算時間を著しく短縮し, 最適性ギャップが小さく, 実現可能性が高いポリシーを生成する。
論文 参考訳(メタデータ) (2024-09-17T15:17:16Z) - An Unsupervised Learning Framework Combined with Heuristics for the Maximum Minimal Cut Problem [5.092968949752308]
本研究は,MMCPの最大値と非教師なし学習フレームワークを提案する。
重要な観察は、それぞれの溶液が少なくとも1本の枝木に対応することである。
フレームワークを評価し、特定のアプリケーションを提供するために、広範な実験を行います。
論文 参考訳(メタデータ) (2024-08-16T02:07:34Z) - Learning Constrained Optimization with Deep Augmented Lagrangian Methods [54.22290715244502]
機械学習(ML)モデルは、制約付き最適化ソルバをエミュレートするために訓練される。
本稿では,MLモデルを用いて2つの解推定を直接予測する手法を提案する。
これにより、双対目的が損失関数であるエンドツーエンドのトレーニングスキームと、双対上昇法をエミュレートした原始的実現可能性への解推定を可能にする。
論文 参考訳(メタデータ) (2024-03-06T04:43:22Z) - Machine Learning Insides OptVerse AI Solver: Design Principles and
Applications [74.67495900436728]
本稿では,Huawei CloudのOpsVerse AIソルバに機械学習(ML)技術を統合するための総合的研究について述べる。
本稿では,実世界の多面構造を反映した生成モデルを用いて,複雑なSATインスタンスとMILPインスタンスを生成する手法を紹介する。
本稿では,解解器性能を著しく向上させる,最先端パラメータチューニングアルゴリズムの導入について詳述する。
論文 参考訳(メタデータ) (2024-01-11T15:02:15Z) - A Multi-Head Ensemble Multi-Task Learning Approach for Dynamical
Computation Offloading [62.34538208323411]
共有バックボーンと複数の予測ヘッド(PH)を組み合わせたマルチヘッドマルチタスク学習(MEMTL)手法を提案する。
MEMTLは、追加のトレーニングデータを必要とせず、推測精度と平均平方誤差の両方でベンチマーク手法より優れている。
論文 参考訳(メタデータ) (2023-09-02T11:01:16Z) - Learning to Optimize Permutation Flow Shop Scheduling via Graph-based
Imitation Learning [70.65666982566655]
置換フローショップスケジューリング(PFSS)は製造業で広く使われている。
我々は,より安定かつ正確に収束を加速する専門家主導の模倣学習を通じてモデルを訓練することを提案する。
我々のモデルのネットワークパラメータはわずか37%に減少し、エキスパートソリューションに対する我々のモデルの解のギャップは平均6.8%から1.3%に減少する。
論文 参考訳(メタデータ) (2022-10-31T09:46:26Z) - Minimizing Entropy to Discover Good Solutions to Recurrent Mixed Integer
Programs [0.0]
混合整数プログラミング(MIP)問題に対する現在の解法は、幅広い問題に対して良好に動作するように設計されている。
近年の研究では、機械学習(ML)をMIPソルバと統合してドメイン知識を注入し、最適性ギャップを効率的に閉じることが示されている。
本稿では、エントロピーの概念を用いて、最小限のトレーニングデータとチューニングで効率的にモデルを構築するオンラインソルバを提案する。
論文 参考訳(メタデータ) (2022-02-07T18:52:56Z) - Learning to Schedule Heuristics in Branch-and-Bound [25.79025327341732]
現実世界のアプリケーションは通常、迅速な意思決定を可能にするために、検索の早い段階で優れたソリューションを見つける必要があります。
正確なMIPソルバにおけるスケジューリングのための最初のデータ駆動フレームワークを提案する。
最先端の学術MIPソルバーのデフォルト設定と比較して、挑戦的なインスタンスのクラスで平均プライマリ積分を最大49%削減することができます。
論文 参考訳(メタデータ) (2021-03-18T14:49:52Z) - Adaptive Sampling for Best Policy Identification in Markov Decision
Processes [79.4957965474334]
本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。
最先端アルゴリズムの利点を論じ、解説する。
論文 参考訳(メタデータ) (2020-09-28T15:22:24Z) - Combining Deep Learning and Optimization for Security-Constrained
Optimal Power Flow [94.24763814458686]
セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。
SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。
本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
論文 参考訳(メタデータ) (2020-07-14T12:38:21Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。