REMS: A Unified Solution Representation, Problem Modeling and Metaheuristic Algorithm Design for General Combinatorial Optimization Problems

Aijuan Song; Guohua Wu

doi:10.1109/JAS.2026.125864

Volume 13 Issue 9

Sep. 2026

IEEE/CAA Journal of Automatica Sinica

JCR Impact Factor: 18.3, Top 1 (SCI Q1)

CiteScore: 28.2, Top 1% (Q1)
Google Scholar h5-index: 95， TOP 5

Turn off MathJax

Article Contents

Article Navigation > IEEE/CAA Journal of Automatica Sinica > 2026 > 13(9): 2062-2077

A. Song and G. Wu, “REMS: A unified solution representation, problem modeling and metaheuristic algorithm design for general combinatorial optimization problems,” IEEE/CAA J. Autom. Sinica, vol. 13, no. 9, pp. 2062–2077, Sep. 2026. doi: 10.1109/JAS.2026.125864

Citation:

A. Song and G. Wu, “REMS: A unified solution representation, problem modeling and metaheuristic algorithm design for general combinatorial optimization problems,” IEEE/CAA J. Autom. Sinica, vol. 13, no. 9, pp. 2062–2077, Sep. 2026. doi: 10.1109/JAS.2026.125864

Citation:

PDF( 3275 KB)

REMS: A Unified Solution Representation, Problem Modeling and Metaheuristic Algorithm Design for General Combinatorial Optimization Problems

doi: 10.1109/JAS.2026.125864

Aijuan Song^,,
Guohua Wu^{,
,}

Funds: This work was supported by the National Natural Science Foundation of China (62373380, 62403493), the Fundamental Research Funds for the Central Universities of Central South University (2025ZZTS0108), and the Natural Science Foundation of Hunan Province (2025JJ10007)

More Information

Abstract

Abstract

Combinatorial optimization problems (COPs) with discrete variables and finite search spaces are critical across various 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, it is valuable to leverage general problem domain knowledge to establish a framework that formulates diverse COPs into a unified paradigm and supports the design of broadly applicable metaheuristic algorithms. A COP can typically be viewed as the process of giving resources to perform specific tasks, subject to given constraints. Motivated by this, a resource-centered modeling and solving framework (REMS) is introduced. We first extract and define resources and tasks from a COP. Subsequently, given predetermined resources, the solution structure is unified by assigning tasks to resources, from which variables, objectives, and constraints can be derived, thereby constructing the problem model. To solve the COPs, several fundamental operators are designed from the resource-task perspective 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. Specifically, 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 by the algorithms in REMS without any specific design. Furthermore, REMS is more competitive than Gurobi optimizer (GUROBI) and solving constraint integer programs (SCIP) in tackling large-scale instances and complex COPs, and outperforms OR-TOOLS on several challenging COPs.
- Combinatorial optimization,
- metaheuristic algorithm,
- problem modeling,
- unified solution representation

FullText(HTML)

¹ Supplementary Material of this paper can be found in link https://www.ieee-jas.net/article/doi/10.1109/JAS.2026.125864?pageType=en.

References(54)

References

