Author name cluster

Yan Jin

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

19 papers

1 author row

EAAI Journal 2026 Journal Article

A doubly reinforced local search for solving the Quadratic Multiple Knapsack Problem

Yingsong Nie
Lingyan Zhang
Xiaolu Liu
Lei He
Tao Guan
Yan Jin

The Quadratic Multiple Knapsack Problem (QMKP) is a computationally challenging combinatorial optimization problem with important real-world applications in manufacturing and production planning. Traditional methods often struggle to effectively balance intensification and diversification, relying heavily on expert experience to guide the search process. To address these limitations, we propose a doubly reinforced local search algorithm (denoted as DRLS) that integrates two distinct reinforcement learning methods into a multi-neighborhood tabu search framework, each activated at different stages of the search process to improve adaptive decision-making. Specifically, a multi-armed bandit mechanism is incorporated into the neighborhood selection phase to dynamically select promising neighborhood operators in a stateless environments for effective search. In addition, a Q-learning model is employed in item removal phase to state-dependent remove items, enabling the search to escape from local optima. Evaluations on 720 benchmark instances across four datasets demonstrate that DRLS consistently outperforms six state-of-the-art algorithms in both solution quality and runtime efficiency. In particular, DRLS discovers new best-known solutions for over 50% of the instances, highlighting its effectiveness. Additional experiments are presented to gain insight into the role of the reinforcement learning components.

Details DOI

AAMAS Conference 2026 Conference Paper

LLMAide: Language-Assisted Neural Solver for Vehicle Routing Problems

Manuj Malik
Jianan Zhou
Yan Jin
Zhiguang Cao

We propose a novel approach to Vehicle Routing Problems (VRPs) that integrates the strengths of neural spatial embeddings with the semantic understanding of large language models (LLMs). While traditional neural methods excel in structured routing, they typically “feel” constraints through rigid mechanisms like feasibility masking, limiting their expressiveness. Conversely, LLMs demonstrate robust semantic capabilities but lack the spatial reasoning essential for precise routing optimization. To address these gaps, we introduce a hierarchical, multi-scale fusion architecture that integrates LLM-derived semantics with spatial routing features. Our contributions include: (1) a scale-aware decomposition aligning LLM features with spatial representations, (2) a bidirectional cross-modal attention module enabling interaction between linguistic and spatial domains, and (3) a progressive refinement pathway ensuring semantic and spatial fidelity. Through theoretical analysis, we prove the convergence properties of our fusion mechanism and its effectiveness in preserving critical information from both modalities. Evaluationsacross16VRPvariantsdemonstratecompetitive performance, highlighting the benefits of embedding semantic understanding into VRP optimization.

PDF

EAAI Journal 2025 Journal Article

An effective method for prospective scheduling of tasks in cloud-fog computing with an energy consumption management approach based on Q-learning

Yan Jin

The increasing energy consumption in cloud computing data centers has become a significant concern due to the expanding scale of computational demands. Efficient task scheduling is crucial to optimizing resource utilization while reducing operational costs and energy consumption. This study proposes a Multi-Agent Reinforcement Learning (MARL)-based scheduling framework that enhances system efficiency by dynamically allocating tasks based on environmental variations and workload fluctuations. Unlike conventional methods, MARL allows multiple intelligent agents to collaboratively optimize scheduling decisions, leading to superior adaptability and performance. The proposed approach consists of two steps: first, a centralized task dispatcher assigns incoming tasks to cloud servers using a queuing model. Second, an MARL-based scheduler on each server prioritizes and allocates tasks to virtual machines while continuously updating scheduling policies to maximize efficiency. The framework is evaluated using a CloudSim-based simulation environment to ensure a realistic and controlled assessment. Experimental results demonstrate that the proposed method reduces energy consumption by an average of 51. 34 %, improves CPU utilization efficiency, and decreases response time by 44. 35 % compared to traditional scheduling techniques, including First In-First Out (FIFO), Greedy, and Queue-based Scheduling (Q-sch). By leveraging MARL, the scheduler effectively minimizes waiting times and optimizes task completion rates, ensuring a balance between energy efficiency and system performance. This work highlights the advantages of reinforcement learning in cloud-fog computing and underscores its potential for intelligent resource management.

