The submodular knapsack problem (SKP), which seeks to maximize a submodular set function by selecting a subset of elements within a given budget, is an important discrete optimization problem. The majority of existing approaches to solving the SKP are approximation algorithms. However, in domains such as health-care facility location and risk management, the need for optimal solutions is still critical, necessitating the use of exact algorithms over approximation methods. In this paper, we present an optimal branch-and-bound approach, featuring a novel upper bound with a worst-case tightness guarantee and an efficient dual branching method to minimize repeated computations. Experiments in applications such as facility location, weighted coverage, influence maximization, and so on show that the algorithms that implement the new ideas are far more efficient than conventional methods.

Detecting critical nodes in sparse graphs is important in a variety of application domains, such as network vulnerability assessment, epidemic control, and drug design. The critical node problem (CNP) aims to find a set of critical nodes from a network whose deletion maximally degrades the pairwise connectivity of the residual network. Due to its general NP-hard nature, state-of-the-art CNP solutions are based on heuristic approaches. Domain knowledge and trial-and-error are usually required when designing such approaches, thus consuming considerable effort and time. This work proposes a feature importance-aware graph attention network for node representation and combines it with dueling double deep Q-network to create an end-to-end algorithm to solve CNP for the first time. It does not need any problem-specific knowledge or labeled datasets as required by most of existing methods. Once the model is trained, it can be generalized to cope with various types of CNPs (with different sizes and topological structures) without re-training. Computational experiments on 28 real-world networks show that the proposed method is highly comparable to state-of-the-art methods. It does not require any problem-specific knowledge and, hence, can be applicable to many applications including those impossible ones by using the existing approaches. It can be combined with some local search methods to further improve its solution quality. Extensive comparison results are given to show its effectiveness in solving CNP.Note to Practitioners—This work is motivated by the problems of identifying influential nodes from a sparse graph or network. Various practical applications can be naturally modeled as critical node problems, e.g., finding the most influential stations or airports within a transportation network, identifying a specific number of people to be vaccinated in order to reduce the overall transmissibility of a virus, and reinforcing the protection over some most important nodes to make the electric network more stable. It proposes an effective end-to-end deep learning algorithm to solve the critical node problem. The proposed approach combines feature importance-aware graph attention network with dueling double deep Q-network. Extensive numerical experiments and comparisons show that our proposed algorithm is highly comparable to state-of-the-art algorithms and can help decision-makers to discover valuable knowledge or influential nodes in a real-world network.

A bottleneck-minimized colored traveling salesman problem is an important variant of colored traveling salesman problems. It is useful in handling the planning problems with partially overlapped workspace such as the scheduling transportation resources for timely delivery of goods. In this work, we propose an efficient bi-trajectory hybrid search method for it. The proposed method integrates a route-based crossover operator to generate promising offspring solutions, a multi-neighborhood simulated annealing to perform local optimization, and a stagnation-detect-escape mechanism to help the search escape from local optima. We also propose a bidirectional adjacency solution representation method to encode a solution, which extends the traditional adjacency representation method by additionally employing an array to represent its reverse counterpart. Extensive evaluations on two sets of 58 widely used benchmark instances demonstrate that the proposed method significantly outperforms state-of-the-art algorithms. Investigations on key algorithm modules are performed to confirm the novelty and effectiveness of the proposed ideas and strategies. Finally, we verify the generalization of the proposed method via its use to solve a colored traveling salesman problem with its aim to balance workload among salesmen. Note to Practitioners—This work is motivated by the problems of scheduling transportation resources for timely delivery of goods. It proposes an effective bi-trajectory hybrid search to tackle bottleneck-minimized colored traveling salesman problem. The proposed approach performs bi-trajectory hybrid evolutionary search by maintaining only two individuals during the whole search process. Extensive numerical experiments and comparisons show that our proposed algorithm significantly outperforms state-of-the-art algorithms and can help decision-makers in designing best-routing solutions.

