Li Zhao

Yan Jin, Yuandong Ding, Xuanhao Pan et al.

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 both 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 SOTA DRL approaches do, Pointerformer can also well generalize to large-scale TSPs.

Xuanhao Pan, Yan Jin, Yuandong Ding et al.

We propose an end-to-end learning framework based on hierarchical reinforcement learning, called H-TSP, for addressing the large-scale Travelling 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.

Shizhe Li, Li Zhao, Chen-Song Zhang

The numerical simulation of large-scale multiphase flow in porous media is of considerable importance across various application fields, particularly in the petroleum industry. The fully implicit method is preferred in reservoir simulations owing to its superior numerical stability and more relaxed time step constraints. However, this method requires solving a large nonlinear system, which becomes highly nonlinear in complex heterogeneous media with small grid scales, emphasizing the need for efficient and convergent numerical methods to accelerate nonlinear solvers on parallel computing systems. In this paper, we present an adaptively coupled subdomain framework based on domain decomposition methods. This framework effectively handles strong local nonlinearities in global problems by solving subproblems within the coupled regions. Furthermore, we propose several adaptive coupling strategies and present a novel method for calculating initial guesses, aimed at improving the convergence and scalability of nonlinear solvers. A series of numerical experiments validate the effectiveness and robustness of the proposed framework. Additionally, large-scale reservoir simulations demonstrate that the proposed method achieves competitive parallel performance.