Details DOI

AAAI Conference 2025 Conference Paper

DualOpt: A Dual Divide-and-Optimize Algorithm for the Large-scale Traveling Salesman Problem

Shipei Zhou
Yuandong Ding
Chi Zhang
Zhiguang Cao
Yan Jin

This paper proposes a dual divide-and-optimize algorithm (DualOpt) for solving the large-scale traveling salesman problem (TSP). DualOpt combines two complementary strategies to improve both solution quality and computational efficiency. The first strategy is a grid-based divide-and-conquer procedure that partitions the TSP into smaller sub-problems, solving them in parallel and iteratively refining the solution by merging nodes and partial routes. The process continues until only one grid remains, yielding a high-quality initial solution. The second strategy involves a path-based divide-and-optimize procedure that further optimizes the solution by dividing it into sub-paths, optimizing each using a neural solver, and merging them back to progressively improve the overall solution. Extensive experiments conducted on two groups of TSP benchmark instances, including randomly generated instances with up to 100,000 nodes and real-world datasets from TSPLIB, demonstrate the effectiveness of DualOpt. The proposed DualOpt achieves highly competitive results compared to 10 state-of-the-art algorithms in the literature. In particular, DualOpt achieves an improvement gap up to 1.40% for the largest instance TSP100K with a remarkable 104x speed-up over the leading heuristic solver LKH3. Additionally, DualOpt demonstrates strong generalization on TSPLIB benchmarks, confirming its capability to tackle diverse real-world TSP applications.

PDF Details DOI

AIJ Journal 2025 Journal Article

Integrating multi-armed bandit with local search for MaxSAT

Jiongzhi Zheng
Kun He
Jianrong Zhou
Yan Jin
Chu-Min Li
Felip Manyà

Partial MaxSAT (PMS) and Weighted PMS (WPMS) are two practical generalizations of the MaxSAT problem. In this paper, we introduce a new local search algorithm for these problems, named BandHS. It applies two multi-armed bandit (MAB) models to guide the search directions when escaping local optima. One MAB model is combined with all the soft clauses to help the algorithm select to satisfy appropriate soft clauses, while the other MAB model is combined with all the literals in hard clauses to help the algorithm select suitable literals to satisfy the hard clauses. These two models enhance the algorithm's search ability in both feasible and infeasible solution spaces. BandHS also incorporates a novel initialization method that prioritizes both unit and binary clauses when generating the initial solutions. Moreover, we apply our MAB approach to the state-of-the-art local search algorithm NuWLS and to the local search component of the incomplete solver NuWLS-c-2023. The extensive experiments conducted demonstrate the excellent performance and generalization capability of the proposed method. Additionally, we provide analyses on the type of problems where our MAB method works well or not, aiming to offer insights and suggestions for its application. Encouragingly, our MAB method has been successfully applied in core local search components in the winner of the WPMS complete track of MaxSAT Evaluation 2023, as well as the runners-up of the incomplete track of MaxSAT Evaluations 2022 and 2023.

Details DOI

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.

PDF Details DOI

IJCAI Conference 2024 Conference Paper

Dynamically Anchored Prompting for Task-Imbalanced Continual Learning

Chenxing Hong
Yan Jin
Zhiqi Kang
Yizhou Chen
Mengke Li
Yang Lu
Hanzi Wang

