論文の概要: EquivaMap: Leveraging LLMs for Automatic Equivalence Checking of Optimization Formulations

• arxiv url: http://arxiv.org/abs/2502.14760v1
• Date: Thu, 20 Feb 2025 17:35:32 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-21 14:28:33.359278
• Title: EquivaMap: Leveraging LLMs for Automatic Equivalence Checking of Optimization Formulations
• Title（参考訳）: EquivaMap:最適化式の自動等価チェックのためのLCMの活用
• Authors: Haotian Zhai, Connor Lawless, Ellen Vitercik, Liu Leqi,
• Abstract要約: 2つの最適化定式化が等価であるかどうかを決定するための公式な基準である準カルプ同値を導入する。 本研究では,大規模な言語モデルを利用して,そのようなマッピングを自動的に検出するフレームワークであるEquivaMapを提案する。
• 参考スコア（独自算出の注目度）: 12.962019992859531
• License:
• Abstract: A fundamental problem in combinatorial optimization is identifying equivalent formulations, which can lead to more efficient solution strategies and deeper insights into a problem's computational complexity. The need to automatically identify equivalence between problem formulations has grown as optimization copilots--systems that generate problem formulations from natural language descriptions--have proliferated. However, existing approaches to checking formulation equivalence lack grounding, relying on simple heuristics which are insufficient for rigorous validation. Inspired by Karp reductions, in this work we introduce quasi-Karp equivalence, a formal criterion for determining when two optimization formulations are equivalent based on the existence of a mapping between their decision variables. We propose EquivaMap, a framework that leverages large language models to automatically discover such mappings, enabling scalable and reliable equivalence verification. To evaluate our approach, we construct the first open-source dataset of equivalent optimization formulations, generated by applying transformations such as adding slack variables or valid inequalities to existing formulations. Empirically, EquivaMap significantly outperforms existing methods, achieving substantial improvements in correctly identifying formulation equivalence.
• Abstract（参考訳）: 組合せ最適化における根本的な問題は、等価な定式化を特定することである。 問題定式化の同値性を自動的に識別する必要性は、自然言語記述から問題定式化を生成するシステムである最適化コピロとして増大している。 しかし、定式化同値性をチェックする既存のアプローチは、厳密な検証に不十分な単純なヒューリスティックに頼らず、根拠を欠いている。 カルプ還元にインスパイアされたこの研究では、準カルプ同値(英語版)(quasi-Karp equivalence)を導入し、2つの最適化定式化がそれらの決定変数間の写像の存在に基づいて等価であるかどうかを決定する公式な基準を導入する。 EquivaMapは、大規模言語モデルを利用して、そのようなマッピングを自動的に検出し、スケーラブルで信頼性の高い等価性検証を可能にするフレームワークである。 提案手法を評価するために,スラック変数の追加や既存の定式化に有効な不等式などの変換を適用した,等価な最適化定式化のための最初のオープンソースデータセットを構築した。 経験的に、EquivaMapは既存の手法を著しく上回り、定式化同値性を正しく識別する大幅な改善を実現している。

関連論文リスト

• Autoformulation of Mathematical Optimization Models Using LLMs [50.030647274271516]
  商用問題解決者のための自然言語記述から最適化モデルを作成するための自動アプローチを開発する。 本稿では,(1)問題依存仮説空間の定義,(2)不確実性の下でこの空間を効率的に探索すること,(3)定式化の正しさを評価すること,の3つの課題を同定する。
  論文  参考訳（メタデータ） (2024-11-03T20:41:38Z)
• LLaMA-Berry: Pairwise Optimization for O1-like Olympiad-Level Mathematical Reasoning [56.273799410256075]
  このフレームワークはMonte Carlo Tree Search (MCTS)と反復的なSelf-Refineを組み合わせて推論パスを最適化する。 このフレームワークは、一般的なベンチマークと高度なベンチマークでテストされており、探索効率と問題解決能力の点で優れた性能を示している。
  論文  参考訳（メタデータ） (2024-10-03T18:12:29Z)
