論文の概要: Local Search for Integer Quadratic Programming

• arxiv url: http://arxiv.org/abs/2409.19668v1
• Date: Sun, 29 Sep 2024 11:45:44 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-10-01 22:04:42.096617
• Title: Local Search for Integer Quadratic Programming
• Title（参考訳）: 整数二次計画法の局所探索
• Authors: Xiang He, Peng Lin, Shaowei Cai,
• Abstract要約: 本稿では,汎用二次計画法(IQP)のための効率的な局所探索解法を開発する。 目的関数,制約,あるいはその両方で2次項を扱えるIQP用の新しい局所探索演算子を4つ提案する。 2モードの局所探索アルゴリズムを導入し、新たに設計されたスコアリング機能を利用して探索プロセスを強化する。
• 参考スコア（独自算出の注目度）: 15.937160807265439
• License:
• Abstract: Integer Quadratic Programming (IQP) is an important problem in operations research. Local search is a powerful method for solving hard problems, but the research on local search algorithms for IQP solving is still on its early stage. This paper develops an efficient local search solver for solving general IQP, called LS-IQCQP. We propose four new local search operators for IQP that can handle quadratic terms in the objective function, constraints or both. Furthermore, a two-mode local search algorithm is introduced, utilizing newly designed scoring functions to enhance the search process. Experiments are conducted on standard IQP benchmarks QPLIB and MINLPLIB, comparing LS-IQCQP with several state-of-the-art IQP solvers. Experimental results demonstrate that LS-IQCQP is competitive with the most powerful commercial solver Gurobi and outperforms other state-of-the-art solvers. Moreover, LS-IQCQP has established 6 new records for QPLIB and MINLPLIB open instances.
• Abstract（参考訳）: Integer Quadratic Programming (IQP) はオペレーション研究において重要な問題である。 局所探索は難しい問題を解くための強力な手法であるが、IQP解決のための局所探索アルゴリズムの研究はまだ初期段階にある。 本稿では、LS-IQCQPと呼ばれる一般IQPを解くための効率的な局所探索解法を開発する。 目的関数,制約,あるいはその両方で2次項を扱えるIQP用の新しい局所探索演算子を4つ提案する。 さらに、2モードの局所探索アルゴリズムを導入し、新たに設計されたスコアリング機能を利用して探索プロセスを強化する。 標準IQPベンチマークQPLIBとMINLPLIBで実験を行い、LS-IQCQPと最先端IQPソルバを比較した。 実験の結果、LS-IQCQPは最も強力な商用解法であるグロビと競合し、他の最先端解法よりも優れていることが示された。 さらに、LS-IQCQPはQPLIBとMINLPLIBのオープンインスタンスに6つの新しいレコードを樹立した。

関連論文リスト

• Benchmarking Uncertainty Quantification Methods for Large Language Models with LM-Polygraph [85.51252685938564]
  不確実性定量化(UQ)は、機械学習(ML)に依存するアプリケーションの重要なコンポーネントとして、ますます認識されつつある。 他のMLモデルと同様に、大きな言語モデル(LLM)は、クレームを作成することによって誤った予測をする傾向があり、あるいは与えられた入力に対して単に低品質の出力を生成する。 本稿では,最先端のUQベースラインの集合を実装した新しいベンチマークを提案し,新しいテクニックを制御可能かつ一貫した評価を行う環境を提供する。
  論文  参考訳（メタデータ） (2024-06-21T20:06:31Z)
• Learning Solution-Aware Transformers for Efficiently Solving Quadratic Assignment Problem [27.33966993065248]
  本研究は,2次割当て問題(QAP)を効率的に解くための学習ベースソリューションに焦点を当てる。 QAPに関する現在の研究は、限られた規模と非効率性に悩まされている。 そこで本研究では,QAPの学習と改善のカテゴリにおける第1の解法を提案する。
  論文  参考訳（メタデータ） (2024-06-14T10:15:03Z)
