The Computer Journal, Volume 62, Issue 12, December 2019, Pages 1734-1747, doi: 10.1093/comjnl/bxz033. In the originally published version of this manuscript, requested author amendments were inadvertently omitted prior to publishing and have since been corrected. The Publisher would like to apologise for any inconvenience caused to the reader.

Knapsack problems (KPs) are common in industry, but solving KPs is known to be NP-hard and has been tractable only at a relatively small scale. This paper examines KPs in a slightly generalized form and shows that they can be solved nearly optimally at scale via distributed algorithms. The proposed approach can be implemented fairly easily with off-the-shelf distributed computing frameworks (e.g. MPI, Hadoop, Spark). As an example, our implementation leads to one of the most efficient KP solvers known to date – capable to solve KPs at an unprecedented scale (e.g., KPs with 1 billion decision variables and 1 billion constraints can be solved within 1 hour). The system has been deployed to production and called on a daily basis, yielding significant business impacts at Ant Financial.

Abstract Malware brings a big security threat on the Internet today. With the great increasing malware attacks. Behavior-based detection approaches are one of the major method to detect zero-day malware. Such approaches often use API calls to represent the behavior of malware. Unfortunately, behavior-based approaches suffer from behavior obfuscation attacks. In this paper, we propose a novel malware detection approach that is both effective and efficient. First, we abstract the API call to object operation. And then we generate the object operation dependency graph based on these object operations. Our approach use dependency graph to represent the behavior of malware. The evaluation results show that our approach can provide a complete resistance to all types of behavior obfuscation attacks, and outperforms existing behavior-based approaches in terms of better effectiveness and efficiency.

The vehicle routing problem with time windows (VRPTW) is an important problem in logistics. The problem is to serve a number of customers at minimum cost without violating the customers’ time-window constraints or the vehicle-capacity constraint. In this paper, we propose a two-stage algorithm for the VRPTW. The algorithm first minimizes the number of vehicles with an ejection pool to hold temporarily unserved customers, which enables the algorithm to go through the infeasible solution space. Then it minimizes the total travel distance using a multi-start iterated hill-climbing algorithm with classical and new operators including generalized ejection chains, which enable the algorithm to search a larger neighborhood. We applied the algorithm to Solomon’s 56 VRPTW instances and Gehring and Homberger’s 300 extended instances. The experimental results showed that the algorithm is effective and efficient in reducing the number of vehicles and is also very competitive in terms of distance minimization. The m-VRPTW is a variant of the VRPTW in which a limited number of vehicles is available. A feasible solution to m-VRPTW may contain some unserved customers due to the insufficiency of vehicles. The primary objective of m-VRPTW is to maximize the number of customers served. We extended our VRPTW algorithm to solve m-VRPTW and the experimental results showed consistently good performance of the algorithm when compared with other methods.

In this paper, we study shelf space allocation optimization which is important to retail operations management. Our approach is to formulate a model that is applicable to operational realities and to seek solutions with realistic test data. This model is linked to the multidimensional knapsack problem. We first solve a simplified version of the problem to achieve maximum profit by transforming it into a network flow problem. Then, with simple adaptations we solve the general shelf space allocation problem with the help of the network flow model. The approach is simple and direct while experimental results improve on recent findings significantly and are very close to the optimal.