Existing continual learning literature relies heavily on a strong assumption that tasks arrive with a balanced data stream, which is often unrealistic in real-world applications. In this work, we explore task-imbalanced continual learning (TICL) scenarios where the distribution of task data is non-uniform across the whole learning process. We find that imbalanced tasks significantly challenge the capability of models to control the trade-off between stability and plasticity from the perspective of recent prompt-based continual learning methods. On top of the above finding, we propose Dynamically Anchored Prompting (DAP), a prompt-based method that only maintains a single general prompt to adapt to the shifts within a task stream dynamically. This general prompt is regularized in the prompt space with two specifically designed prompt anchors, called boosting anchor and stabilizing anchor, to balance stability and plasticity in TICL. Remarkably, DAP achieves this balance by only storing a prompt across the data stream, therefore offering a substantial advantage in rehearsal-free CL. Extensive experiments demonstrate that the proposed DAP results in 4. 5% to 15% absolute improvements over state-of-the-art methods on benchmarks under task-imbalanced settings. Our code is available at https: //github. com/chenxing6666/DAP.

PDF Details DOI

IJCAI Conference 2024 Conference Paper

ReinforceNS: Reinforcement Learning-based Multi-start Neighborhood Search for Solving the Traveling Thief Problem

Tao Wu
Huachao Cui
Tao Guan
Yuesong Wang
Yan Jin

The Traveling Thief Problem (TTP) is a challenging combinatorial optimization problem with broad practical applications. TTP combines two NP-hard problems: the Traveling Salesman Problem (TSP) and Knapsack Problem (KP). While a number of machine learning and deep learning based algorithms have been developed for TSP and KP, there is limited research dedicated to TTP. In this paper, we present the first reinforcement learning based multi-start neighborhood search algorithm, denoted by ReinforceNS, for solving TTP. To accelerate the search, we employ a pre-processing procedure for neighborhood reduction. A TSP routing and an iterated greedy packing are independently utilized to construct a high-quality initial solution, further improved by a reinforcement learning based neighborhood search. Additionally, a post-optimization procedure is devised for continued solution improvement. We conduct extensive experiments on 60 commonly used benchmark instances with 76 to 33810 cities in the literature. The experimental results demonstrate that our proposed ReinforceNS algorithm outperforms three state-of-the-art algorithms in terms of solution quality with the same time limit. In particular, ReinforceNS achieves 12 new results for 18 instances publicly reported in a recent TTP competition. We also perform an additional experiment to validate the effectiveness of the reinforcement learning strategy.

PDF Details DOI

EAAI Journal 2024 Journal Article

Twin data multimode collaborative transfer learning for bearing failure diagnosis

Xiaofeng Liu
Yan Jin
Fan Yang
Yingying Kang
Lin Bo

To tackle the challenges of gathering and labeling data in practical engineering applications, a multimode collaborative transfer learning method is proposed to bridge the reality gap between labeled twin fault data and unlabeled real-world data. A bearing fault digital twin model is built to produce failure twin data of the test bearing under different health conditions. Three simulation source domains are constructed in accordance with the twin data's transferable modes. The iterative joint geometric-statistical alignment is used to perform the collaborative transfer of twin data's modes, which suppresses the negative transfer brought on by insufficient transferable information and the large inter-domain discrepancy. The fuzzy integral decision fusion is optimized and used to automatically label the real-world samples, which increases the cross-domain category alignment feasibility. The experimental results of extensive diagnosis tasks verified that the proposed method significantly outperforms the state-of-the-art domain adaption methods and can achieve an average classification accuracy of more than 91% in the bearing fault diagnosis with the support of fault twin data alone, without the supervision and guidance of historical labeling data.

Details DOI

AAAI Conference 2023 Conference Paper

H-TSP: Hierarchically Solving the Large-Scale Traveling Salesman Problem

Xuanhao Pan
Yan Jin
Yuandong Ding
Mingxiao Feng
Li Zhao
Lei Song
Jiang Bian

