論文の概要: TabID: Automatic Identification and Tabulation of Subproblems in Constraint Models
- arxiv url: http://arxiv.org/abs/2202.13250v2
- Date: Sat, 31 May 2025 20:09:39 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-06-03 20:53:52.731957
- Title: TabID: Automatic Identification and Tabulation of Subproblems in Constraint Models
- Title（参考訳）: TabID:制約モデルにおけるサブプロブレムの自動同定とタブレーション
- Authors: Özgür Akgün, Ian P. Gent, Christopher Jefferson, Zeynep Kiziltan, Ian Miguel, Peter Nightingale, András Z. Salamon, Felix Ulrich-Oltean,
- Abstract要約: 本稿では,有望なサブプロブレムを自動で同定するTabIDを提案する。
我々は、標準CP(Minion and Gecode)、節学習CP(Chuffed and OR-Tools)、SATソルバ(Kissat)など、様々な問題解決者に対するアプローチを評価した。
- 参考スコア（独自算出の注目度）: 2.126037775904598
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: The performance of a constraint model can often be improved by converting a subproblem into a single table constraint (referred to as tabulation). Finding subproblems to tabulate is traditionally a manual and time-intensive process, even for expert modellers. This paper presents TabID, an entirely automated method to identify promising subproblems for tabulation in constraint programming. We introduce a diverse set of heuristics designed to identify promising candidates for tabulation, aiming to improve solver performance. These heuristics are intended to encapsulate various factors that contribute to useful tabulation. We also present additional checks to limit the potential drawbacks of suboptimal tabulation. We comprehensively evaluate our approach using benchmark problems from existing literature that previously relied on manual identification by constraint programming experts of constraints to tabulate. We demonstrate that our automated identification and tabulation process achieves comparable, and in some cases improved results. We empirically evaluate the efficacy of our approach on a variety of solvers, including standard CP (Minion and Gecode), clause-learning CP (Chuffed and OR-Tools) and SAT solvers (Kissat). Our findings highlight the substantial potential of fully automated tabulation, suggesting its integration into automated model reformulation tools.
- Abstract（参考訳）: 制約モデルの性能は、サブプロブレムを単一のテーブルの制約に変換することで改善される(タブ化として参照)。
集計するサブプロブレムを見つけることは、伝統的に専門家のモデラーであっても、手動で時間を要するプロセスである。
本稿では,制約プログラミングにおける有望なサブプロブレムを同定する,完全に自動化されたTabIDを提案する。
本稿では,解析性能の向上をめざして,有望な集計候補を特定するための多種多様なヒューリスティックスを提案する。
これらのヒューリスティックスは、有用な集計に寄与する様々な要因をカプセル化することを目的としている。
また,最適なタブレーションの潜在的な欠点を抑えるための追加チェックも提示する。
従来,制約プログラミングの専門家による手動識別に頼っていた既存の文献のベンチマーク問題を用いて,我々のアプローチを網羅的に評価した。
自動識別と集計のプロセスが同等であることを示すとともに,結果が向上するケースもある。
我々は,標準CP(Minion and Gecode),節学習CP(Chuffed and OR-Tools),SATソルバ(Kissat)など,様々な問題解決者に対するアプローチの有効性を実証的に評価した。
この結果から,完全自動集計の可能性が示唆され,自動モデル修正ツールへの統合が示唆された。
関連論文リスト
- Fast Controlled Generation from Language Models with Adaptive Weighted Rejection Sampling [90.86991492288487]
トークンの制約を評価するのは 違法にコストがかかる
LCDは文字列上のグローバル分布を歪め、ローカル情報のみに基づいてトークンをサンプリングすることができる。
我々のアプローチは最先端のベースラインよりも優れていることを示す。
論文 参考訳（メタデータ） (2025-04-07T18:30:18Z) - Automatic Feature Learning for Essence: a Case Study on Car Sequencing [1.006631010704608]
問題インスタンスに最適な組み合わせを自動的に選択するために、機械学習モデルを構築するタスクについて検討する。
学習プロセスの重要な部分は、選択モデルへの入力として機能するインスタンス機能を定義することである。
私たちの貢献は、言語モデルを用いた問題インスタンスの高レベル表現から直接、インスタンス機能の自動学習です。
論文 参考訳（メタデータ） (2024-09-23T16:06:44Z) - Toward Unified Controllable Text Generation via Regular Expression
Instruction [56.68753672187368]
本稿では,正規表現の利点をフル活用し,多様な制約を一様にモデル化する命令ベース機構を用いた正規表現指導(REI)を提案する。
提案手法では,中規模言語モデルの微調整や,大規模言語モデルでの少数ショット・インコンテクスト学習のみを要し,各種制約の組み合わせに適用した場合のさらなる調整は不要である。
論文 参考訳（メタデータ） (2023-09-19T09:05:14Z) - Guided Bottom-Up Interactive Constraint Acquisition [10.552990258277434]
制約獲得システム(Constraint Acquisition, CA)は制約満足度問題のモデル化を支援する。
現在の対話型CAアルゴリズムは、少なくとも2つの大きなボトルネックに悩まされている。
本稿では,CAの効率を向上する2つの新しい手法を提案する。
論文 参考訳（メタデータ） (2023-07-12T12:25:37Z) - ACE, a generic constraint solver [1.550120821358415]
制約プログラミング(CP)は制約された問題のモデリングと解決に有用な技術である。
本稿では,Javaで開発されたオープンソースの制約解決ツールACEについて述べる。
論文 参考訳（メタデータ） (2023-01-06T12:15:18Z) - Symmetric Tensor Networks for Generative Modeling and Constrained
Combinatorial Optimization [72.41480594026815]
ポートフォリオ最適化からロジスティクスに至るまで、制約付き最適化問題は業界に多い。
これらの問題の解決における主要な障害の1つは、有効な検索空間を制限する非自明なハード制約の存在である。
本研究では、Ax=bという形の任意の整数値等式制約をU(1)対称ネットワーク(TN)に直接エンコードし、それらの適用性を量子に着想を得た生成モデルとして活用する。
論文 参考訳（メタデータ） (2022-11-16T18:59:54Z) - 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) - Solving weakly supervised regression problem using low-rank manifold
regularization [77.34726150561087]
我々は弱い教師付き回帰問題を解く。
weakly"の下では、いくつかのトレーニングポイントではラベルが知られ、未知のものもあれば、無作為なノイズの存在やリソースの欠如などの理由によって不確かであることが分かっています。
数値的な節ではモンテカルロモデルを用いて提案手法を人工と実のデータセットに適用した。
論文 参考訳（メタデータ） (2021-04-13T23:21:01Z) - Tabling Optimization for Contextual Abduction [0.0]
本稿では,タブリングの既存実装におけるコンテキスト推論における問題点について述べる。
本稿では, 整合性制約に対する新しいプログラム変換法を提案する。
さらに、テーブルへの述語の選択と、問題の表現を実用的に単純化することで、テーブルメモリの使用を最適化する。
論文 参考訳（メタデータ） (2020-09-22T00:49:10Z) - Conditional gradient methods for stochastically constrained convex
minimization [54.53786593679331]
構造凸最適化問題に対する条件勾配に基づく2つの新しい解法を提案する。
私たちのフレームワークの最も重要な特徴は、各イテレーションで制約のサブセットだけが処理されることです。
提案アルゴリズムは, 条件勾配のステップとともに, 分散の低減と平滑化に頼り, 厳密な収束保証を伴っている。
論文 参考訳（メタデータ） (2020-07-07T21:26:35Z) - An Integer Linear Programming Framework for Mining Constraints from Data [81.60135973848125]
データから制約をマイニングするための一般的なフレームワークを提案する。
特に、構造化された出力予測の推論を整数線形プログラミング(ILP)問題とみなす。
提案手法は,9×9のスドクパズルの解法を学習し,基礎となるルールを提供することなく,例からツリー問題を最小限に分散させることが可能であることを示す。
論文 参考訳（メタデータ） (2020-06-18T20:09:53Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。