Daily Arxiv

This is a page that curates AI-related papers published worldwide.
All content here is summarized using Google Gemini and operated on a non-profit basis.
Copyright for each paper belongs to the authors and their institutions; please make sure to credit the source when sharing.

REMS: a unified solution representation, problem modeling and metaheuristic algorithm design for general combinatorial optimization problems

Created by
  • Haebom

Author

Aijuan Song, Guohua Wu

Outline

This paper presents a resource-centric modeling and solution framework (REMS) for formulating diverse combinatorial optimization problems (COPs) as a unified paradigm and designing reusable metaheuristic algorithms. REMS decomposes a COP into resources and tasks, and constructs a problem model by deriving variables, objective functions, and constraints based on a unified solution structure that assigns tasks to given resources. Based on this unified solution structure, we design basic operators such as initial solution, neighborhood structure, destruction and recovery, crossover, and ranking, and develop various metaheuristic algorithms. We validate the effectiveness of REMS through experiments on ten diverse COPs (including routing, location, loading, assignment, scheduling, and graph coloring) using four single-point-based algorithms and one group-based algorithm. We demonstrate that REMS outperforms GUROBI and SCIP on large-scale and complex COP problems, and outperforms OR-TOOLS on some difficult COP problems.

Takeaways, Limitations

Takeaways:
A new framework (REMS) is presented to comprehensively model and resolve various COPs.
Providing basic operators for developing reusable metaheuristic algorithms.
Providing efficient solutions to large-scale and complex COP problems.
Demonstrated competitive performance compared to existing optimization solvers (GUROBI, SCIP, OR-TOOLS)
Limitations:
Further research is needed to determine the scope of applicable COPs within the REMS framework.
Exploring the generalization and improvement possibilities of the proposed metaheuristic algorithm.
Extensive experimental validation of various types of COPs is needed.
Additional comparative performance analysis is needed against optimized algorithms for specific COPs.
👍