We propose an end-to-end learning framework based on hierarchical reinforcement learning, called H-TSP, for addressing the large-scale Traveling Salesman Problem (TSP). The proposed H-TSP constructs a solution of a TSP instance starting from the scratch relying on two components: the upper-level policy chooses a small subset of nodes (up to 200 in our experiment) from all nodes that are to be traversed, while the lower-level policy takes the chosen nodes as input and outputs a tour connecting them to the existing partial route (initially only containing the depot). After jointly training the upper-level and lower-level policies, our approach can directly generate solutions for the given TSP instances without relying on any time-consuming search procedures. To demonstrate effectiveness of the proposed approach, we have conducted extensive experiments on randomly generated TSP instances with different numbers of nodes. We show that H-TSP can achieve comparable results (gap 3.42% vs. 7.32%) as SOTA search-based approaches, and more importantly, we reduce the time consumption up to two orders of magnitude (3.32s vs. 395.85s). To the best of our knowledge, H-TSP is the first end-to-end deep reinforcement learning approach that can scale to TSP instances of up to 10000 nodes. Although there are still gaps to SOTA results with respect to solution quality, we believe that H-TSP will be useful for practical applications, particularly those that are time-sensitive e.g., on-call routing and ride hailing service.

PDF Details DOI

AAAI Conference 2023 Conference Paper

Pointerformer: Deep Reinforced Multi-Pointer Transformer for the Traveling Salesman Problem

Yan Jin
Yuandong Ding
Xuanhao Pan
Kun He
Li Zhao
Tao Qin
Lei Song
Jiang Bian

Traveling Salesman Problem (TSP), as a classic routing optimization problem originally arising in the domain of transportation and logistics, has become a critical task in broader domains, such as manufacturing and biology. Recently, Deep Reinforcement Learning (DRL) has been increasingly employed to solve TSP due to its high inference efficiency. Nevertheless, most of existing end-to-end DRL algorithms only perform well on small TSP instances and can hardly generalize to large scale because of the drastically soaring memory consumption and computation time along with the enlarging problem scale. In this paper, we propose a novel end-to-end DRL approach, referred to as Pointerformer, based on multi-pointer Transformer. Particularly, Pointerformer adopts both reversible residual network in the encoder and multi-pointer network in the decoder to effectively contain memory consumption of the encoder-decoder architecture. To further improve the performance of TSP solutions, Pointerformer employs a feature augmentation method to explore the symmetries of TSP at both training and inference stages as well as an enhanced context embedding approach to include more comprehensive context information in the query. Extensive experiments on a randomly generated benchmark and a public benchmark have shown that, while achieving comparative results on most small-scale TSP instances as state-of-the-art DRL approaches do, Pointerformer can also well generalize to large-scale TSPs.

PDF Details DOI

IJCAI Conference 2022 Conference Paper

BandMaxSAT: A Local Search MaxSAT Solver with Multi-armed Bandit

Jiongzhi Zheng
Kun He
Jianrong Zhou
Yan Jin
Chu-Min Li
Felip Manyà

We address Partial MaxSAT (PMS) and Weighted PMS (WPMS), two practical generalizations of the MaxSAT problem, and propose a local search algorithm called BandMaxSAT, that applies a multi-armed bandit to guide the search direction, for these problems. The bandit in our method is associated with all the soft clauses in the input (W)PMS instance. Each arm corresponds to a soft clause. The bandit model can help BandMaxSAT to select a good direction to escape from local optima by selecting a soft clause to be satisfied in the current step, that is, selecting an arm to be pulled. We further propose an initialization method for (W)PMS that prioritizes both unit and binary clauses when producing the initial solutions. Extensive experiments demonstrate that BandMaxSAT significantly outperforms the state-of-the-art (W)PMS local search algorithm SATLike3. 0. Specifically, the number of instances in which BandMaxSAT obtains better results is about twice that obtained by SATLike3. 0. We further combine BandMaxSAT with the complete solver TT-Open-WBO-Inc. The resulting solver BandMaxSAT-c also outperforms some of the best state-of-the-art complete (W)PMS solvers, including SATLike-c, Loandra and TT-Open-WBO-Inc.

PDF Details DOI

AAAI Conference 2021 Conference Paper

Combining Reinforcement Learning with Lin-Kernighan-Helsgaun Algorithm for the Traveling Salesman Problem

