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.

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.

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.

The Vertex Bisection Minimization Problem (VBMP) is a relevant graph partitioning model with a variety of practical applications. This work introduces a clustering driven iterated hybrid search algorithm (CLUHS), which is the first approach that applies clustering to reinforce iterated local search for solving VBMP. The proposed CLUHS uses hierarchical clustering to build an initial solution, guide local search process and perform search diversification. Experimental studies on 137 benchmark instances show the high competitiveness of the proposed approach compared to the state-of-the-art methods. In particular, CLUHS finds new record-breaking solutions for 18 instances.

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.

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 first 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 find all maximal k-plexes of prescribed size for community detection in massive real-life networks. We finally carry out experiments on both real and synthetic graphs and demonstrate that our algorithms run much faster than the state-of-the-art algorithms.

This paper addresses a new orthogonal packing and time scheduling problem-3D space-time optimization problem (3D-STO). Given a rectangular sheet and a set of rectangular items, each item needs to be continuously processed with a time length on the sheet, the 3D-STO consists in arranging each item's loading time, location, and orientation for a certain period such that the total utilization time of the sheet, i.e., the makespan of the schedule, is minimized. The 3D-STO involves a series of 2D rectangular packing problem (2D-RPP) for the whole scheduling period. If the processing time of each item is simply regarded as a space dimension for the packing, then the 3D-STO can be reduced to an NP-hard packing problem-3D strip packing problem (3D-SPP). The 3D-STO differs from the 3D-SPP in that the position and orientation of items can be changed over the processing time (the third dimension) such that the 3D-STO has a much larger search space compared with the 3D-SPP. Hereby, the optimal solution of the 3D-STO is better than or equal to the optimal solution of the 3D-SPP, and a possibly better solution could be found for the 3D-STO model. As a new model, there is no algorithm or benchmark in the literature. Moreover, the 2D-RPP and 3D-SPP algorithms are not suitable for solving the 3D-STO which considers the packing and scheduling simultaneously. Hereby, we propose a caving-degree-based scheduling algorithm (CDS) for the 3D-STO. This is the first proposed 3DSTO algorithm. We also formalize the problem as a mixed integer programming model and solve it by ILOG CPLEX. For evaluation, we provide a synthesized method to generate a total of 195 various benchmark instances with guillotine and nonguillotine cut constraints. The comparative results show that CDS is more effective than the CPLEX solver for the 3D-STO. Also, when comparing CDS for the 3D-STO and the adapted CDS for the 3D-SPP, we see that the new 3D-STO model can enhance the flexibility of the item arrangement and make maximum utilization of the sheet and time.

The Latin square completion (LSC) problem involves completing a partially filled Latin square of order n by assigning numbers from 1 to n to the empty grids such that each number occurs exactly once in each row and each column. LSC has numerous applications and is, however, NP-complete. In this paper, we investigate an approach for solving LSC by converting an LSC instance to a domain-constrained Latin square graph and then solving the associated list coloring problem. To be effective, we first employ a constraint propagation-based kernelization technique to reduce the graph model and then call for a dedicated memetic algorithm to find a legal list coloring. The population-based memetic algorithm combines a problem-specific crossover operator to generate meaningful offspring solutions, an iterated tabu search procedure to improve the offspring solutions, and a distance-quality-based pool updating strategy to maintain a healthy diversity of the population. Extensive experiments on more than 1800 LSC benchmark instances in the literature show that the proposed approach can successfully solve all the instances, surpassing the state-of-the-art methods. To our knowledge, this is the first approach achieving such a performance for the considered problem. We also report computational results for the related partial Latin square extension problem.

The bandwidth coloring problem (BCP) and the bandwidth multicoloring problem (BMCP) are two important generalizations of the classical vertex coloring problem. This paper presents learning-based hybrid search (LHS) for BCP and BMCP. LHS combines a construction phase to progressively build feasible (partial) colorings and a local search phase to reestablish feasibility when an illegal partial solution is encountered. The construction phase relies on a learning-based guiding function to determine the next vertex for color assignment while the local search phase uses a tabu search repair procedure to resolve coloring conflicts. Experiments on a set of 33 well-known benchmarks for BCP and a set of 33 benchmarks for BMCP demonstrate that the proposed LHS approach can match the best known solution for most benchmarks. In particular, LHS finds an improved best solution for 14 instances.