論文の概要: A Model-Oriented Approach for Lifting Symmetries in Answer Set Programming

• arxiv url: http://arxiv.org/abs/2208.03095v1
• Date: Fri, 5 Aug 2022 10:50:03 GMT
• ステータス: 処理完了
• システム内更新日: 2022-08-08 13:17:43.361481
• Title: A Model-Oriented Approach for Lifting Symmetries in Answer Set Programming
• Title（参考訳）: 解集合プログラミングにおけるリフティング対称性のモデル指向アプローチ
• Authors: Alice Tarzariol (University of Klagenfurt)
• Abstract要約: 我々は,小問題インスタンスのSBCを解釈可能な一階制約の集合に引き上げる,新しいモデル指向アンサーセットプログラミングを導入する。 簡単な問題をターゲットにして,先進的な意思決定問題にも適用できるように拡張することを目指している。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: When solving combinatorial problems, pruning symmetric solution candidates from the search space is essential. Most of the existing approaches are instance-specific and focus on the automatic computation of Symmetry Breaking Constraints (SBCs) for each given problem instance. However, the application of such approaches to large-scale instances or advanced problem encodings might be problematic since the computed SBCs are propositional and, therefore, can neither be meaningfully interpreted nor transferred to other instances. As a result, a time-consuming recomputation of SBCs must be done before every invocation of a solver. To overcome these limitations, we introduce a new model-oriented approach for Answer Set Programming that lifts the SBCs of small problem instances into a set of interpretable first-order constraints using a form of machine learning called Inductive Logic Programming. After targeting simple combinatorial problems, we aim to extend our method to be applied also for advanced decision and optimization problems.
• Abstract（参考訳）: 組合せ問題を解くとき、探索空間から対称解候補を刈り取ることが不可欠である。 既存のアプローチのほとんどはインスタンス固有であり、各問題インスタンスに対してSBC(Symmetry Breaking Constraints)の自動計算に重点を置いている。 しかしながら、計算されたsbcは命題的であるため、大規模インスタンスや高度な問題エンコーディングへのそのようなアプローチの適用は問題となりうるため、意味のある解釈も他のインスタンスへの転送もできない。 その結果、SBCの計算に要する時間は、ソルバの呼び出しに先立って行う必要がある。 これらの制約を克服するために、我々は、小さな問題インスタンスのSBCをインダクティブ論理プログラミング(Inductive Logic Programming)という機械学習形式を用いて解釈可能な一階制約のセットに引き上げる、Answer Set Programmingの新しいモデル指向のアプローチを導入する。 提案手法は,単純な組合せ問題を対象として,高度な決定・最適化問題にも適用できるように拡張することを目的としている。

関連論文リスト

• Metaheuristics for the Template Design Problem: Encoding, Symmetry and Hybridisation [0.0]
  テンプレート設計問題(TDP)は、多くの対称性を持つ難しい問題であり、それをより複雑にしている。 本稿では,テンプレート設計の適合性を評価することを目的として,多種多様なメタヒューリスティクスを探索し,解析する。
  論文  参考訳（メタデータ） (2024-11-05T06:29:12Z)
• Optimizing Solution-Samplers for Combinatorial Problems: The Landscape of Policy-Gradient Methods [52.0617030129699]
  本稿では,DeepMatching NetworksとReinforcement Learningメソッドの有効性を解析するための新しい理論フレームワークを提案する。 我々の主な貢献は、Max- and Min-Cut、Max-$k$-Bipartite-Bi、Maximum-Weight-Bipartite-Bi、Traveing Salesman Problemを含む幅広い問題である。 本分析の副産物として,バニラ降下による新たな正則化プロセスを導入し,失効する段階的な問題に対処し,悪い静止点から逃れる上で有効であることを示す理論的および実験的証拠を提供する。
  論文  参考訳（メタデータ） (2023-10-08T23:39:38Z)
