論文の概要: REMS: a unified solution representation, problem modeling and metaheuristic algorithm design for general combinatorial optimization problems
- arxiv url: http://arxiv.org/abs/2505.17108v1
- Date: Wed, 21 May 2025 11:21:58 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-05-26 18:08:33.571712
- Title: REMS: a unified solution representation, problem modeling and metaheuristic algorithm design for general combinatorial optimization problems
- Title（参考訳）: REMS:一般組合せ最適化問題に対する統合解表現、問題モデリングおよびメタヒューリスティックアルゴリズムの設計
- Authors: Aijuan Song, Guohua Wu,
- Abstract要約: 離散変数と有限探索空間を持つ組合せ最適化問題(COP)は、多くの分野において重要な問題である。
リソース中心モデリングおよび問題解決フレームワーク(REMS)を初めて紹介する。
REMSはこれらのCOPを統一パラダイム内でモデル化し、設計したメタヒューリスティックアルゴリズムで効果的に解決することができる。
- 参考スコア（独自算出の注目度）: 3.067143391336441
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Combinatorial optimization problems (COPs) with discrete variables and finite search space are critical across numerous fields, and solving them in metaheuristic algorithms is popular. However, addressing a specific COP typically requires developing a tailored and handcrafted algorithm. Even minor adjustments, such as constraint changes, may necessitate algorithm redevelopment. Therefore, establishing a framework for formulating diverse COPs into a unified paradigm and designing reusable metaheuristic algorithms is valuable. A COP can be typically viewed as the process of giving resources to perform specific tasks, subjecting to given constraints. Motivated by this, a resource-centered modeling and solving framework (REMS) is introduced for the first time. We first extract and define resources and tasks from a COP. Subsequently, given predetermined resources, the solution structure is unified as assigning tasks to resources, from which variables, objectives, and constraints can be derived and a problem model is constructed. To solve the modeled COPs, several fundamental operators are designed based on the unified solution structure, including the initial solution, neighborhood structure, destruction and repair, crossover, and ranking. These operators enable the development of various metaheuristic algorithms. Specially, 4 single-point-based algorithms and 1 population-based algorithm are configured herein. Experiments on 10 COPs, covering routing, location, loading, assignment, scheduling, and graph coloring problems, show that REMS can model these COPs within the unified paradigm and effectively solve them with the designed metaheuristic algorithms. Furthermore, REMS is more competitive than GUROBI and SCIP in tackling large-scale instances and complex COPs, and outperforms OR-TOOLS on several challenging COPs.
- Abstract（参考訳）: 離散変数と有限探索空間を持つ組合せ最適化問題(COP)は、多くの分野において重要であり、メタヒューリスティックアルゴリズムでそれらを解くことが一般的である。
しかし、特定のCOPに対処するには、通常、調整された手作りのアルゴリズムを開発する必要がある。
制約変更のような小さな調整でさえ、アルゴリズムの再開発を必要とする可能性がある。
したがって,多様なCOPを統一パラダイムに定式化し,再利用可能なメタヒューリスティックアルゴリズムを設計するための枠組みを確立することは重要である。
COPは一般に、与えられた制約に従って特定のタスクを実行するリソースを与えるプロセスとみなすことができる。
これにより、リソース中心のモデリングおよび解決フレームワーク(REMS)が初めて導入された。
まず、COPからリソースとタスクを抽出し、定義する。
その後、所定のリソースが与えられた場合、解構造はリソースへのタスク割り当てとして統一され、そこから変数、目的、制約が導出され、問題モデルが構築される。
モデリングされたCOPを解くために、初期解、近傍構造、破壊と修復、クロスオーバー、ランキングを含む統一された解構造に基づいて、いくつかの基本演算子を設計する。
これらの演算子は様々なメタヒューリスティックアルゴリズムの開発を可能にする。
特に、4つの単一点ベースアルゴリズムと1つの集団ベースアルゴリズムが構成されている。
10個のCOPの実験では、ルーティング、ロケーション、ローディング、割り当て、スケジューリング、グラフカラー化の問題をカバーし、REMSがこれらのCOPを統一パラダイム内でモデル化し、設計したメタヒューリスティックアルゴリズムで効果的に解決できることが示されている。
さらに、REMSは大規模インスタンスや複雑なCOPの処理においてGUROBIやSCIPよりも競争力があり、いくつかの挑戦的なCOPではOR-TOOLSよりも優れています。
関連論文リスト
- PlanGEN: A Multi-Agent Framework for Generating Planning and Reasoning Trajectories for Complex Problem Solving [89.60370366013142]
制約,検証,選択という3つの重要な要素を持つモデルに依存しない,スケーラブルなエージェントフレームワークであるPlanGENを提案する。
具体的には、推論時間アルゴリズムの性能を向上させるために、制約誘導反復検証を提案する。
論文 参考訳（メタデータ） (2025-02-22T06:21:56Z) - A Multiagent Path Search Algorithm for Large-Scale Coalition Structure Generation [61.08720171136229]
結合構造生成はマルチエージェントシステムにおける基本的な計算問題である。
我々はCSGの多エージェントパス探索アルゴリズムであるSALDAEを開発し、連立構造グラフ上で運用する。
論文 参考訳（メタデータ） (2025-02-14T15:21:27Z) - Memetic collaborative approaches for finding balanced incomplete block designs [0.0]
平衡不完全ブロック設計(BIBD)問題は、多数の対称性を持つ難しい問題である。
本稿では,古典的二元数定式化の代替として機能する双対(整数)問題表現を提案する。
論文 参考訳（メタデータ） (2024-11-04T16:41:18Z) - Bridging Large Language Models and Optimization: A Unified Framework for Text-attributed Combinatorial Optimization [21.232626415696267]
Language-based Neural COPsolvr (LNCS)は、多種多様なテキスト対応COPのエンドツーエンド解決のために統一された新しいフレームワークである。
広汎な実験により、LNCSの有効性と一般化性が検証され、現実世界のCOPアプリケーションのための統一的で実用的なフレームワークとしての可能性を強調した。
論文 参考訳（メタデータ） (2024-08-22T08:42:44Z) - Factorization of Multi-Agent Sampling-Based Motion Planning [72.42734061131569]
現代のロボティクスは、共有環境内で複数のエンボディエージェントを動作させることが多い。
標準的なサンプリングベースのアルゴリズムは、ロボットの関節空間における解の探索に使用できる。
我々は、因子化の概念をサンプリングベースアルゴリズムに統合し、既存の手法への最小限の変更しか必要としない。
本稿では, PRM* のサンプル複雑性の観点から解析的ゲインを導出し, RRG の実証結果を示す。
論文 参考訳（メタデータ） (2023-04-01T15:50:18Z) - An Efficient Merge Search Matheuristic for Maximising the Net Present
Value of Project Schedules [5.10800491975164]
リソース制約のあるプロジェクトスケジューリングは多くの実用的なアプリケーションにおいて重要な最適化問題である。
本稿では,資源制約のあるプロジェクトスケジューリングを解くために,マージ探索と並列計算に基づく新しい数学ヒューリスティックアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-10-20T13:30:23Z) - A Two-stage Framework and Reinforcement Learning-based Optimization
Algorithms for Complex Scheduling Problems [54.61091936472494]
本稿では、強化学習(RL)と従来の運用研究(OR)アルゴリズムを組み合わせた2段階のフレームワークを開発する。
スケジューリング問題は,有限マルコフ決定過程 (MDP) と混合整数計画過程 (mixed-integer programming process) の2段階で解決される。
その結果,本アルゴリズムは,アジャイルな地球観測衛星スケジューリング問題に対して,安定かつ効率的に十分なスケジューリング計画を得ることができた。
論文 参考訳（メタデータ） (2021-03-10T03:16:12Z) - Resource Allocation via Model-Free Deep Learning in Free Space Optical
Communications [119.81868223344173]
本稿では,自由空間光学(FSO)通信におけるチャネルフェージング効果の緩和のための資源配分の一般的な問題について検討する。
本フレームワークでは,FSO資源割り当て問題を解決する2つのアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-07-27T17:38:51Z) - Iterative Algorithm Induced Deep-Unfolding Neural Networks: Precoding
Design for Multiuser MIMO Systems [59.804810122136345]
本稿では,AIIDNN(ディープ・アンフォールディング・ニューラルネット)を一般化した,ディープ・アンフォールディングのためのフレームワークを提案する。
古典的重み付き最小二乗誤差(WMMSE)反復アルゴリズムの構造に基づく効率的なIAIDNNを提案する。
提案したIAIDNNは,計算複雑性を低減した反復WMMSEアルゴリズムの性能を効率よく向上することを示す。
論文 参考訳（メタデータ） (2020-06-15T02:57:57Z) - A Novel Multi-Agent System for Complex Scheduling Problems [2.294014185517203]
本稿では,様々な問題領域に適用可能なマルチエージェントシステムの概念と実装について述べる。
提案手法の有効性を示すため,NP-hardスケジューリング問題をシミュレートする。
本稿では,レイアウトの複雑さの低減,複雑なシステムの制御の改善,拡張性など,エージェントベースのアプローチの利点を強調した。
論文 参考訳（メタデータ） (2020-04-20T14:04:58Z) - C-CoCoA: A Continuous Cooperative Constraint Approximation Algorithm to
Solve Functional DCOPs [4.404507236193031]
本稿では,協調制約近似(CoCoA)アルゴリズムに非線形最適化法を適用した。
提案アルゴリズムは,通信コストの低減と実行時間の短縮を犠牲にして,高品質なソリューションを提供することができる。
論文 参考訳（メタデータ） (2020-02-27T20:44:25Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。