Fugu-MT 論文翻訳(概要): Threshold-aware Learning to Generate Feasible Solutions for Mixed Integer Programs

論文の概要: Threshold-aware Learning to Generate Feasible Solutions for Mixed Integer Programs

arxiv url: http://arxiv.org/abs/2308.00327v1
Date: Tue, 1 Aug 2023 07:03:16 GMT
ステータス: 処理完了
システム内更新日: 2023-08-02 15:13:21.878963
Title: Threshold-aware Learning to Generate Feasible Solutions for Mixed Integer Programs
Title（参考訳）: 混合整数プログラムに有効な解を生成するための閾値認識学習
Authors: Taehyun Yoon, Jinwon Choi, Hyokun Yun, Sungbin Lim
Abstract要約: ニューラルダイビング(ND)は、混合プログラム(MIP)における部分的な離散変数代入を生成する学習ベースのアプローチの1つである。カバー範囲を最適化するためのポストホック法と学習に基づくアプローチを導入する。実験結果から、ニューラルネットワークを学習して高品質な実現可能なソリューションを見つけるためのカバレッジを推定することで、NeurIPS ML4COデータセットの最先端のパフォーマンスが達成されることが示された。
参考スコア（独自算出の注目度）: 5.28005598366543
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: Finding a high-quality feasible solution to a combinatorial optimization (CO) problem in a limited time is challenging due to its discrete nature. Recently, there has been an increasing number of machine learning (ML) methods for addressing CO problems. Neural diving (ND) is one of the learning-based approaches to generating partial discrete variable assignments in Mixed Integer Programs (MIP), a framework for modeling CO problems. However, a major drawback of ND is a large discrepancy between the ML and MIP objectives, i.e., variable value classification accuracy over primal bound. Our study investigates that a specific range of variable assignment rates (coverage) yields high-quality feasible solutions, where we suggest optimizing the coverage bridges the gap between the learning and MIP objectives. Consequently, we introduce a post-hoc method and a learning-based approach for optimizing the coverage. A key idea of our approach is to jointly learn to restrict the coverage search space and to predict the coverage in the learned search space. Experimental results demonstrate that learning a deep neural network to estimate the coverage for finding high-quality feasible solutions achieves state-of-the-art performance in NeurIPS ML4CO datasets. In particular, our method shows outstanding performance in the workload apportionment dataset, achieving the optimality gap of 0.45%, a ten-fold improvement over SCIP within the one-minute time limit.
Abstract（参考訳）: 組合せ最適化(CO)問題に対する高品質な実現可能な解を限られた時間で見つけることは、その離散的性質のため困難である。近年,co問題に対処するための機械学習(ml)手法が増えている。 neural dive (nd) は co 問題をモデル化するためのフレームワークである mixed integer programs (mip) において偏離散変数割当を生成するための学習ベースのアプローチの1つである。しかし、ndの大きな欠点はmlとmipの目的、すなわちプライマルバウンドに対する変数値の分類精度の差が大きいことである。本研究は,特定範囲の可変割当率(カバレッジ)が高品質な実現可能な解をもたらすことを考察し,学習目標とMIP目標のギャップを埋めることを提案する。そこで,本稿では,ポストホック法と学習に基づくカバレッジ最適化手法を提案する。提案手法の鍵となる考え方は,検索空間の制限を共同で学習し,学習した検索空間のカバレッジを予測することである。実験結果から、ニューラルネットワークを学習して高品質な実現可能なソリューションを見つけるためのカバレッジを推定することで、NeurIPS ML4COデータセットの最先端のパフォーマンスが達成されることが示された。特に,本手法は作業負荷調整データセットの性能に優れており,その最適性ギャップは0.45%であり,SCIPよりも10倍改善されている。

関連論文リスト

