論文の概要: Effective Generation of Feasible Solutions for Integer Programming via Guided Diffusion
- arxiv url: http://arxiv.org/abs/2406.12349v1
- Date: Tue, 18 Jun 2024 07:33:05 GMT
- ステータス: 処理完了
- システム内更新日: 2024-06-19 20:16:07.431409
- Title: Effective Generation of Feasible Solutions for Integer Programming via Guided Diffusion
- Title（参考訳）: 誘導拡散による整数計画のための有効な解の効率的な生成
- Authors: Hao Zeng, Jiaqi Wang, Avirup Das, Junying He, Kunpeng Han, Haoyuan Hu, Mingfei Sun,
- Abstract要約: 実現可能なソリューションは、問題解決プロセスを大幅にスピードアップできるため、プログラミング(IP)にとって不可欠です。
完全実現可能なソリューションをエンド・ツー・エンドで生成する新しいフレームワークを提案する。
我々は,IP問題の典型的な4つのデータセット上で,我々の枠組みを実証的に評価し,高い確率で完全な実現可能な解を効果的に生成することを示す。
- 参考スコア（独自算出の注目度）: 27.35862371517583
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Feasible solutions are crucial for Integer Programming (IP) since they can substantially speed up the solving process. In many applications, similar IP instances often exhibit similar structures and shared solution distributions, which can be potentially modeled by deep learning methods. Unfortunately, existing deep-learning-based algorithms, such as Neural Diving and Predict-and-search framework, are limited to generating only partial feasible solutions, and they must rely on solvers like SCIP and Gurobi to complete the solutions for a given IP problem. In this paper, we propose a novel framework that generates complete feasible solutions end-to-end. Our framework leverages contrastive learning to characterize the relationship between IP instances and solutions, and learns latent embeddings for both IP instances and their solutions. Further, the framework employs diffusion models to learn the distribution of solution embeddings conditioned on IP representations, with a dedicated guided sampling strategy that accounts for both constraints and objectives. We empirically evaluate our framework on four typical datasets of IP problems, and show that it effectively generates complete feasible solutions with a high probability (> 89.7 \%) without the reliance of Solvers and the quality of solutions is comparable to the best heuristic solutions from Gurobi. Furthermore, by integrating our method's sampled partial solutions with the CompleteSol heuristic from SCIP, the resulting feasible solutions outperform those from state-of-the-art methods across all datasets, exhibiting a 3.7 to 33.7\% improvement in the gap to optimal values, and maintaining a feasible ratio of over 99.7\% for all datasets.
- Abstract（参考訳）: 実現可能なソリューションは、解決プロセスを著しくスピードアップできるため、整数プログラミング(IP)にとって不可欠です。
多くのアプリケーションにおいて、類似のIPインスタンスは、よく似た構造と共有されたソリューション分布を示すが、これはディープラーニングの手法によってモデル化される可能性がある。
残念ながら、Neural DivingやPredict-and-searchフレームワークのような既存のディープラーニングベースのアルゴリズムは、部分的な実現可能なソリューションのみを生成することに限定されており、与えられたIP問題に対するソリューションを完成させるためには、SCIPやGurobiのような問題解決者に頼る必要がある。
本稿では,完全な実現可能なソリューションをエンド・ツー・エンドで生成する新しいフレームワークを提案する。
本フレームワークは,IPインスタンスとソリューションの関係を特徴付けるために,コントラスト学習を活用し,IPインスタンスとソリューションの両方に対する遅延埋め込みを学習する。
さらに、このフレームワークは拡散モデルを用いて、IP表現に条件づけられたソリューション埋め込みの分布を学習し、制約と目的の両方を考慮に入れた専用のサンプリング戦略を提供する。
我々は,IP問題の4つの典型的なデータセット上で,我々の枠組みを実証的に評価し,解の質は解法に頼らずに高い確率で実現可能な解(>89.7 \%)を効果的に生成し,グロビの最良のヒューリスティック解に匹敵することを示した。
さらに、本手法のサンプル部分解をSCIPのCompleteSolヒューリスティックと統合することにより、結果として得られる実現可能な解は、すべてのデータセットで最先端のメソッドよりも優れ、最適値とのギャップが3.7～33.7\%改善され、すべてのデータセットに対して99.7\%以上の実現可能な比が維持される。
関連論文リスト
- DiffSG: A Generative Solver for Network Optimization with Diffusion Model [75.27274046562806]
拡散生成モデルはより広い範囲の解を考えることができ、学習パラメータによるより強力な一般化を示す。
拡散生成モデルの本質的な分布学習を利用して高品質な解を学習する新しいフレームワークを提案する。
論文 参考訳（メタデータ） (2024-08-13T07:56:21Z) - Online POMDP Planning with Anytime Deterministic Guarantees [11.157761902108692]
不確実性の下での計画は、部分的に観測可能なマルコフ決定プロセス(POMDP)を用いて数学的に定式化できる
POMDPの最適計画を見つけるには計算コストがかかり、小さなタスクにのみ適用可能である。
簡便な解と理論的に最適な解との決定論的関係を導出する。
論文 参考訳（メタデータ） (2023-10-03T04:40:38Z) - Let the Flows Tell: Solving Graph Combinatorial Optimization Problems
with GFlowNets [86.43523688236077]
組合せ最適化(CO)問題はしばしばNPハードであり、正確なアルゴリズムには及ばない。
GFlowNetsは、複合非正規化密度を逐次サンプリングする強力な機械として登場した。
本稿では,異なる問題に対してマルコフ決定プロセス(MDP)を設計し,条件付きGFlowNetを学習して解空間からサンプルを作成することを提案する。
論文 参考訳（メタデータ） (2023-05-26T15:13:09Z) - Optimization and Optimizers for Adversarial Robustness [10.279287131070157]
本稿では,汎用的制約最適化解法と制約Foldingを融合した新しいフレームワークを提案する。
信頼性に関して、PWCFは、ソリューションの品質を評価するための定常度測定と実現可能性テストのソリューションを提供する。
さらに、損失、摂動モデル、最適化アルゴリズムの様々な組み合わせを用いて、これらの問題を解決するための解の異なるパターンについて検討する。
論文 参考訳（メタデータ） (2023-03-23T16:22:59Z) - Solving Recurrent MIPs with Semi-supervised Graph Neural Networks [15.54959083707859]
本稿では,変数の値を予測することで,MIPの解を自動化・高速化するMLモデルを提案する。
私たちのアプローチは、多くの問題インスタンスが健全な特徴とソリューション構造を共有しているという観察によって動機付けられています。
例えば、輸送やルーティングの問題では、商品の量やリンクコストが変わるたびに、決定を再最適化する必要がある。
論文 参考訳（メタデータ） (2023-02-20T15:57:56Z) - Exploiting Temporal Structures of Cyclostationary Signals for
Data-Driven Single-Channel Source Separation [98.95383921866096]
単一チャネルソース分離(SCSS)の問題点について検討する。
我々は、様々なアプリケーション領域に特に適するサイクロ定常信号に焦点を当てる。
本稿では,最小MSE推定器と競合するU-Netアーキテクチャを用いたディープラーニング手法を提案する。
論文 参考訳（メタデータ） (2022-08-22T14:04:56Z) - Straggler-Resilient Personalized Federated Learning [55.54344312542944]
フェデレーション学習は、プライバシと通信の制限を尊重しながら、クライアントの大規模なネットワークに分散されたサンプルからのトレーニングモデルを可能にする。
これら2つのハードルを同時に処理する理論的なスピードアップを保証する新しいアルゴリズム手法を開発した。
提案手法は,すべてのクライアントのデータを用いてグローバルな共通表現を見つけ,各クライアントに対してパーソナライズされたソリューションにつながるパラメータの集合を学習するために,表現学習理論からのアイデアに依存している。
論文 参考訳（メタデータ） (2022-06-05T01:14:46Z) - Scalable Distributional Robustness in a Class of Non Convex Optimization
with Guarantees [7.541571634887807]
分散ロバスト最適化 (DRO) は, サンプルベース問題と同様に, 学習におけるロバスト性を示す。
実世界における課題を解くのに十分ではない混合整数クラスタリングプログラム (MISOCP) を提案する。
論文 参考訳（メタデータ） (2022-05-31T09:07:01Z) - Contrastive Losses and Solution Caching for Predict-and-Optimize [19.31153168397003]
ノイズコントラスト法を用いて、サロゲート損失関数の族を動機付ける。
すべての予測と最適化アプローチのボトルネックに対処する。
非常に遅い成長率でさえ、最先端の手法の質に合わせるのに十分であることを示す。
論文 参考訳（メタデータ） (2020-11-10T19:09:12Z) - Combining Deep Learning and Optimization for Security-Constrained
Optimal Power Flow [94.24763814458686]
セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。
SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。
本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
論文 参考訳（メタデータ） (2020-07-14T12:38:21Z) - Dynamic Federated Learning [57.14673504239551]
フェデレートラーニング(Federated Learning)は、マルチエージェント環境における集中的なコーディネーション戦略の包括的用語として登場した。
我々は、各イテレーションにおいて、利用可能なエージェントのランダムなサブセットがそのデータに基づいてローカル更新を実行する、フェデレートされた学習モデルを考える。
集約最適化問題に対する真の最小化器上の非定常ランダムウォークモデルの下で、アーキテクチャの性能は、各エージェントにおけるデータ変動率、各エージェントにおけるモデル変動率、アルゴリズムの学習率に逆比例する追跡項の3つの要因によって決定されることを示す。
論文 参考訳（メタデータ） (2020-02-20T15:00:54Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。