Fliggy of Alibaba group is one of the largest online travel platform (OTPs) in China, which provides travel products and travel experiences for tens of millions of online users by the personalized recommendation system (RS). User's future travel intent prediction is one key problem in travel scenario, which decides where and what to recommend, e.g., traveling to a surrounding city or a distant city. Such travel intent prediction problem has a lot of important applications, e.g., to push a notification with surrounding scenic spots recommendation to a user with intent to travel around, or to enable personalized promotion strategies to users with different intents. Existing studies on user's intent are largely sub-optimal for users' travel intent prediction at OTPs, since they rarely pay attentions to the characteristics of the travel industry, namely, user behavior sparsity due to low frequency of travel, spatial-temporal periodicity patterns, and the correlations between user's online and offline behaviors. In this paper, to address these challenges, we propose a dual channel intent evolution network based online-offline periodicity-aware network, DCIEN, for user's future travel intent prediction. In particular, it consists of two basic components including 1) Spatial-temporal Intent Patterns Network(ST-IPN), which exploits users' periodic intent patterns from offline data based on convolutional neural networks; 2) Periodicity-aware Intent Evolution Network(PA-IEN), which captures user's instant intent from online behaviors data and the interactions between online and offline intents. Extensive offline and online experiments on a real-world OTP demonstrate the superior performance of DCIEN over state-of-the-art methods.

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.

A coloring traveling salesman problem (CTSP) generalizes the well-known multiple traveling salesman problem, where colors are used to differentiate salesmen’s the accessibility to individual cities to be visited. As a useful model for a variety of complex scheduling problems, CTSP is computationally challenging. In this paper, we propose a Multi-neighborhood Simulated Annealing-based Iterated Local Search (MSAILS) to solve it. Starting from an initial solution, it iterates through three sequential search procedures: a multi-neighborhood simulated annealing search to find a local optimum, a local search-enhanced edge assembly crossover to find nearby high-quality solutions around a local optimum, and a solution reconstruction procedure to move away from the current search region. Experimental results on two groups of 45 medium and large benchmark instances show that it significantly outperforms state-of-the-art algorithms. In particular, it is able to discover new upper bounds for 29 instances while matching 8 previous best-known upper bounds. Hence, this work greatly advances the field of CTSP.

Recently, a variety of regularization techniques have been widely applied in deep neural networks, which mainly focus on the regularization of weight parameters to encourage generalization effectively. Label regularization techniques are also proposed with the motivation of softening the labels while neglecting the relation of classes. Among them, the technique of knowledge distillation proposes to distill the soft label, which contains the knowledge of class relations. However, this technique needs to pre-train an extra cumbersome teacher model. In this paper, we propose a method called Knowledge Refinery (KR), which enables the neural network to learn the relation of classes on-the-fly without the teacher-student training strategy. We propose the definition of decoupled labels, which consist of the original hard label and the residual label. To exhibit the generalization of KR, we evaluate our method in both fields of computer vision and natural language processing. Our empirical results show consistent performance gains under all experimental settings.

For the traveling salesman problem (TSP), the existing supervised learning based algorithms suffer seriously from the lack of generalization ability. To overcome this drawback, this paper tries to train (in supervised manner) a small-scale model, which could be repetitively used to build heat maps for TSP instances of arbitrarily large size, based on a series of techniques such as graph sampling, graph converting and heat maps merging. Furthermore, the heat maps are fed into a reinforcement learning approach (Monte Carlo tree search), to guide the search of high-quality solutions. Experimental results based on a large number of instances (with up to 10,000 vertices) show that, this new approach clearly outperforms the existing machine learning based TSP algorithms, and significantly improves the generalization ability of the trained model.

In a graph, a k-plex is a vertex set in which every vertex is not adjacent to at most k vertices of this set. The maximum k-plex problem, which asks for the largest k-plex from the given graph, is a key primitive in a variety of real-world applications like community detection and so on. In the paper, we develop an exact algorithm, Maplex, for solving this problem in real world graphs practically. Based on the existing first-order and the novel second-order reduction rules, we design a powerful preprocessing method which efficiently removes redundant vertices and edges for Maplex. Also, the graph color heuristic is widely used for overestimating the maximum clique of a graph. For the first time, we generalize this technique for bounding the size of maximum k-plex in Maplex. Experiments are carried out to compare our algorithm with other state-of-the-art solvers on a wide range of publicly available graphs. Maplex outperforms all other algorithms on large real world graphs and is competitive with existing solvers on artificial dense graphs. Finally, we shed light on the effectiveness of each key component of Maplex.