Learning to Optimize for Mixed-Integer Non-linear Programming [20.469394148261838]
混合整数非NLPプログラム(MINLP)はエネルギーシステムや輸送など様々な領域で発生するが、解決は困難である。機械学習の最近の進歩は、最適化のための学習として知られる領域において、顕著な成功をもたらしている。勾配を保ちながら整数出力を生成する2つの異なる補正層を提案する。
論文参考訳（メタデータ） (2024-10-14T20:14:39Z)
Machine Learning and Constraint Programming for Efficient Healthcare Scheduling [0.8287206589886879]
看護スケジューリング問題(NSP)に取り組む暗黙の問題解決アプローチでは、学習パターンに埋め込まれる可能性のある制約や目的を通じて、過去のデータを使って新しいソリューションを学習し、生成する機械学習手法を頼りにしています。提案手法では, 制約や目的が具体的に見えるものではないことを考慮し, 暗黙的アプローチに関する不確実性を補うために, 制約満足度問題フレームワークを用いてまずNSPをモデル化する明示的アプローチを提案する。我々の暗黙的アプローチは生成したソリューションの実現可能性や最適性を保証するものではないため、データ駆動型アプローチを提案し、NSPを制約として受動的に学習する。
論文参考訳（メタデータ） (2024-09-11T18:09:25Z)
Optimization by Parallel Quasi-Quantum Annealing with Gradient-Based Sampling [0.0]
本研究では、連続緩和による勾配に基づく更新と準量子アナリング(QQA)を組み合わせた別のアプローチを提案する。数値実験により,本手法はiSCOと学習型解法に匹敵する性能を有する汎用解法であることが示された。
論文参考訳（メタデータ） (2024-09-02T12:55:27Z)
BalMCTS: Balancing Objective Function and Search Nodes in MCTS for Constraint Optimization Problems [7.196057722218442]
制約問題最適化(COP)は、通常ブランチ・アンド・バウンド(B&B)法によって解決される問題において、複雑な課題を提起する。 COPを解くための深度優先探索アルゴリズムに基づく新しいニューラルネットワークアルゴリズムを提案する。提案手法は,最初の5つの実現可能な解のうち17.63%未満のギャップを有する実現可能な解を同定する。
論文参考訳（メタデータ） (2023-12-26T03:09:08Z)
Mixture Weight Estimation and Model Prediction in Multi-source Multi-target Domain Adaptation [22.933419188759707]
複数の異種源からモデルを学習する問題を考察する。学習者の目標は、これらのデータソースを目標分布を意識した方法で混ぜることである。
論文参考訳（メタデータ） (2023-09-19T16:29:34Z)
A Multi-Head Ensemble Multi-Task Learning Approach for Dynamical Computation Offloading [62.34538208323411]
共有バックボーンと複数の予測ヘッド(PH)を組み合わせたマルチヘッドマルチタスク学習(MEMTL)手法を提案する。 MEMTLは、追加のトレーニングデータを必要とせず、推測精度と平均平方誤差の両方でベンチマーク手法より優れている。
論文参考訳（メタデータ） (2023-09-02T11:01:16Z)
Federated Compositional Deep AUC Maximization [58.25078060952361]
本研究では,曲線(AUC)のスコアを直接最適化することにより,不均衡なデータに対する新しいフェデレート学習法を開発した。私たちの知る限りでは、このような好ましい理論的な結果を達成した最初の作品である。
論文参考訳（メタデータ） (2023-04-20T05:49:41Z)
DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimization [51.517956081644186]
グラフベースの拡散フレームワークであるDIFUSCOを導入する。本フレームワークは, NPC問題を離散0, 1ベクトル最適化問題とみなす。 MIS問題に対して、DIFUSCOは、挑戦的なSATLIBベンチマークにおいて、以前の最先端のニューラルソルバよりも優れている。
論文参考訳（メタデータ） (2023-02-16T11:13:36Z)
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)
Self-Directed Online Machine Learning for Topology Optimization [58.920693413667216]
自己指向型オンライン学習最適化は、ディープニューラルネットワーク(DNN)と有限要素法(FEM)計算を統合している。本アルゴリズムは, コンプライアンスの最小化, 流体構造最適化, 伝熱促進, トラス最適化の4種類の問題によって検証された。その結果, 直接使用法と比較して計算時間を2～5桁削減し, 実験で検証した全ての最先端アルゴリズムより優れていた。
論文参考訳（メタデータ） (2020-02-04T20:00:28Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。