• Regularized Projection Matrix Approximation with Applications to Community Detection [1.3761665705201904]
  本稿では,アフィニティ行列からクラスタ情報を復元するための正規化プロジェクション行列近似フレームワークを提案する。 3つの異なるペナルティ関数について検討し, それぞれが有界, 正, スパースシナリオに対応するように調整した。 合成および実世界の両方のデータセットで行った数値実験により、我々の正規化射影行列近似アプローチはクラスタリング性能において最先端の手法を著しく上回っていることが明らかとなった。
  論文  参考訳（メタデータ） (2024-05-26T15:18:22Z)
• An Inexact Halpern Iteration with Application to Distributionally Robust Optimization [9.529117276663431]
  決定論的および決定論的収束設定におけるスキームの不正確な変種について検討する。 不正確なスキームを適切に選択することにより、(予想される)剰余ノルムの点において$O(k-1)収束率を許容することを示す。
  論文  参考訳（メタデータ） (2024-02-08T20:12:47Z)
• Obtaining Explainable Classification Models using Distributionally Robust Optimization [12.511155426574563]
  特徴値規則の集合を用いて構築した一般化線形モデルについて検討する。 ルールセットの間隔と予測精度の間には、固有のトレードオフが存在する。 我々はこれらの競合する要因に同時に対処するルールセットの集合を学習するための新しい定式化を提案する。
  論文  参考訳（メタデータ） (2023-11-03T15:45:34Z)
• Backpropagation of Unrolled Solvers with Folded Optimization [55.04219793298687]
  ディープネットワークにおけるコンポーネントとしての制約付き最適化モデルの統合は、多くの専門的な学習タスクに有望な進歩をもたらした。 1つの典型的な戦略はアルゴリズムのアンローリングであり、これは反復解法の操作による自動微分に依存している。 本稿では,非ロール最適化の後方通過に関する理論的知見を提供し,効率よく解けるバックプロパゲーション解析モデルを生成するシステムに繋がる。
  論文  参考訳（メタデータ） (2023-01-28T01:50:42Z)
• HyperImpute: Generalized Iterative Imputation with Automatic Model Selection [77.86861638371926]
  カラムワイズモデルを適応的かつ自動的に構成するための一般化反復計算フレームワークを提案する。 既製の学習者,シミュレータ,インターフェースを備えた具体的な実装を提供する。
  論文  参考訳（メタデータ） (2022-06-15T19:10:35Z)
• Outlier-Robust Sparse Estimation via Non-Convex Optimization [73.18654719887205]
  空間的制約が存在する場合の高次元統計量と非破壊的最適化の関連について検討する。 これらの問題に対する新規で簡単な最適化法を開発した。 結論として、効率よくステーションに収束する一階法は、これらのタスクに対して効率的なアルゴリズムを導出する。
  論文  参考訳（メタデータ） (2021-09-23T17:38:24Z)
• Automatic selection of basis-adaptive sparse polynomial chaos expansions for engineering applications [0.0]
  スパースカオス展開のための3つの最新技術に基づく基礎適応的アプローチについて述べる。 我々は,大規模な計算モデルに対して,大域的近似精度の観点から広範なベンチマークを行う。 クロスバリデーションエラーによって導かれる新しい解法と基底適応性選択スキームを導入する。
  論文  参考訳（メタデータ） (2020-09-10T12:13:57Z)
• Robust, Accurate Stochastic Optimization for Variational Inference [68.83746081733464]
  また, 共通最適化手法は, 問題が適度に大きい場合, 変分近似の精度が低下することを示した。 これらの結果から,基礎となるアルゴリズムをマルコフ連鎖の生成とみなして,より堅牢で正確な最適化フレームワークを開発する。
  論文  参考訳（メタデータ） (2020-09-01T19:12:11Z)

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

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