Junwen Ding

AAAI Conference 2026 Conference Paper

An Adaptive Configuration-Aware Simulated Annealing for the Maximally Diverse Grouping Problem

• Baiyu Chen
• Canhui Luo
• Junwen Ding
• Qingyun Zhang
• Zhouxing Su
• Zhipeng Lü

The maximally diverse grouping problem (MDGP) seeks to partition the vertices of a complete graph into a fixed number of groups under capacity constraints, maximizing the sum of edge weights within each group. MDGP is an NP-hard combinatorial optimization problem and has wide real-world applications. In this paper, we propose an adaptive configuration-aware simulated annealing (ACSA) algorithm to solve MDGP. First, ACSA adopts a relaxation-based insertion strategy, which temporarily relaxes capacity constraints to expand the neighborhood and allow effective exploration of promising regions. Second, a memory-based swap mechanism is introduced to integrate high-potential suboptimal swap moves into the conventional best-swap operation, thereby achieving a better balance between diversification and intensification of the search. Finally, ACSA employs a vertex-wise sequential coordination strategy to dynamically organize the insertion and swap moves, which enhances the search flexibility. Experiments on 500 benchmark instances demonstrate the strong competitiveness of ACSA, as it improves the best results among the state-of-the-art algorithms on 460 instances and matches them on 39 instances.

IJCAI Conference 2025 Conference Paper

A Weighted-Based Fast Local Search for α-Neighbor p-Center Problem

• Qingyun Zhang
• Zhipeng Lü
• Junwen Ding
• Zhouxing Su

The α-neighbor p-center problem (α-pCP) is an extension of the classical p-center problem. It aims to select p centers from a set of candidate centers to minimize the maximum distance between any client and its α service centers. In this paper, we propose a weighting-based fast local search algorithm called WFLS for solving α-pCP. First, WFLS converts the complex α-pCP into a series of decision subproblems by specifying the service radius, effectively mitigating the gradient vanishing issue during the search process, and introduces a new MIP model. Then, it addresses the simpliffed subproblems using a fast local search procedure with a swap-based neighborhood structure. WFLS adopts an efffcient weighting strategy, an incremental evaluation technique, a reffned-grained penaltybased neighborhood evaluation, and two scoring functions of neighborhood evaluation to accelerate and guide the search process. Computational experiments on 154 widely used public benchmark instances demonstrate that WFLS outperforms the state-of-the-art methods in the literature. Speciffcally, WFLS improves 69 previous best known results and matches the best know results for all the remaining ones in less time than other competitors.

AAAI Conference 2025 Conference Paper

An Elite-guided Weighted Simulated Annealing Algorithm for the Clique Partitioning Problem

• Baiyu Chen
• Junwen Ding
• Canhui Luo
• Qingyun Zhang
• Zhouxing Su
• Zhipeng Lü

The clique partitioning problem (CPP) aims to find a partition of vertices of a complete graph in order to maximize the sum of edge weights within each partition (clique), which has been proven to be NP-hard and has wide real-world applications. In this paper, we propose an elite-guided weighted simulated annealing algorithm called EWSA to solve the CPP. First, EWSA employs two specific configurations and alternates between them via an oscillation strategy, which balances the exploitation and exploration of the search. Second, a weighting strategy is introduced to improve the scoring function in traditional simulated annealing, which is able to guide the search to explore diverse solutions. Finally, a partition restriction strategy is adopted to reduce search space and increase the search efficiency. Experiments on 255 instances demonstrate the competitiveness of EWSA. For 130 open instances, EWSA discovers new upper bounds in 32 cases and matches the best known results for the others. For the remaining 125 closed instances, EWSA achieves the best known objective values within a short computational time.

EAAI Journal 2025 Journal Article

An oscillation based simulated annealing algorithm for the single row facility layout problem

• Baiyu Chen
• Zhipeng Lü
• Zhouxing Su
• Junwen Ding

