論文の概要: Graph-Based Specification and Automated Construction of ILP Problems
- arxiv url: http://arxiv.org/abs/2212.11629v2
- Date: Wed, 15 May 2024 14:28:38 GMT
- ステータス: 処理完了
- システム内更新日: 2024-05-16 18:49:58.377317
- Title: Graph-Based Specification and Automated Construction of ILP Problems
- Title(参考訳): グラフに基づくICP問題の仕様と自動構築
- Authors: Sebastian Ehmes, Maximilian Kratz, Andy Schürr,
- Abstract要約: GIPS(Graph-based ILP Problem Specification Tool)フレームワークを導入し、ICP問題ジェネレータの開発を簡単にする。
我々のアプローチでは、特定のアプリケーションドメインに対するILP問題生成を自動生成する出発点として、GIPSL仕様を用いています。
最初の実験では、派生したICP問題生成器が、ICPの専門家によって開発された手作りプログラムと競合することを示した。
- 参考スコア(独自算出の注目度): 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In the Model-Driven Software Engineering (MDSE) community, the combination of techniques operating on graph-based models (e.g., Pattern Matching (PM) and Graph Transformation (GT)) and Integer Linear Programming (ILP) is a common occurrence, since ILP solvers offer a powerful approach to solve linear optimization problems and help to enforce global constraints while delivering optimal solutions. However, designing and specifying complex optimization problems from more abstract problem descriptions can be a challenging task. A designer must be an expert in the specific problem domain as well as the ILP optimization domain to translate the given problem into a valid ILP problem. Typically, domain-specific ILP problem generators are hand-crafted by experts, to avoid specifying a new ILP problem by hand for each new instance of a problem domain. Unfortunately, the task of writing ILP problem generators is an exercise, which has to be repeated for each new scenario, tool, and approach. For this purpose, we introduce the GIPS (Graph-Based ILP Problem Specification Tool) framework that simplifies the development of ILP problem generators for graph-based optimization problems and a new Domain-Specific Language (DSL) called GIPSL (Graph-Based ILP Problem Specification Language) that integrates GT and ILP problems on an abstract level. Our approach uses GIPSL specifications as a starting point to derive ILP problem generators for a specific application domain automatically. First experiments show that the derived ILP problem generators can compete with hand-crafted programs developed by ILP experts.
- Abstract(参考訳): モデル駆動ソフトウェアエンジニアリング(MDSE)コミュニティでは、グラフベースのモデル(例えば、パターンマッチング(PM)とグラフ変換(GT))と整数線形プログラミング(ILP)で動く技術の組み合わせが一般的である。
しかし、より抽象的な問題記述から複雑な最適化問題の設計と特定は難しい課題である。
設計者は、与えられた問題を有効なILP問題に変換するために、特定の問題領域とILP最適化領域の専門家でなければならない。
通常、ドメイン固有のICP問題生成器は、問題領域の各新しいインスタンスに対して手動で新しいILP問題を特定することを避けるために、専門家によって手作りされる。
残念ながら、ILP問題ジェネレータを書くタスクはエクササイズであり、新しいシナリオ、ツール、アプローチごとに繰り返す必要があります。
この目的のために、グラフベースの最適化問題に対するILP問題生成器の開発を簡略化するGIPS(Graph-based ILP Problem Specification Tool)フレームワークと、GIPSL(Graph-based ILP Problem Specification Language)と呼ばれる新しいドメイン特化言語(DSL)を導入し、GTとILP問題を抽象レベルで統合する。
我々のアプローチでは、特定のアプリケーションドメインに対するILP問題生成を自動生成する出発点として、GIPSL仕様を用いています。
最初の実験では、派生したICP問題生成器が、ICPの専門家によって開発された手作りプログラムと競合できることが示されている。
関連論文リスト
- EHOP: A Dataset of Everyday NP-Hard Optimization Problems [66.41749917354159]
Everyday Hard Optimization Problems (EHOP) は、自然言語で表されるNPハード最適化問題の集合である。
EHOPには、コンピュータサイエンスの教科書で見られる問題の定式化、実生活で起こりうる問題として着飾られたバージョン、逆ルールでよく知られた問題の変種が含まれている。
現状のLLMは、複数のプロンプト戦略にまたがって、実生活や逆転型よりも教科書問題を体系的に高精度に解決していることがわかった。
論文 参考訳(メタデータ) (2025-02-19T14:39:59Z) - LLM-Generated Heuristics for AI Planning: Do We Even Need Domain-Independence Anymore? [87.71321254733384]
大規模言語モデル(LLM)は、特定の計画問題に適した計画手法を生成することができる。
LLMは、いくつかの標準IPCドメインで最先端のパフォーマンスを達成することができる。
これらの結果がパラダイムシフトを意味するのか、既存の計画手法をどのように補完するかについて議論する。
論文 参考訳(メタデータ) (2025-01-30T22:21:12Z) - Comprehensive Benchmarking Environment for Worker Flexibility in Flexible Job Shop Scheduling Problems [0.0]
生産スケジューリングにおいて、フレキシブルジョブショップスケジューリング問題(FJSSP)は、一連の操作を最適化し、それぞれの処理時間を異なるマシンに割り当てることを目的としている。
結果として生じる問題はFlexible Job Shop Scheduling Problem with Worker Flexibility (FJSSP-W)と呼ばれる。
本稿では、一般に受け入れられているFJSSPインスタンス402のコレクションを示し、労働者の柔軟性で拡張するアプローチを提案する。
論文 参考訳(メタデータ) (2025-01-27T15:56:12Z) - AutoG: Towards automatic graph construction from tabular data [60.877867570524884]
グラフ構築法を形式化し,評価するためのデータセットのセットを導入する。
人間の介入なしに高品質なグラフスキーマを自動的に生成するLLMベースのソリューションAutoGを提案する。
論文 参考訳(メタデータ) (2025-01-25T17:31:56Z) - Domain-Agnostic Co-Evolution of Generalizable Parallel Algorithm Portfolios [27.138566940625385]
一般化は、データからトレーニングする際の中核的な目的である。
並列アルゴリズムポートフォリオ(PAP)とインスタンス人口を同時に進化させることによって、共進化的アプローチはこの課題に対処する。
本研究は,パラメタライズドサーチ(DACE)のドメインに依存しない共進化という,汎用的で既成のPAP構築手法を提案する。
論文 参考訳(メタデータ) (2025-01-06T10:29:48Z) - G-LLaVA: Solving Geometric Problem with Multi-Modal Large Language Model [124.68242155098189]
大規模言語モデル(LLM)は、人間レベルの推論と生成能力に顕著な習熟性を示している。
G-LLaVAは幾何学的問題の解法において例外的な性能を示し、7Bパラメータしか持たないMathVistaベンチマークにおいて GPT-4-V を著しく上回っている。
論文 参考訳(メタデータ) (2023-12-18T17:36:20Z) - Symmetry-preserving graph attention network to solve routing problems at
multiple resolutions [1.9304772860080408]
問題解決のために,最初の完全同変モデルとトレーニングを導入する。
入力グラフのマルチスケール構造を捉えることが不可欠である。
本稿では,Equi Graph Attention Network (mEGAT) アーキテクチャと組み合わせたマルチレゾリューション方式を提案する。
論文 参考訳(メタデータ) (2023-10-24T06:22:20Z) - Thought Propagation: An Analogical Approach to Complex Reasoning with Large Language Models [62.96551299003463]
大規模言語モデルの複雑な推論能力を高めるために,textbftextitThought Propagation (TP)を提案する。
TP はまず LLM に対して,入力問題に関連する類似問題の集合を提案し,解決するよう促す。
TPは、類似問題の結果を再利用して、新しいソリューションを直接生成したり、スクラッチから得られた初期ソリューションを修正するための知識集約的な実行プランを導出する。
論文 参考訳(メタデータ) (2023-10-06T01:40:09Z) - NeSIG: A Neuro-Symbolic Method for Learning to Generate Planning Problems [9.176056742068814]
我々はNe SIGを提案し、私たちの知る限り、計画問題を自動的に生成する最初のドメインに依存しない手法を提案する。
マルコフ決定プロセスとして問題生成を定式化し、Deep Reinforcement Learningを用いて2つの生成ポリシーを訓練して問題を生成する。
結果は、Ne SIGがドメイン固有のジェネレータよりもはるかに難しい、有効で多様な問題を自動生成できることを示している。
論文 参考訳(メタデータ) (2023-01-24T19:37:59Z) - GeoQA: A Geometric Question Answering Benchmark Towards Multimodal
Numerical Reasoning [172.36214872466707]
我々は、テキスト記述、視覚図、定理知識の包括的理解を必要とする幾何学的問題を解くことに注力する。
そこで本研究では,5,010の幾何学的問題を含む幾何学的質問応答データセットGeoQAを提案する。
論文 参考訳(メタデータ) (2021-05-30T12:34:17Z) - Exploring Instance Generation for Automated Planning [1.6735240552964108]
制約プログラミングと自動計画はこれらの分野の例である。
各解法の効率は、問題間だけでなく、同じ問題のインスタンス間でも異なる。
本稿では,Essenceを用いて計画上の問題記述全体をモデル化する手法を提案する。
論文 参考訳(メタデータ) (2020-09-21T19:58:33Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。