[1]	D. Z. Du and P. M. Pardalos, Handbook of Combinatorial Optimization. New York, USA: Springer, 1998.
[2]	M. Karimi-Mamaghan, M. Mohammadi, P. Meyer, A. M. Karimi-Mamaghan, and E. G. Talbi, “Machine learning at the service of meta-heuristics for solving combinatorial optimization problems: A state-of-the-art,” Eur. J. Oper. Res., vol. 296, no. 2, pp. 393−422, Jan. 2022. doi: 10.1016/j.ejor.2021.04.032
[3]	B. Li, G. Wu, Y. He, M. Fan, and W. Pedrycz, “An overview and experimental study of learning-based optimization algorithms for the vehicle routing problem,” IEEE/CAA J. Autom. Sinica, vol. 9, no. 7, pp. 1115−1138, Jul. 2022. doi: 10.1109/JAS.2022.105677
[4]	Z. Lei, S. Gao, Z. Zhang, H. Yang, and H. Li, “A chaotic local search-based particle swarm optimizer for large-scale complex wind farm layout optimization,” IEEE/CAA J. Autom. Sinica, vol. 10, no. 5, pp. 1168−1180, May 2023. doi: 10.1109/JAS.2023.123387
[5]	A. Ekici, “A large neighborhood search algorithm and lower bounds for the variable-Sized bin packing problem with conflicts,” Eur. J. Oper. Res., vol. 308, no. 3, pp. 1007−1020, Aug. 2023. doi: 10.1016/j.ejor.2022.12.042
[6]	S. O. Krumke and C. Thielen, “The generalized assignment problem with minimum quantities,” Eur. J. Oper. Res., vol. 228, no. 1, pp. 46−55, Jul. 2013. doi: 10.1016/j.ejor.2013.01.027
[7]	S. Dauzère-Pérès, J. Ding, L. Shen, and K. Tamssaouet, “The flexible job shop scheduling problem: A review,” Eur. J. Oper. Res., vol. 314, no. 2, pp. 409−432, Apr. 2024. doi: 10.1016/j.ejor.2023.05.017
[8]	T. R. Jensen and B. Toft, Graph Coloring Problems. New York, USA: John Wiley & Sons, 1995.
[9]	E. Kaya, B. Gorkemli, B. Akay, and D. Karaboga, “A review on the studies employing artificial bee colony algorithm to solve combinatorial optimization problems,” Eng. Appl. Artif. Intell., vol. 115, Art. no. 105311, Oct. 2022. doi: 10.1016/j.engappai.2022.105311
[10]	R. Martí and G. Reinelt, Exact and Heuristic Methods in Combinatorial Optimization. 2nd ed. Berlin, Germany: Springer-Verlag, 2022.
[11]	F. Pagnozzi and T. Stützle, “Automatic design of hybrid stochastic local search algorithms for permutation flowshop problems,” Eur. J. Oper. Res., vol. 276, no. 2, pp. 409−421, Jul. 2019. doi: 10.1016/j.ejor.2019.01.018
[12]	J. Kallestad, R. Hasibi, A. Hemmati, and K. Sörensen, “A general deep reinforcement learning hyperheuristic framework for solving combinatorial optimization problems,” Eur. J. Oper. Res., vol. 309, no. 1, pp. 446−468, Aug. 2023. doi: 10.1016/j.ejor.2023.01.017
[13]	R. Martí, M. Sevaux, and K. Sörensen, “Fifty years of metaheuristics,” Eur. J. Oper. Res., vol. 321, no. 2, pp. 345−362, Mar. 2025. doi: 10.1016/j.ejor.2024.04.004
[14]	E. L. Lawler and D. E. Wood, “Branch-and-bound methods: A survey,” Oper. Res., vol. 14, no. 4, pp. 699−719, Aug. 1966. doi: 10.1007/springerreference_72456
[15]	Z. Y. Zhao, M. C. Zhou, and S. X. Liu, “Iterated greedy algorithms for flow-shop scheduling problems: A tutorial,” IEEE Trans. Autom. Sci. Eng., vol. 19, no. 3, pp. 1941−1959, Jul. 2022. doi: 10.1109/TASE.2021.3062994
[16]	M. D. Nelson, K. E. Nygard, J. H. Griffin, and W. E. Shreve, “Implementation techniques for the vehicle routing problem,” Comput. Oper. Res., vol. 12, no. 3, pp. 273−283, 1985. doi: 10.1016/0305-0548(85)90026-7
[17]	G. Laporte, M. Gendreau, J. Y. Potvin, and F. Semet, “Classical and modern heuristics for the vehicle routing problem,” Int. Tran. Oper. Res., vol. 7, no. 4−5, pp. 285−300, Sep. 2000. doi: 10.1016/s0969-6016(00)00003-4
[18]	P. Tian, J. Ma, and D. M. Zhang, “Application of the simulated annealing algorithm to the combinatorial optimisation problem with permutation property: An investigation of generation mechanism,” Eur. J. Oper. Res., vol. 118, no. 1, pp. 81−94, Oct. 1999. doi: 10.1016/S0377-2217(98)00308-7
[19]	R. Chelouah and P. Siarry, “Tabu Search applied to global optimization,” Eur. J. Oper. Res., vol. 123, no. 2, pp. 256−270, Jun. 2000. doi: 10.1016/S0377-2217(99)00255-6
[20]	S. T. W. Mara, R. Norcahyo, P. Jodiawan, L. Lusiantoro, and A. P. Rifai, “A survey of adaptive large neighborhood search algorithms and applications,” Comput. Oper. Res., vol. 146, Art. no. 105903, Oct. 2022. doi: 10.1016/j.cor.2022.105903
[21]	J. Brimberg, S. Salhi, R. Todosijević, and D. Urošević, “Variable Neighborhood Search: The power of change and simplicity,” Comput. Oper. Res., vol. 155, Art. no. 106221, Jul. 2023. doi: 10.1016/j.cor.2023.106221
[22]	B. Zhao, W. N. Chen, F. F. Wei, X. Liu, Q. Pei, and J. Zhang, “PEGA: A privacy-preserving genetic algorithm for combinatorial optimization,” IEEE Trans. Cybern., vol. 54, no. 6, pp. 3638−3651, Jun. 2024. doi: 10.1109/TCYB.2023.3346863
[23]	F. Peres and M. Castelli, “Combinatorial optimization problems and metaheuristics: Review, challenges, design, and development,” Appl. Sci., vol. 11, no. 14, Art. no. 6449, Jul. 2021. doi: 10.3390/app11146449
[24]	E. J. B. Moreira and S. A. A. De Freitas, “A CP-SAT approach for academic resource timetabling in higher education institutions: A case study at a major public university,” in Proc. 21st Int. Conf. Information Technology Based Higher Education and Training, Paris, France, 2024, pp. 1−8.
[25]	K. Thakurani, “Leveraging SAT-SMT for TA scheduling optimization: Enhancing efficiency and effectiveness,” B.S. dissertation, Faculty of Electrical Engineering, Mathematics and Computer Science, University of Twente, Enschede, The Netherlands, 2024.
[26]	A. Bit-Monnot, “Enhancing hybrid CP-SAT search for disjunctive scheduling,” in Proc. ECAI, Amsterdam, The Netherlands, 2023, pp. 255−262.
[27]	T. Cuvelier, F. Didier, V. Furnon, S. Gay, S. Mohajeri, and L. Perron, “OR-tools’ vehicle routing solver: A generic constraint-programming solver with heuristic search for routing problems,” in 24th Annual Congress of the French Society of Operations Research and Decision Support, Rennes, France, 2023.
[28]	L. Blaise, “Modeling Scheduling Problems with Hexaly,” 2025. [Online]. Available: https://www.hexaly.com/wp-content/uploads/2025/04/MIM2025_Scheduling_Models-1.pdf. Accessed: Dec. 20, 2025
[29]	L. Zhang, H. Pingaud, F. Fontanili, E. Lamine, C. Martinez, C. Bortolaso, and M. Derras, “Balancing the satisfaction of stakeholders in home health care coordination: A novel OptaPlanner CSP model,” Health Syst., vol. 12, no. 4, pp. 408−428, Feb. 2023. doi: 10.1080/20476965.2023.2179947
[30]	T. Vidal, T. G. Crainic, M. Gendreau, and C. Prins, “A unified solution framework for multi-attribute vehicle routing problems,” Eur. J. Oper. Res., vol. 234, no. 3, pp. 658−673, May 2014. doi: 10.1016/j.ejor.2013.09.045
[31]	C. Blum, P. Pinacho, M. López-Ibáñez, and J. A. Lozano, “Construct, Merge, Solve & Adapt A new general algorithm for combinatorial optimization,” Comput. Oper. Res., vol. 68, pp. 75−88, Apr. 2016. doi: 10.1016/j.cor.2015.10.014
[32]	M. S. Sarafraz and M. S. Tavazoei, “A unified optimization-based framework to adjust consensus convergence rate and optimize the network topology in uncertain multi-agent systems,” IEEE/CAA J. Autom. Sinica, vol. 8, no. 9, pp. 1539−1548, Sep. 2021. doi: 10.1109/JAS.2021.1004111
[33]	X. Shi, X. Xu, G. Wen, and J. Cao, “Fixed-time gradient flows for solving constrained optimization: A unified approach,” IEEE/CAA J. Autom. Sinica, vol. 11, no. 8, pp. 1849−1864, Aug. 2024. doi: 10.1109/JAS.2023.124089
[34]	Y. D. Kwon, J. Choo, B. Kim, I. Yoon, Y. Gwon, and S. Min, “POMO: Policy optimization with multiple optima for reinforcement learning,” in Proc. 34th Int. Conf. Neural Information Processing Systems, Vancouver, Canada, 2020, Art. no. 1779.
[35]	X. Wu, D. Wang, L. Wen, Y. Xiao, C. Wu, Y. Wu, C. Yu, D. L. Maskell, and Y. Zhou, “Neural combinatorial optimization algorithms for solving vehicle routing problems: A comprehensive survey with perspectives,” arXiv preprint arXiv: 2406.00415, 2025.
[36]	I. Bello, H. Pham, Q. V. Le, M. Norouzi, and S. Bengio, “Neural combinatorial optimization with reinforcement learning,” arXiv preprint arXiv:1611.09940, 2016.
[37]	H. C. W. Lau, T. M. Chan, W. T. Tsui, and W. K. Pang, “Application of genetic algorithms to solve the multidepot vehicle routing problem,” IEEE Trans. Autom. Sci. Eng., vol. 7, no. 2, pp. 383−392, Apr. 2010. doi: 10.1109/TASE.2009.2019265
[38]	L. Saviniec and A. A. Constantino, “Effective local search algorithms for high school timetabling problems,” Appl. Soft Comput., vol. 60, pp. 363−373, Nov. 2017. doi: 10.1016/j.asoc.2017.06.047
[39]	T. Zhen and Q. Zhang, “A hybrid metaheuristic algorithm for the multi-depot vehicle routing problem with time windows,” in Proc. Int. Conf. Networks Security, Wireless Communi. and Trusted Computing, Wuhan, China, 2009, pp. 798−801.
[40]	K. Sun, D. Zheng, H. Song, Z. Cheng, X. Lang, W. Yuan, and J. Wang, “Hybrid genetic algorithm with variable neighborhood search for flexible job shop scheduling problem in a machining system,” Expert Syst. Appl., vol. 215, Art. no. 119359, Apr. 2023. doi: 10.1016/j.eswa.2022.119359
[41]	A. Van Breedam, “Comparing descent heuristics and metaheuristics for the vehicle routing problem,” Comput. Oper. Res., vol. 28, no. 4, pp. 289−315, Apr. 2001. doi: 10.1016/S0305-0548(99)00101-X
[42]	I. H. Osman, “Heuristics for the generalised assignment problem: Simulated annealing and tabu search approaches,” Oper.-Res.-Spektrum, vol. 17, no. 4, pp. 211−225, Dec. 1995. doi: 10.1007/BF01720977
[43]	R. Sridharan, “The capacitated plant location problem,” Eur. J. Oper. Res., vol. 87, no. 2, pp. 203−213, Dec. 1995. doi: 10.1016/0377-2217(95)00042-O
[44]	A. E. F. Muritiba, M. Iori, E. Malaguti, and P. Toth, “Algorithms for the bin packing problem with conflicts,” INFORMS J. Comput., vol. 22, no. 3, pp. 401−415, Oct. 2010. doi: 10.1287/ijoc.1090.0355
[45]	M. M. Baldi, D. Manerba, G. Perboli, and R. Tadei, “A generalized bin packing problem for parcel delivery in last-mile logistics,” Eur. J. Oper. Res., vol. 274, no. 3, pp. 990−999, May 2019. doi: 10.1016/j.ejor.2018.10.056
[46]	L. Galli, S. Martello, C. Rey, and P. Toth, “Polynomial-size formulations and relaxations for the quadratic multiple knapsack problem,” Eur. J. Oper. Res., vol. 291, no. 3, pp. 871−882, Jun. 2021. doi: 10.1016/j.ejor.2020.10.047
[47]	E. Taillard, “Benchmarks for basic scheduling problems,” Eur. J. Oper. Res., vol. 64, no. 2, pp. 278−285, Jan. 1993. doi: 10.1016/0377-2217(93)90182-M
[48]	C. Fleurent and J. A. Ferland, “Genetic and hybrid algorithms for graph coloring,” Ann. Oper. Res., vol. 63, no. 3, pp. 437−461, Jun. 1996. doi: 10.1007/BF02125407
[49]	B. Romera-Paredes, M. Barekatain, A. Novikov, M. Balog, M. P. Kumar, E. Dupont, F. J. R. Ruiz, J. S. Ellenberg, P. Wang, O. Fawzi, et al., “Mathematical discoveries from program search with large language models,” Nature, vol. 625, no. 7995, pp. 468−475, Dec. 2024. doi: 10.1038/s41586-023-06924-6
[50]	F. Liu, X. Tong, M. Yuan, X. Lin, F. Luo, Z. Wang, Z. Lu, and Q. Zhang, “Evolution of heuristics: Towards efficient automatic algorithm design using large language model,” in Proc. 41st Int. Conf. Machine Learning, Vienna, Austria, 2024, pp. 32201−32223.
[51]	X. Yang, L. Zhang, H. Qian, L. Song, and J. Bian, “HeurAgenix: Leveraging LLMs for solving complex combinatorial optimization challenges,” arXiv preprint arXiv: 2506.15196, 2025.
[52]	G. Wu, R. Mallipeddi, and P. N. Suganthan, “Ensemble strategies for population-based optimization algorithms−A survey,” Swarm Evol. Comput., vol. 44, pp. 695−711, Feb. 2019. doi: 10.1016/j.swevo.2018.08.015
[53]	A. Song, G. Wu, L. Zhou, L. Wang, and W. Pedrycz, “Exact and metaheuristic algorithms for variable reduction,” IEEE Trans. Evol. Comput., vol. 28, no. 6, pp. 1704−1718, Dec. 2024. doi: 10.1109/TEVC.2023.3332913
[54]	Y. Sun, X. Li, and A. Ernst, “Using statistical measures and machine learning for graph reduction to solve maximum weight clique problems,” IEEE Trans. Pattern Anal. Mach. Intell., vol. 43, no. 5, pp. 1746−1760, May 2021. doi: 10.1109/TPAMI.2019.2954827