論文の概要: The Differentiable Feasibility Pump

• arxiv url: http://arxiv.org/abs/2411.03535v1
• Date: Tue, 05 Nov 2024 22:26:51 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-07 19:22:24.018604
• Title: The Differentiable Feasibility Pump
• Title（参考訳）: 差別化可能なフェーザビリティポンプ
• Authors: Matteo Cacciola, Alexandre Forel, Antonio Frangioni, Andrea Lodi,
• Abstract要約: 本稿では,従来の実現可能性ポンプとその追随点の多くを,特定のパラメータを持つ勾配差アルゴリズムとみなすことができることを示す。 この再解釈の中心的な側面は、伝統的なアルゴリズムがそのコストに関して線形緩和の解を区別することを観察することである。
• 参考スコア（独自算出の注目度）: 49.55771920271201
• License:
• Abstract: Although nearly 20 years have passed since its conception, the feasibility pump algorithm remains a widely used heuristic to find feasible primal solutions to mixed-integer linear problems. Many extensions of the initial algorithm have been proposed. Yet, its core algorithm remains centered around two key steps: solving the linear relaxation of the original problem to obtain a solution that respects the constraints, and rounding it to obtain an integer solution. This paper shows that the traditional feasibility pump and many of its follow-ups can be seen as gradient-descent algorithms with specific parameters. A central aspect of this reinterpretation is observing that the traditional algorithm differentiates the solution of the linear relaxation with respect to its cost. This reinterpretation opens many opportunities for improving the performance of the original algorithm. We study how to modify the gradient-update step as well as extending its loss function. We perform extensive experiments on MIPLIB instances and show that these modifications can substantially reduce the number of iterations needed to find a solution.
• Abstract（参考訳）: 提案から20年近くが経過したが、この実現可能性ポンプアルゴリズムは、混合整数線形問題に対する実現可能な原始解を見つけるために広く使われているヒューリスティックである。 初期アルゴリズムの多くの拡張が提案されている。 しかし、その中心となるアルゴリズムは、制約を尊重する解を得るために元の問題の線形緩和を解くことと、整数解を得るためにそれを丸めることである。 本稿では,従来の実現可能性ポンプとその追随点の多くを,特定のパラメータを持つ勾配差アルゴリズムとみなすことができることを示す。 この再解釈の中心的な側面は、伝統的なアルゴリズムがそのコストに関して線形緩和の解を区別することを観察することである。 この再解釈は、元のアルゴリズムの性能を改善する多くの機会を開放する。 我々は、勾配更新ステップの修正と損失関数の延長について研究する。 我々はMIPLIBインスタンス上で広範囲な実験を行い、これらの修正が解を見つけるのに必要な反復回数を大幅に削減できることを示した。

関連論文リスト

• Analysis of the Non-variational Quantum Walk-based Optimisation Algorithm [0.0]
  本稿では,多種多様な最適化問題を解くために設計された非変分量子アルゴリズムを詳細に紹介する。 このアルゴリズムは、増幅状態の繰り返しの準備と測定から最適解とほぼ最適解を返す。
  論文  参考訳（メタデータ） (2024-07-29T13:54:28Z)
• Discretize Relaxed Solution of Spectral Clustering via a Non-Heuristic Algorithm [77.53604156112144]
  我々は、元の問題と離散化アルゴリズムを橋渡しする1次項を開発する。 非ヒューリスティック法は元のグラフ切断問題を認識しているため、最終的な離散解の方が信頼性が高い。
  論文  参考訳（メタデータ） (2023-10-19T13:57:38Z)
• Beyond the Golden Ratio for Variational Inequality Algorithms [12.470097382737933]
  我々は,モノトーン変分不等式 (VI) と凸凹 min-max 問題の解法である $textitgolden ratio algorithm$ の理解を改善した。 我々は,黄金比アルゴリズムと文献における既存のアルゴリズムとの橋渡しを完了するために,より大きなステップサイズを使用することのできる新しい分析手法を提案する。
  論文  参考訳（メタデータ） (2022-12-28T16:58:48Z)
• A Single-Loop Gradient Descent and Perturbed Ascent Algorithm for Nonconvex Functional Constrained Optimization [27.07082875330508]
  制約のない不等式問題は、マルチクラスネイマンオラクルのような多くの機械学習問題をモデル化するために用いられる。 このような緩やかな規則性の条件下では、値損失の交互化と制約違反の低減のバランスをとることは困難である。 本稿では,新しい不等式制約問題アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-07-12T16:30:34Z)
• A framework for bilevel optimization that enables stochastic and global variance reduction algorithms [17.12280360174073]
  双レベル最適化は、他の関数のarg最小値を含む値関数を最小化する問題である。 本稿では, 内部問題の解, 線形系の解, 主変数を同時に発展させる新しい枠組みを提案する。 我々のフレームワークにおけるSAGAアルゴリズムの適応であるSABAは$O(frac1T)$収束率を持ち、Polyak-Lojasciewicz仮定の下で線形収束を達成することを示した。
  論文  参考訳（メタデータ） (2022-01-31T18:17:25Z)
• Quadratic Unconstrained Binary Optimisation via Quantum-Inspired Annealing [58.720142291102135]
  本稿では,2次非制約二項最適化の事例に対する近似解を求める古典的アルゴリズムを提案する。 我々は、チューニング可能な硬さと植え付けソリューションを備えた大規模問題インスタンスに対して、我々のアプローチをベンチマークする。
  論文  参考訳（メタデータ） (2021-08-18T09:26:17Z)
• A Hybrid Quantum-Classical Heuristic to solve large-scale Integer Linear Programs [0.4925222726301578]
  本稿では、整数線形プログラムの解を見つけることができる任意の量子アルゴリズムをブランチ・アンド・プライス・アルゴリズムに統合する手法を提案する。 量子アルゴリズムの役割は、ブランチ・アンド・プライスに現れるサブプロブレムに対する整数解を見つけることである。
  論文  参考訳（メタデータ） (2021-03-29T08:59:26Z)
• Boosting Data Reduction for the Maximum Weight Independent Set Problem Using Increasing Transformations [59.84561168501493]
  最大重み独立集合問題に対する新しい一般化データ削減および変換規則を導入する。 驚くべきことに、これらのいわゆる増進変換は問題を単純化し、還元空間を開き、アルゴリズムの後にさらに小さな既約グラフが得られる。 提案アルゴリズムは, 1つのインスタンスを除くすべての既約グラフを計算し, 従来よりも多くのインスタンスを最適に解き, 最高の最先端解法よりも最大2桁高速に解き, 解法DynWVCやHILSよりも高品質な解を求める。
  論文  参考訳（メタデータ） (2020-08-12T08:52:50Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。 SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。 本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
  論文  参考訳（メタデータ） (2020-07-14T12:38:21Z)
• Conditional gradient methods for stochastically constrained convex minimization [54.53786593679331]
  構造凸最適化問題に対する条件勾配に基づく2つの新しい解法を提案する。 私たちのフレームワークの最も重要な特徴は、各イテレーションで制約のサブセットだけが処理されることです。 提案アルゴリズムは, 条件勾配のステップとともに, 分散の低減と平滑化に頼り, 厳密な収束保証を伴っている。
  論文  参考訳（メタデータ） (2020-07-07T21:26:35Z)

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

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