统一建模与求解离散优化问题,一套框架适配多种难题。
REMS: a unified solution representation, problem modeling and metaheuristic algorithm design for general combinatorial optimization problems
- 以资源与任务为中心构建统一问题模型
- 10类典型问题均成功建模并高效求解
- 适合需要快速适配新优化问题的研究者
离散变量且搜索空间有限的组合优化问题(COPs)在众多领域至关重要,而基于元启发式算法求解是主流方法。然而,针对特定问题通常需定制开发算法,微小调整(如约束变化)也可能导致重写。为此,首次提出资源中心化建模与求解框架REMS。通过提取问题中的资源与任务,将解结构统一为任务到资源的分配,由此推导出变量、目标与约束,构建统一问题模型。基于此结构设计了初始化、邻域、破坏修复、交叉与排序等基础算子,支持多种元启发式算法实现。本文配置了4种单点算法与1种群体算法。在涵盖路径规划、选址、装载、分配、调度及图着色等10类典型问题上验证,REMS可有效建模并求解,尤其在大规模与复杂实例上优于GUROBI和SCIP,部分场景超越OR-TOOLS。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。