• Multi-Timescale Ensemble Q-learning for Markov Decision Process Policy Optimization [21.30645601474163]
  元々のQ-ラーニングは、非常に大きなネットワークにわたるパフォーマンスと複雑性の課題に悩まされている。 従来のQ-ラーニングに適応したモデルフリーアンサンブル強化学習アルゴリズムを提案する。 計算結果から,提案アルゴリズムは平均ポリシエラーを最大55%,実行時複雑性を最大50%削減できることがわかった。
  論文  参考訳（メタデータ） (2024-02-08T08:08:23Z)
• Pointer Networks with Q-Learning for Combinatorial Optimization [55.2480439325792]
  我々は、モデルフリーQ値ポリシー近似をPointer Networks(Ptr-Nets)と統合したハイブリッドニューラルネットワークであるPointer Q-Network(PQN)を紹介する。 実験により,本手法の有効性を実証し,不安定な環境でモデルをテストする。
  論文  参考訳（メタデータ） (2023-11-05T12:03:58Z)
• Unifying (Quantum) Statistical and Parametrized (Quantum) Algorithms [65.268245109828]
  我々はカーンズのSQオラクルとヴァリアントの弱い評価オラクルからインスピレーションを得ます。 評価クエリから学習するための非条件の下限を出力する,広範かつ直感的なフレームワークを提案する。
  論文  参考訳（メタデータ） (2023-10-26T18:23:21Z)
• Rethinking Model Selection and Decoding for Keyphrase Generation with Pre-trained Sequence-to-Sequence Models [76.52997424694767]
  キーフレーズ生成(英: Keyphrase Generation, KPG)は、NLPにおける長年の課題である。 Seq2seq 事前訓練言語モデル (PLM) は KPG に転換期を迎え、有望な性能改善をもたらした。 本稿では, PLM に基づく KPG におけるモデル選択と復号化戦略の影響について, 系統解析を行った。
  論文  参考訳（メタデータ） (2023-10-10T07:34:45Z)
• Matching Game for Optimized Association in Quantum Communication Networks [65.16483325184237]
  本稿では,量子スイッチのためのスワップスタブルな要求-QSアソシエーションアルゴリズムを提案する。 サービスされた要求の割合で、ほぼ最適(5%)のパフォーマンスを達成する。 QCNのサイズが大きくなると、スケーラビリティが向上し、ほぼ最適性能を維持することが示されている。
  論文  参考訳（メタデータ） (2023-05-22T03:39:18Z)
• Reinforcement Learning Quantum Local Search [0.0]
  我々は、量子局所探索(QLS)におけるサブプロブレム選択の改善のためのエージェントを訓練するための強化学習(RL)に基づくアプローチを提案する。 提案手法は,完全連結ランダムイジング問題に対するQLSの平均近似比を効果的に向上することを示した。
  論文  参考訳（メタデータ） (2023-04-13T13:07:19Z)
• RELS-DQN: A Robust and Efficient Local Search Framework for Combinatorial Optimization [11.269582666887324]
  本稿では,DQNフレームワークのRELS-DQNを紹介する。 1つのアプリケーションでトレーニングされたRELS-DQNモデルを使用することで、ローカル検索アルゴリズムと既存のDQNモデルの両方に等しい解値を提供することで、様々なアプリケーションに一般化することができる。
  論文  参考訳（メタデータ） (2023-04-11T18:01:49Z)
• NISQ Algorithm for Semidefinite Programming [0.0]
  半有限計画法(SDP)のNISQアルゴリズムについて述べる。 NISQ固有解器の設計には,SDPに基づくハミルトン基底状態問題の定式化を利用する。 我々の研究は、過去数十年で最も成功したアルゴリズムフレームワークの1つにNISQコンピュータの応用を拡張しました。
  論文  参考訳（メタデータ） (2021-06-07T18:08:53Z)
• A* Search Without Expansions: Learning Heuristic Functions with Deep Q-Networks [70.0197695666261]
  Q*検索は,ノードの子どもの移動コストと値の和を利用するために,深いQ-networksを用いて探索をガイドする検索アルゴリズムである。 我々は1872のメタアクションを含む大きなアクション空間で定式化された場合、Q*探索を用いてルービックキューブを解く。 Q*検索は最大129倍速く、A*検索の最大1288倍のノードを生成する。
  論文  参考訳（メタデータ） (2021-02-08T20:36:41Z)

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

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