Jiongzhi Zheng
Kun He
Jianrong Zhou
Yan Jin
Chu-Min Li

We address the Traveling Salesman Problem (TSP), a famous NP-hard combinatorial optimization problem. And we propose a variable strategy reinforced approach, denoted as VSR-LKH, which combines three reinforcement learning methods (Q-learning, Sarsa and Monte Carlo) with the well-known TSP algorithm, called Lin-Kernighan-Helsgaun (LKH). VSR-LKH replaces the inflexible traversal operation in LKH, and lets the program learn to make choice at each search step by reinforcement learning. Experimental results on 111 TSP benchmarks from the TSPLIB with up to 85, 900 cities demonstrate the excellent performance of the proposed method.

PDF Details

AAAI Conference 2020 Conference Paper

Enumerating Maximal k -Plexes with Worst-Case Time Guarantee

Yi Zhou
Jingwei Xu
Zhenyu Guo
Mingyu Xiao
Yan Jin

The problem of enumerating all maximal cliques in a graph is a key primitive in a variety of real-world applications such as community detection and so on. However, in practice, communities are rarely formed as cliques due to data noise. Hence, k-plex, a subgraph in which any vertex is adjacent to all but at most k vertices, is introduced as a relaxation of clique. In this paper, we investigate the problem of enumerating all maximal k-plexes and present FaPlexen, an enumeration algorithm which integrates the “pivot” heuristic and new branching schemes. To our best knowledge, for the ﬁrst time, FaPlexen lists all maximal k-plexes with provably worst-case running time O(n2 γn ) in a graph with n vertices, where γ < 2. Then, we propose another algorithm CommuPlex which non-trivially extends FaPlexen to ﬁnd all maximal kplexes of prescribed size for community detection in massive real-life networks. We ﬁnally carry out experiments on both real and synthetic graphs and demonstrate that our algorithms run much faster than the state-of-the-art algorithms.

PDF Details

AAAI Conference 2018 Short Paper

Predicting Depression Severity by Multi-Modal Feature Engineering and Fusion

Aven Samareh
Yan Jin
Zhangyang Wang
Xiangyu Chang
Shuai Huang

We present our preliminary work to determine if patient’s vocal acoustic, linguistic, and facial patterns could predict clinical ratings of depression severity, namely Patient Health Questionnaire depression scale (PHQ-8). We proposed a multi-modal fusion model that combines three different modalities: audio, video, and text features. By training over the AVEC2017 dataset, our proposed model outperforms each single-modality prediction model, and surpasses the dataset baseline with a nice margin.

PDF Details

EAAI Journal 2015 Journal Article

General swap-based multiple neighborhood tabu search for the maximum independent set problem

Yan Jin
Jin-Kao Hao

Given a graph G = ( V, E ), the Maximum Independent Set problem (MIS) aims to determine a subset S ⊆ V of maximum cardinality such that no two vertices of S are adjacent. This paper presents a general Swap-Based Tabu Search (SBTS) for solving the MIS. SBTS integrates distinguished features including a general and unified (k, 1)-swap operator, four constrained neighborhoods and specific rules for neighborhood exploration. Extensive evaluations on two popular benchmarks (DIMACS and BHOSLIB) of 120 instances show that SBTS attains the best-known results for all the instances. To our knowledge, such a performance was not reported in the literature for a single heuristic. The best-known results on 11 additional instances from code theory are also attained.

Details DOI

YNICL Journal 2015 Journal Article

White matter disruption in moderate/severe pediatric traumatic brain injury: Advanced tract-based analyses

Emily L. Dennis
Yan Jin
Julio E. Villalon-Reina
Liang Zhan
Claudia L. Kernan
Talin Babikian
Richard B. Mink
Christopher J. Babbitt

