Zhouxing Su

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 2024 Conference Paper

Threshold-Based Responsive Simulated Annealing for Directed Feedback Vertex Set Problem

• Qingyun Zhang
• Yuming Du
• Zhouxing Su
• Chu-Min Li
• Junzhou Xu
• Zhihuai Chen
• Zhipeng Lü

As a classical NP-hard problem and the topic of the PACE 2022 competition, the directed feedback vertex set problem (DFVSP) aims to find a minimum subset of vertices such that, when vertices in the subset and all their adjacent edges are removed from the directed graph, the remainder graph is acyclic. In this paper, we propose a threshold-based responsive simulated annealing algorithm called TRSA for solving DFVSP. First, we simplify the problem instances with two new reduction rules proposed in this paper and eight reduction rules from the literature. Then, based on a new solution representation, TRSA solves DFVSP with a fast local search procedure featured by a swap-based neighborhood structure and three neighborhood acceleration strategies. Finally, all these strategies are incorporated into a threshold-based responsive simulated annealing framework. Computational experiments on 140 benchmark instances show that TRSA is highly competitive compared to the state-of-the-art methods. Specifically, TRSA can improve the best known results for 53 instances, while matching the best known results for 79 ones. Furthermore, some important features of TRSA are analyzed to identify its success factors.

IJCAI Conference 2022 Conference Paper

A Weighting-Based Tabu Search Algorithm for the p-Next Center Problem

• Qingyun Zhang
• Zhouxing Su
• Zhipeng Lü
• Lingxiao Yang

The p-next center problem (pNCP) is an extension of the classical p-center problem. It consists of locating p centers from a set of candidate centers and allocating both a reference and a backup center to each client, to minimize the maximum cost, which is the length of the path from a client to its reference center and then to its backup center. Among them, the reference center is the closest center to a client and serves it under normal circumstances, while the backup center is the closest center to the reference center and serves the client when the reference center is out of service. In this paper, we propose a weighting-based tabu search algorithm called WTS for solving pNCP. WTS optimizes the pNCP by solving its decision subproblems with given assignment costs with an efficient swap-based neighborhood structure and a hierarchical penalty strategy for neighborhood evaluation. Extensive experimental studies on 413 benchmark instances demonstrate that WTS outperforms the state-of-the-art methods in the literature. Specifically, WTS improves 12 previous best known results and matches the optimal results for all remaining 401 ones in a much shorter time than other algorithms. More importantly, WTS reaches the lower bounds for 10 instances for the first time.

AAAI Conference 2021 Conference Paper

Weighting-based Variable Neighborhood Search for Optimal Camera Placement

• Zhouxing Su
• Qingyun Zhang
• Zhipeng Lü
• Chu-Min Li
• Weibo Lin
• Fuda Ma

The optimal camera placement problem (OCP) aims to accomplish surveillance tasks with the minimum number of cameras, which is one of the topics in the GECCO 2020 Competition and can be modeled as the unicost set covering problem (USCP). This paper presents a weighting-based variable neighborhood search (WVNS) algorithm for solving OCP. First, it simplifies the problem instances with four reduction rules based on dominance and independence. Then, WVNS converts the simplified OCP into a series of decision unicost set covering subproblems and tackles them with a fast local search procedure featured by a swap-based neighborhood structure. WVNS employs an efficient incremental evaluation technique and further boosts the neighborhood evaluation by exploiting the dominance and independence features among neighborhood moves. Computational experiments on the 69 benchmark instances introduced in the GECCO 2020 Competition on OCP and USCP show that WVNS is extremely competitive comparing to the state-of-the-art methods. It outperforms or matches several best performing competitors on all instances in both the OCP and USCP tracks of the competition, and its advantage on 15 large-scale instances are over 10%. In addition, WVNS improves the previous best known results for 12 classical benchmark instances in the literature.

IJCAI Conference 2020 Conference Paper

A Two-Stage Matheuristic Algorithm for Classical Inventory Routing Problem

• Zhouxing Su
• Shihao Huang
• Chungen Li
• Zhipeng Lü

The inventory routing problem (IRP), which is NP-hard, tackles the combination of inventory management and transportation optimization in supply chains. It seeks a minimum-cost schedule which utilizes a single vehicle to perform deliveries in multiple periods, so that no customer runs out of stock. Specifically, the solution of IRP can be represented as how many products should be delivered to which customer during each period, as well as the route in each period. We propose a two-stage matheuristic (TSMH) algorithm to solve the IRP. The first stage optimizes the overall schedule and generates an initial solution by a relax-and-repair method. The second stage employs an iterated tabu search procedure to achieve a fine-grained optimization to the current solution. Tested on 220 most commonly used benchmark instances, TSMH obtains advantages comparing to the state-of-the-art algorithms. The experimental results show that the proposed algorithm can obtain not only the optimal solutions for most small instances, but also better upper bounds for 40 out of 60 large instances. These results demonstrate that the TSMH algorithm is effective and efficient in solving the IRP. In addition, the comparative experiments justify the importance of two optimization stages of TSMH.

IJCAI Conference 2020 Conference Paper

Vertex Weighting-Based Tabu Search for p-Center Problem

• Qingyun Zhang
• Zhipeng Lü
• Zhouxing Su
• Chumin Li
• Yuan Fang
• Fuda Ma

The p-center problem consists of choosing p centers from a set of candidates to minimize the maximum cost between any client and its assigned facility. In this paper, we transform the p-center problem into a series of set covering subproblems, and propose a vertex weighting-based tabu search (VWTS) algorithm to solve them. The proposed VWTS algorithm integrates distinguishing features such as a vertex weighting technique and a tabu search strategy to help the search to jump out of the local optima. Computational experiments on 138 most commonly used benchmark instances show that VWTS is highly competitive comparing to the state-of-the-art methods in spite of its simplicity. As a well-known NP-hard problem which has already been studied for over half a century, it is a challenging task to break the records on these classic datasets. Yet VWTS improves the best known results for 14 out of 54 large instances, and matches the optimal results for all remaining 84 ones. In addition, the computational time taken by VWTS is much shorter than other algorithms in the literature.