Neural Network-Based Dimensionality Reduction for Large-Scale Binary Optimization With Millions of Variables

Binary optimization assumes a pervasive significance in the context of practical applications, such as knapsack problems, maximum cut problems, and critical node detection problems. Existing techniques including mathematical programming, heuristics, evolutionary computation, and neural networks have been employed to tackle binary optimization problems (BOPs), however, they grapple with the challenge of optimizing a large number of binary variables. In this paper, we propose a dimensionality reduction method to assist evolutionary algorithms in solving large-scale BOPs, which is achieved based on neural networks. The proposed method converts the optimization of a large number of binary variables into the optimization of a small number of network weights, resulting in a significant reduction in search space dimensionality. Crucially, the proposed method obviates the necessity for a training process, which eliminates the requirement for a priori knowledge and enhances the search efficiency. On six types of single-and multi-objective BOPs with up to 10 000 000 variables, the proposed method demonstrates superiority over top-tier evolutionary algorithms and neural network-based methods.