Traumatic brain injury (TBI) is the leading cause of death and disability in children and can lead to a wide range of impairments. Brain imaging methods such as DTI (diffusion tensor imaging) are uniquely sensitive to the white matter (WM) damage that is common in TBI. However, higher-level analyses using tractography are complicated by the damage and decreased FA (fractional anisotropy) characteristic of TBI, which can result in premature tract endings. We used the newly developed autoMATE (automated multi-atlas tract extraction) method to identify differences in WM integrity. 63 pediatric patients aged 8-19 years with moderate/severe TBI were examined with cross sectional scanning at one or two time points after injury: a post-acute assessment 1-5 months post-injury and a chronic assessment 13-19 months post-injury. A battery of cognitive function tests was performed in the same time periods. 56 children were examined in the first phase, 28 TBI patients and 28 healthy controls. In the second phase 34 children were studied, 17 TBI patients and 17 controls (27 participants completed both post-acute and chronic phases). We did not find any significant group differences in the post-acute phase. Chronically, we found extensive group differences, mainly for mean and radial diffusivity (MD and RD). In the chronic phase, we found higher MD and RD across a wide range of WM. Additionally, we found correlations between these WM integrity measures and cognitive deficits. This suggests a distributed pattern of WM disruption that continues over the first year following a TBI in children.

Details DOI

YNIMG Journal 2014 Journal Article

Automatic clustering of white matter fibers in brain diffusion MRI with an application to genetics

Yan Jin
Yonggang Shi
Liang Zhan
Boris A. Gutman
Greig I. de Zubicaray
Katie L. McMahon
Margaret J. Wright
Arthur W. Toga

To understand factors that affect brain connectivity and integrity, it is beneficial to automatically cluster white matter (WM) fibers into anatomically recognizable tracts. Whole brain tractography, based on diffusion-weighted MRI, generates vast sets of fibers throughout the brain; clustering them into consistent and recognizable bundles can be difficult as there are wide individual variations in the trajectory and shape of WM pathways. Here we introduce a novel automated tract clustering algorithm based on label fusion – a concept from traditional intensity-based segmentation. Streamline tractography generates many incorrect fibers, so our top-down approach extracts tracts consistent with known anatomy, by mapping multiple hand-labeled atlases into a new dataset. We fuse clustering results from different atlases, using a mean distance fusion scheme. We reliably extracted the major tracts from 105-gradient high angular resolution diffusion images (HARDI) of 198 young normal twins. To compute population statistics, we use a pointwise correspondence method to match, compare, and average WM tracts across subjects. We illustrate our method in a genetic study of white matter tract heritability in twins.

Details DOI

KER Journal 1998 Journal Article

The Process Interchange Format and Framework

Jintae Lee
Michael Gruninger
Yan Jin
Thomas Malone
Austin Tate
GREGG YOST
OTHER MEMBERS OF THE PIF WORKING GROUP

This document provides the specification of the Process Interchange Format (PIF) version 1.2. The goal of this work is to develop an interchange format to help automatically exchange process descriptions among a wide variety of business process modelling and support systems such as workflow software, flow charting tools, planners, process simulation systems and process repositories. Instead of having to write ad hoc translators for each pair of such systems each system will only need to have a single translator for converting process descriptions in that system into and out of the common PIF format. Then any system will be able to automatically exchange basic process descriptions with any other system. This document describes the PIF-CORE 1.2, i.e. the core set of object types (such as activities, agents and prerequisite relations) that can be used to describe the basic elements of any process. The document also describes a framework for extending the core set of object types to include additional information needed in specific applications. These extended descriptions are exchanged in such a way that the common elements are interpretable by any PIF translator, and the additional elements are interpretable by any translator that knows about the extensions. The PIF format was developed by a working group including representatives from several universities and companies, and has been used for experimental automatic translations among systems developed independently at three of these sites. This document is being distributed in the hopes that other groups will comment upon the interchange format proposed here, and that this format (or future versions of it) may be useful to other groups as well. The PIF Document 1.0 was released in December 1994, and the current document reports the revised PIF that incorporate the feedback received since then.

Details DOI