Binary (0-1) integer programming (BIP) is pivotal in scientific domains requiring discrete decision-making. As the advance of AI computing, recent works explore neural network-based solver for integer linear programming (ILP) problems. Yet, they lack scalability for tackling nonlinear challenges. To handle nonlinearities, state-of-the-art Branch-and-Cut solvers employ linear relaxations, leading to exponential growth in auxiliary variables and severe computation limitations. To overcome these limitations, we propose BIPNN, an unsupervised learning framework to solve BIP problems via hypergraph neural networks (HyperGNN). Specifically, (i) BIPNN reformulates BIPs-constrained, discrete, and nonlinear (sin, log, exp) optimization problems-into unconstrained, differentiable, and polynomial loss functions. The reformulation stems from the observation of a precise one-to-one mapping between polynomial BIP objectives and hypergraph structures, enabling the unsupervised training of HyperGNN to optimize BIP problems in an end-to-end manner. On this basis, (ii) we propose a GPU-accelerated and continuous-annealing-enhanced training pipeline for BIPNN. The pipeline enables BIPNN to optimize large-scale nonlinear terms in BIPs fully in parallel via straightforward gradient descent, thus significantly reducing the training cost while ensuring the generation of discrete, high-quality solutions. Extensive experiments on synthetic and real-world datasets highlight the superiority of our approach.

The booming crowdsourced delivery leverages networks of local, part time couriers to meet growing customer demands for increasingly speedy shipping. By conducting city-wide low-cost delivery networks, crowd-sourced enabled instant delivery platforms have fought to figure out a way to offer instant shipping at low price. Nevertheless, limited ubiquitous computing infrastructures impede the discovery of equilibrium between cost reduction and sufficient shipping capacity. In this article, we present our endeavor towards understanding and designing a dynamic pricing framework based on a large-scale food-delivery platform. To reduce delivery fees in capacity overload regions and resolve the decline of service quality caused by insufficient shipping capacity, we address the challenge of quantifying the inter-regional shipping capacity disparities by accordingly applying a variety of techniques, including cooperative game theory, probability analysis and address entity recognition. In particular, we provide an$O(n^{2})$algorithm for the cooperative game based cost allocation, of which the exponential computational complexity$O(n^{2}2^{n})$is generally considered a major challenge in real-world applications. City-wide experiments in Nanjing and Shenzhen illustrate that we achieve a 10% decrease in delivery fees under overload shipping capacity and a 3% increase in completion rates in customer locations with poor service quality.

Summary Replacement algorithms have been widely used as key technologies for cache management in areas such as file systems or database management. A replacement algorithm determines which page to be evicted when the cache is full and a new page is referenced. Because replacement policies considering only recency or frequency such as LRU (Least Recently Used) and LFU (Least Frequently Used) do not perform well, replacement polices that take both recency and frequency into account have been intensively studied. As a classical replacement policy, LRFU (Least Recently/Frequently Used) policy subsumes the LRU and LFU policy. However, because LFU is not able to adapt to the change of page accessing pattern and it is hard to select a suitable λ for each certain trace, LRFU cannot always guarantee a good performance. In this paper, we propose a Window‐LRFU policy, to subsume the LRU and Window‐LFU policies. Experimental results show that the Window‐LRFU policy outperforms LRFU and has at least competitive performance than other classical algorithms. Copyright © 2015 John Wiley & Sons, Ltd.

In ad hoc wireless networks, a Connected Dominating Set (CDS) has been extensively used as a Virtual Backbone (VB) for routing. The majority of approximation algorithms for constructing a small CDS in wireless ad hoc networks follow a general two-phased approach. The first phase is to construct a Dominating Set (DS) and the second phase is to connect the nodes in it. Generally, in the first phase, a Maximum Independent Set (MIS) is used as the DS. The relation between the size of a Maximum Independent Set and a Minimum Connected Dominating Set (MCDS) plays the key role in the performance analyses of these two-phased algorithms. In homogeneous wireless ad hoc networks modeled as Unit Disk Graphs (UDG) and Unit Ball Graphs (UBG), the relation between them has been well studied. However, in heterogeneous wireless networks which generally modeled as Disk Graphs with Bidirectional links (DGB) and Ball Graphs with Bidirectional links (BGB), upper bounds for the size of MISs have seldom been studied. In this paper, we give tighter upper bounds for the size of MISs in heterogeneous wireless ad hoc networks. When the maximum and minimum transmission range are relatively close, our result is much better. In DGB, when the transmission range ratio is (1,1.152], (1.152,1.307], (1.307,1.407], (1.407,1.462], (1.462,1.515], (1.515,1.618], (1.618,1.932], we prove that the size of any Maximal Independent Set (MIS) is upper bounded by 6opt + 1, 7opt + 1, 8opt + 1, 9opt + 1, 10opt + 1, 11opt + 1, 16.7778opt + 1.2222, where opt denotes the size of an optimal solution of the CDS problem.