Self-assembly has attracted growing interests in modular robotics during past decades. Recent work accelerates the assembly process by parallelizing the docking actions among robots. However, these methods can only apply to ideal environments without obstacles. Otherwise, robots will get trapped during the assembly process, due to the complex scenes with obstacles. This paper presents an efficient parallel assembly planning algorithm for modular robots by taking the surrounding obstacles into consideration. By this algorithm, the docking actions are able to avoid immovable obstacles, and therefore parallel self-assembly of robots can adapt to complex environments. To validate the efficacy and generality, the authors have implemented this algorithm in a grid-world simulation environment with 25 distinct maps. The simulation results show a much higher success rate (more than 80%) of our proposed algorithm compared with the existing parallel self-assembly planning algorithms. Finally, the feasibility of the algorithm is affirmed by a self-assembly experiment on the automated guided vehicles (AGVs).

Given an undirected graph, the Maximum k-plex Problem (MKP) is to find a largest induced subgraph in which each vertex has at most k−1 non-adjacent vertices. The problem arises in social network analysis and has found applications in many important areas employing graph-based data mining. Existing exact algorithms usually implement a branch-and-bound approach that requires a tight upper bound to reduce the search space. In this paper, we propose a new upper bound for MKP, which is a partitioning of the candidate vertex set with respect to the constructing solution. We implement a new branch-and-bound algorithm that employs the upper bound to reduce the number of branches. Experimental results show that the upper bound is very effective in reducing the search space. The new algorithm outperforms the state-of-the-art algorithms significantly on real-world massive graphs, DIMACS graphs and random graphs.

Population-based memetic algorithms have been successfully applied to solve many difficult combinatorial problems. Often, a population of fixed size is used in such algorithms to record some best solutions sampled during the search. However, given the particular features of the problem instance under consideration, a population of variable size would be more suitable to ensure the best search performance possible. In this work, we propose a variable population memetic search (VPMS), where a strategic population sizing mechanism is used to dynamically adjust the population size during the search process. Our VPMS approach starts its search from a small population of only two solutions to focus on exploitation and then adapts the population size according to the search status to continuously influence the balancing between exploitation and exploration. We illustrate an application of the VPMS approach to solve the challenging critical node problem (CNP). We show that the VPMS algorithm integrating a variable population, an effective local optimization procedure, and a backbone-based crossover operator performs very well compared to state-of-the-art CNP algorithms. The algorithm is able to discover new upper bounds for 12 instances out of the 42 popular benchmark instances while matching 23 previous best-known upper bounds.

Constructing proper representations of molecules lies at the core of numerous tasks such as molecular property prediction and drug design. Graph neural networks, especially message passing neural network (MPNN) and its variants, have recently made remarkable achievements in molecular graph modeling. Albeit powerful, the one-sided focuses on atom (node) or bond (edge) information of existing MPNN methods lead to the insufficient representations of the attributed molecular graphs. Herein, we propose a Communicative Message Passing Neural Network (CMPNN) to improve the molecular embedding by strengthening the message interactions between nodes and edges through a communicative kernel. In addition, the message generation process is enriched by introducing a new message booster module. Extensive experiments demonstrated that the proposed model obtained superior performances against state-of-the-art baselines on six chemical property datasets. Further visualization also showed better representation capacity of our model.

We present a highly effective dynamic programming driven memetic algorithm for the Steiner tree problem with revenues, budget, and hop constraints (STPRBH), which aims at determining a subtree of an undirected graph, so as to maximize the collected revenue, subject to both budget and hop constraints. The main features of the proposed algorithm include a probabilistic constructive procedure to generate initial solutions, a neighborhood search procedure using dynamic programming to significantly speed up neighborhood exploration, a backbone-based crossover operator to generate offspring solutions, as well as a quality-and-distance updating strategy to manage the population. Computational results based on four groups of 384 well-known benchmarks demonstrate the value of the proposed algorithm, compared to the state of the art approaches. In particular, for the 56 most challenging instances with unknown optima, our algorithm succeeds in providing 45 improved best known solutions within a short computing time. We additionally provide results for a group of 30 challenging instances that are introduced in the paper. We provide a complexity analysis of the proposed algorithm and study the impact of some ingredients on the performance of the algorithm.