REMS: a unified solution representation, problem modeling and metaheuristic algorithm design for general combinatorial optimization problems
REMS framework models COP as resource-task assignment, enabling versatile metaheuristic algorithms; outperforms GUROBI, SCIP, OR-TOOLS on large/complex instances.
Key Findings
Methodology
REMS constructs a unified problem model by extracting resources and tasks from various COPs. Resources R and tasks T form the core sets, with solution structure represented by assigning tasks to resource positions via variable X. Attribute variables Y capture additional solution features. Based on this, fundamental operators—neighborhood, destruction, repair, crossover, ranking—are designed. These operators are integrated into multiple metaheuristics (SA, LNS, VNS, TS, GA), enabling flexible, problem-agnostic solving without problem-specific tailoring. The framework emphasizes generality, scalability, and ease of adaptation.
Key Results
- Extensive experiments on 10 diverse COPs, including routing, location, loading, scheduling, and graph coloring, demonstrate REMS’s ability to model and solve effectively. The metaheuristic algorithms outperform GUROBI, SCIP, and OR-TOOLS, especially on large-scale and complex instances, reducing solution times by 20-30%.
- In nonlinear and constrained problems, REMS maintains solution quality comparable or superior to specialized algorithms, validating its broad applicability.
- Ablation studies confirm the importance of neighborhood and destruction operators, showing their critical role in search efficiency.
Significance
This work advances the field by providing a universal modeling paradigm that reduces the reliance on problem-specific algorithms. It bridges the gap between exact solvers and heuristic methods, offering a flexible, scalable, and efficient solution framework suitable for industrial-scale problems. The approach fosters automation in problem formulation and algorithm design, promising widespread impact across logistics, manufacturing, and scheduling industries.
Technical Contribution
The paper introduces a resource-centered modeling approach that simplifies diverse COPs into a common structure. It designs a set of fundamental operators compatible with various metaheuristics, enabling easy customization and extension. The framework supports multi-objective and constraint-rich problems, with a mathematically elegant yet practical formulation, significantly improving solution efficiency and adaptability over existing methods.
Novelty
This is the first comprehensive framework that models multiple COPs via a resource-task paradigm, unifying problem representation and solution strategies. The design of generic operators based on this structure offers a flexible, problem-agnostic solution approach, setting a new standard in metaheuristic algorithm development for combinatorial problems.
Limitations
- The model assumes fixed, discrete resources and tasks, limiting its direct application to problems with continuous or dynamic elements.
- Handling extremely large-scale or highly nonlinear problems still poses computational challenges, requiring further optimization of operators.
- Support for complex nonlinear objectives is limited; future work should incorporate advanced nonlinear modeling techniques.
Future Work
Future efforts will focus on extending the framework to dynamic and continuous variables, integrating machine learning techniques to adapt operators automatically, and developing hybrid models combining exact and heuristic methods. Additionally, exploring real-time applications and multi-objective optimization remains a promising direction.
AI Executive Summary
In the realm of industrial optimization, combinatorial problems such as routing, scheduling, and facility location are ubiquitous yet challenging. Traditional approaches often rely on problem-specific algorithms, which are labor-intensive to develop and lack flexibility for changing requirements. To address this, the authors introduce REMS, a novel framework that models diverse COPs through a resource-task paradigm. By extracting resources and tasks from problem instances, REMS constructs a unified solution structure where task assignments to resource positions form the core decision variables. This abstraction simplifies the problem representation, making it adaptable across different problem types.
The framework further defines attribute variables to capture additional solution features like timing and demand, enabling comprehensive modeling. Based on this structure, the authors design fundamental operators—neighborhood moves, destruction and repair, crossover, and ranking—that are compatible with multiple metaheuristics, including simulated annealing, large neighborhood search, variable neighborhood search, tabu search, and genetic algorithms. These operators facilitate efficient exploration of the solution space without the need for problem-specific tuning.
Experimental validation on 10 diverse COPs demonstrates the robustness and versatility of REMS. The algorithms outperform traditional solvers like GUROBI, SCIP, and OR-TOOLS on large and complex instances, reducing computational times and improving solution quality. Notably, in path planning and scheduling problems, REMS achieves solutions with 15-25% lower costs or makespan, showcasing its practical value.
This research marks a significant step toward universal, automated, and scalable optimization solutions. By unifying problem modeling and algorithm design, REMS reduces development effort and enhances adaptability, promising broad industrial impact. Future work aims to incorporate continuous variables, real-time data, and machine learning-driven operator adaptation, further pushing the frontier of combinatorial optimization.
Deep Dive
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.