• Numerical Methods for Convex Multistage Stochastic Optimization [86.45244607927732]
  最適化プログラミング(SP)、最適制御(SOC)、決定プロセス(MDP)に焦点を当てる。 凸多段マルコフ問題の解決の最近の進歩は、動的プログラミング方程式のコスト対ゴー関数の切断面近似に基づいている。 切削平面型法は多段階問題を多段階的に扱えるが、状態(決定)変数は比較的少ない。
  論文  参考訳（メタデータ） (2023-03-28T01:30:40Z)
• Self-adaptive algorithms for quasiconvex programming and applications to machine learning [0.0]
  凸線探索技術や,軽微な仮定の下での汎用的アプローチを含まない,自己適応的なステップサイズ戦略を提案する。 提案手法は,いくつかの計算例から予備的な結果によって検証される。 大規模問題に対する提案手法の有効性を実証するため,機械学習実験に適用した。
  論文  参考訳（メタデータ） (2022-12-13T05:30:29Z)
• Symmetric Tensor Networks for Generative Modeling and Constrained Combinatorial Optimization [72.41480594026815]
  ポートフォリオ最適化からロジスティクスに至るまで、制約付き最適化問題は業界に多い。 これらの問題の解決における主要な障害の1つは、有効な検索空間を制限する非自明なハード制約の存在である。 本研究では、Ax=bという形の任意の整数値等式制約をU(1)対称ネットワーク(TN)に直接エンコードし、それらの適用性を量子に着想を得た生成モデルとして活用する。
  論文  参考訳（メタデータ） (2022-11-16T18:59:54Z)
• Efficient lifting of symmetry breaking constraints for complex combinatorial problems [9.156939957189502]
  この作業は、Answer Set Programmingのためのモデルベースのアプローチの学習フレームワークと実装を拡張します。 Inductive Logic Programming System ILASPに新たなコンフリクト解析アルゴリズムを組み込む。
  論文  参考訳（メタデータ） (2022-05-14T20:42:13Z)
• Lifting Symmetry Breaking Constraints with Inductive Logic Programming [2.036811219647753]
  我々は、Symmetry Breaking Constraintsを解釈可能な一階制約の集合に引き上げる、Answer Set Programmingのための新しいモデル指向のアプローチを導入する。 実験は、我々のフレームワークがインスタンス固有のSBCから一般的な制約を学習できることを実証する。
  論文  参考訳（メタデータ） (2021-12-22T11:27:48Z)
• Transformer-based Machine Learning for Fast SAT Solvers and Logic Synthesis [63.53283025435107]
  CNFベースのSATとMaxSATは論理合成と検証システムの中心である。 そこで本研究では,Transformerアーキテクチャから派生したワンショットモデルを用いて,MaxSAT問題の解法を提案する。
  論文  参考訳（メタデータ） (2021-07-15T04:47:35Z)
• Randomized Stochastic Variance-Reduced Methods for Stochastic Bilevel Optimization [62.87181271021217]
  機械学習に多くの応用がある非SBO問題を考察する。 本稿では,非SBO問題に対する高速ランダム化アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-05-05T18:28:42Z)
• QROSS: QUBO Relaxation Parameter Optimisation via Learning Solver Surrogates [14.905085636501438]
  問題のインスタンスの集合に関するソルバデータから学習することで,quboソルバのサロゲートモデルを構築する。 このようにして、インスタンスの共通構造とそれらの解決者との相互作用を捉えることができ、ペナルティパラメータを適切に選択することができる。 qrossは分散型データセットや様々な種類のquboソルバによく一般化されている。
  論文  参考訳（メタデータ） (2021-03-19T09:06:12Z)
• Conditional gradient methods for stochastically constrained convex minimization [54.53786593679331]
  構造凸最適化問題に対する条件勾配に基づく2つの新しい解法を提案する。 私たちのフレームワークの最も重要な特徴は、各イテレーションで制約のサブセットだけが処理されることです。 提案アルゴリズムは, 条件勾配のステップとともに, 分散の低減と平滑化に頼り, 厳密な収束保証を伴っている。
  論文  参考訳（メタデータ） (2020-07-07T21:26:35Z)

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

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