IJCAI Conference 2025 Conference Paper

NS4S: Neighborhood Search for Scheduling Problems Via Large Language Models

• Junjie Zhang
• Canhui Luo
• Zhouxing Su
• Qingyun Zhang
• Zhipeng Lü
• Junwen Ding
• Yan Jin

Large Language Models (LLMs) have emerged as a promising technology for solving combinatorial optimization problems. However, their direct application to scheduling problems remains limited due to the inherent complexity of these problems. This paper proposes an LLMs-based neighborhood search method that leverages LLMs to tackle the job shop scheduling problem (JSP) and its variants. The main contributions of this work are threefold. First, we introduce a novel LLMs-guided neighborhood evaluation strategy that guides local search by dynamically adjusting operation weights. Second, we develop a verification evolution (VeEvo) framework to mitigate the hallucination effects of LLMs, enabling the generation of high-quality heuristics for weight updates. Third, we integrate this framework with the weighted neighborhood evaluation strategy to effectively guide the search towards promising regions. Extensive experiments are conducted on 349 benchmark instances across three classical scheduling problems. The results demonstrate that our algorithm significantly outperforms existing state-of-the-art methods. For JSP, our algorithm reduces the average optimality gap from 10. 46% to 1. 35% on Taillard's instances compared to reinforced adaptive staircase curriculum learning. For flexible JSP (FJSP), it reduces the gap from 13. 24% to 0. 05% on Brandimarte's instances compared to deep reinforcement learning methods. Furthermore, for FJSP with sequence dependent setup time, our algorithm updates 9 upper bounds for benchmark instances.

IJCAI Conference 2024 Conference Paper

A Swap Relaxation-Based Local Search for the Latin Square Completion Problem

• Zhenxuan Xie
• Zhipeng Lü
• Zhouxing Su
• Chu-Min Li
• Junwen Ding
• Yuxuan Wang

The Latin square completion (LSC) problem aims to assign n symbols to the empty cells of a partially filled Latin square such that in each row and each column, each symbol appears exactly once. In this paper, we propose a swap relaxation-based fast local search algorithm called SRLS for solving the LSC problem. First, it introduces a novel search space definition, which forbids row conflicts based on which a swap-based neighborhood is defined. Second, a color domain relaxation technique is employed in the swap-based neighborhood by temporarily accepting the violation of some constraints to connect high-quality solutions. Third, two effective scoring functions are adopted to select neighborhood moves minimizing the number of conflicting edges as well as the number of color domain violations. Finally, SRLS employs an adaptive restart mechanism to balance the exploitation and exploration of the search. Extensive experiments on 1819 public benchmark instances demonstrate that SRLS outperforms the state-of-the-art algorithms in the literature in terms of both success rate and computational efficiency.

AAAI Conference 2019 Conference Paper

A Two-Individual Based Evolutionary Algorithm for the Flexible Job Shop Scheduling Problem

• Junwen Ding
• Zhipeng Lü
• Chu-Min Li
• Liji Shen
• Liping Xu
• Fred Glover

Population-based evolutionary algorithms usually manage a large number of individuals to maintain the diversity of the search, which is complex and time-consuming. In this paper, we propose an evolutionary algorithm using only two individuals, called master-apprentice evolutionary algorithm (MAE), for solving the flexible job shop scheduling problem (FJSP). To ensure the diversity and the quality of the evolution, MAE integrates a tabu search procedure, a recombination operator based on path relinking using a novel distance definition, and an effective individual updating strategy, taking into account the multiple complex constraints of FJSP. Experiments on 313 widely-used public instances show that MAE improves the previous best known results for 47 instances and matches the best known results on all except 3 of the remaining instances while consuming the same computational time as current state-of-the-art metaheuristics. MAE additionally establishes solution quality records for 10 hard instances whose previous best values were established by a well-known industrial solver and a state-of-the-art exact method.