Zhipeng Lü

Junwen Ding, Liangcai Song, Siyuan Li et al.

Computing workflows in heterogeneous multiprocessor systems are frequently modeled as directed acyclic graphs of tasks and data blocks, which represent computational modules and their dependencies in the form of data produced by a task and used by others. However, for some workflows, such as the task schedule in a digital signal processor may run out of memory by exposing too much parallelism. This paper focuses on the data allocation and task scheduling problem under memory constraints, and concentrates on shared memory platforms. We first propose an integer linear programming model to formulate the problem. Then we consider the problem as an extended flexible job shop scheduling problem, while trying to minimize the critical path of the graph. To solve this problem, we propose a tabu search algorithm (TS) which combines several distinguished features such as a greedy initial solution construction method and a mixed neighborhood evaluation strategy based on exact evaluation and approximate evaluation methods. Experimental results on randomly generated instances show that the the proposed TS algorithm can obtain relatively high-quality solutions in a reasonable computational time. In specific, the tabu search method averagely improves the makespan by 5-25\% compared to the classical load balancing algorithm that are widely used in the literature. Besides, some key features of TS are also analyzed to identify its success factors.

Zhengyang Lu, Bingjie Lu, Weifan Wang et al.

Fabric defect detection confronts two fundamental challenges. First, conventional non-maximum suppression disrupts gradient flow, which hinders genuine end-to-end learning. Second, acquiring pixel-level annotations at industrial scale is prohibitively costly. Addressing these limitations, we propose a differentiable NMS framework for fabric defect detection that achieves superior localization precision through end-to-end optimization. We reformulate NMS as a differentiable bipartite matching problem solved through the Sinkhorn-Knopp algorithm, maintaining uninterrupted gradient flow throughout the network. This approach specifically targets the irregular morphologies and ambiguous boundaries of fabric defects by integrating proposal quality, feature similarity, and spatial relationships. Our entropy-constrained mask refinement mechanism further enhances localization precision through principled uncertainty modeling. Extensive experiments on the Tianchi fabric defect dataset demonstrate significant performance improvements over existing methods while maintaining real-time speeds suitable for industrial deployment. The framework exhibits remarkable adaptability across different architectures and generalizes effectively to general object detection tasks.

Zuxing Lu, Xin Yuan, Shaowen Yang et al.

Semantic-aware 3D scene reconstruction is essential for autonomous robots to perform complex interactions. Semantic SLAM, an online approach, integrates pose tracking, geometric reconstruction, and semantic mapping into a unified framework, shows significant potential. However, existing systems, which rely on 2D ground truth priors for supervision, are often limited by the sparsity and noise of these signals in real-world environments. To address this challenge, we propose GSFF-SLAM, a novel dense semantic SLAM system based on 3D Gaussian Splatting that leverages feature fields to achieve joint rendering of appearance, geometry, and N-dimensional semantic features. By independently optimizing feature gradients, our method supports semantic reconstruction using various forms of 2D priors, particularly sparse and noisy signals. Experimental results demonstrate that our approach outperforms previous methods in both tracking accuracy and photorealistic rendering quality. When utilizing 2D ground truth priors, GSFF-SLAM achieves state-of-the-art semantic segmentation performance with 95.03\% mIoU, while achieving up to 2.9$\times$ speedup with only marginal performance degradation.

Mao Luo, Chu-Min Li, Xinyun Wu et al.

The two most effective branching strategies LRB and VSIDS perform differently on different types of instances. Generally, LRB is more effective on crafted instances, while VSIDS is more effective on application ones. However, distinguishing the types of instances is difficult. To overcome this drawback, we propose a branching strategy selection approach based on the vivification ratio. This approach uses the LRB branching strategy more to solve the instances with a very low vivification ratio. We tested the instances from the main track of SAT competitions in recent years. The results show that the proposed approach is robust and it significantly increases the number of solved instances. It is worth mentioning that, with the help of our approach, the solver Maple\_CM can solve more than 16 instances for the benchmark from the 2020 SAT competition.

Chu-Min Li, Fan Xiao, Mao Luo et al.

Original and learnt clauses in Conflict-Driven Clause Learning (CDCL) SAT solvers often contain redundant literals. This may have a negative impact on performance because redundant literals may deteriorate both the effectiveness of Boolean constraint propagation and the quality of subsequent learnt clauses. To overcome this drawback, we propose a clause vivification approach that eliminates redundant literals by applying unit propagation. The proposed clause vivification is activated before the SAT solver triggers some selected restarts, and only affects a subset of original and learnt clauses, which are considered to be more relevant according to metrics like the literal block distance (LBD). Moreover, we conducted an empirical investigation with instances coming from the hard combinatorial and application categories of recent SAT competitions. The results show that a remarkable number of additional instances are solved when the proposed approach is incorporated into five of the best performing CDCL SAT solvers (Glucose, TC_Glucose, COMiniSatPS, MapleCOMSPS and MapleCOMSPS_LRB). More importantly, the empirical investigation includes an in-depth analysis of the effectiveness of clause vivification. It is worth mentioning that one of the SAT solvers described here was ranked first in the main track of SAT Competition 2017 thanks to the incorporation of the proposed clause vivification. That solver was further improved in this paper and won the bronze medal in the main track of SAT Competition 2018.

Tao Ye, Kan Zhou, Zhipeng Lu et al.

This paper introduces an effective memetic algorithm for the linear ordering problem with cumulative costs. The proposed algorithm combines an order-based recombination operator with an improved forward-backward local search procedure and employs a solution quality based replacement criterion for pool updating. Extensive experiments on 118 well-known benchmark instances show that the proposed algorithm achieves competitive results by identifying 46 new upper bounds. Furthermore, some critical ingredients of our algorithm are analyzed to understand the source of its performance.

Tao Ye, Tao Wang, Zhipeng Lu et al.

In this paper, we present a multi-parent memetic algorithm (denoted by MPM) for solving the classic Linear Ordering Problem (LOP). The MPM algorithm integrates in particular a multi-parent recombination operator for generating offspring solutions and a distance-and-quality based criterion for pool updating. Our MPM algorithm is assessed on 8 sets of 484 widely used LOP instances and compared with several state-of-the-art algorithms in the literature, showing the efficacy of the MPM algorithm. Specifically, for the 255 instances whose optimal solutions are unknown, the MPM is able to detect better solutions than the previous best-known ones for 66 instances, while matching the previous best-known results for 163 instances. Furthermore, some additional experiments are carried out to analyze the key elements and important parameters of MPM.

Tao Ye, Wenqi Huang, Zhipeng Lu

This paper presents an Iterated Tabu Search algorithm (denoted by ITS-PUCC) for solving the problem of Packing Unequal Circles in a Circle. The algorithm exploits the continuous and combinatorial nature of the unequal circles packing problem. It uses a continuous local optimization method to generate locally optimal packings. Meanwhile, it builds a neighborhood structure on the set of local minimum via two appropriate perturbation moves and integrates two combinatorial optimization methods, Tabu Search and Iterated Local Search, to systematically search for good local minima. Computational experiments on two sets of widely-used test instances prove its effectiveness and efficiency. For the first set of 46 instances coming from the famous circle packing contest and the second set of 24 instances widely used in the literature, the algorithm is able to discover respectively 14 and 16 better solutions than the previous best-known records.