Solving Combinatorial Optimization Problems with Deep Neural Network:A Survey

Combinatorial Optimization Problems(COPs)are a class of optimization problems that are commonly encountered in industrial production and everyday life.Over the last few decades,traditional algorithms,such as exact algorithms,approximate algorithms,and heuristic algorithms,have been proposed to solve COPs.However,as COPs in the real world become more complex,traditional algorithms struggle to generate optimal solutions in a limited amount of time.Since Deep Neural Networks(DNNs)are not heavily dependent on expert knowledge and are adequately flexible for generalization to various COPs,several DNN-based algorithms have been proposed in the last ten years for solving COPs.Herein,we categorize these algorithms into four classes and provide a brief overview of their applications in real-world problems.

Learning to Branch in Combinatorial Optimization With Graph Pointer Networks

Traditional expert-designed branching rules in branch-and-bound(B&B) are static, often failing to adapt to diverse and evolving problem instances. Crafting these rules is labor-intensive, and may not scale well with complex problems.Given the frequent need to solve varied combinatorial optimization problems, leveraging statistical learning to auto-tune B&B algorithms for specific problem classes becomes attractive. This paper proposes a graph pointer network model to learn the branch rules. Graph features, global features and historical features are designated to represent the solver state. The graph neural network processes graph features, while the pointer mechanism assimilates the global and historical features to finally determine the variable on which to branch. The model is trained to imitate the expert strong branching rule by a tailored top-k Kullback-Leibler divergence loss function. Experiments on a series of benchmark problems demonstrate that the proposed approach significantly outperforms the widely used expert-designed branching rules. It also outperforms state-of-the-art machine-learning-based branch-and-bound methods in terms of solving speed and search tree size on all the test instances. In addition, the model can generalize to unseen instances and scale to larger instances.

Combinatorial Optimization Based Analog Circuit Fault Diagnosis with Back Propagation Neural Network

Electronic components' reliability has become the key of the complex system mission execution. Analog circuit is an important part of electronic components. Its fault diagnosis is far more challenging than that of digital circuit. Simulations and applications have shown that the methods based on BP neural network are effective in analog circuit fault diagnosis. Aiming at the tolerance of analog circuit,a combinatorial optimization diagnosis scheme was proposed with back propagation( BP) neural network( BPNN).The main contributions of this scheme included two parts:( 1) the random tolerance samples were added into the nominal training samples to establish new training samples,which were used to train the BP neural network based diagnosis model;( 2) the initial weights of the BP neural network were optimized by genetic algorithm( GA) to avoid local minima,and the BP neural network was tuned with Levenberg-Marquardt algorithm( LMA) in the local solution space to look for the optimum solution or approximate optimal solutions. The experimental results show preliminarily that the scheme substantially improves the whole learning process approximation and generalization ability,and effectively promotes analog circuit fault diagnosis performance based on BPNN.

RECURRENT NEURAL NETWORK MODEL BASED ON PROJECTIVE OPERATOR AND ITS APPLICATION TO OPTIMIZATION PROBLEMS

The recurrent neural network （RNN） model based on projective operator was studied. Different from the former study, the value region of projective operator in the neural network in this paper is a general closed convex subset of n-dimensional Euclidean space and it is not a compact convex set in general, that is, the value region of projective operator is probably unbounded. It was proved that the network has a global solution and its solution trajectory converges to some equilibrium set whenever objective function satisfies some conditions. After that, the model was applied to continuously differentiable optimization and nonlinear or implicit complementarity problems. In addition, simulation experiments confirm the efficiency of the RNN.

Chaotic Neural Network Technique for "0-1" Programming Problems

0-1 programming is a special case of the integer programming, which is commonly encountered in many optimization problems. Neural network and its general energy function are presented for 0-1 optimization problem. Then, the 0-1 optimization problems are solved by a neural network model with transient chaotic dynamics (TCNN). Numerical simulations of two typical 0-1 optimization problems show that TCNN can overcome HNN's main drawbacks that it suffers from the local minimum and can search for the global optimal solutions in to solveing 0-1 optimization problems.

A New Searching Strategy for the Lost Plane Based on RBF Neural Network Model and Global Optimization Model

In this paper, we construct two models for the searching task for a lost plane. Model 1 determines the searching area. We predict the trajectory of floats generated after the disintegration of the plane by using RBF neural network model, and then determine the searching area according to the trajectory. With the pass of time, the searching area will also be constantly moving along the trajectory. Model 2 develops a maritime search plan to achieve the purpose of completing the search in the shortest time. We optimize the searching time and transform the problem into the 0-1 knapsack problem. Solving this problem by improved genetic algorithm, we can get the shortest searching time and the best choice for the search power.

Application of the edge of chaos in combinatorial optimization

Many problems in science,engineering and real life are related to the combinatorial optimization.However,many combinatorial optimization problems belong to a class of the NP-hard problems,and their globally optimal solutions are usually difficult to solve.Therefore,great attention has been attracted to the algorithms of searching the globally optimal solution or near-optimal solution for the combinatorial optimization problems.As a typical combinatorial optimization problem,the traveling salesman problem(TSP)often serves as a touchstone for novel approaches.It has been found that natural systems,particularly brain nervous systems,work at the critical region between order and disorder,namely,on the edge of chaos.In this work,an algorithm for the combinatorial optimization problems is proposed based on the neural networks on the edge of chaos(ECNN).The algorithm is then applied to TSPs of 10 cities,21 cities,48 cities and 70 cities.The results show that ECNN algorithm has strong ability to drive the networks away from local minimums.Compared with the transiently chaotic neural network(TCNN),the stochastic chaotic neural network(SCNN)algorithms and other optimization algorithms,much higher rates of globally optimal solutions and near-optimal solutions are obtained with ECNN algorithm.To conclude,our algorithm provides an effective way for solving the combinatorial optimization problems.

Hopfield neural network based on ant system

Hopfield neural network is a single layer feedforward neural network. Hopfield network requires some control parameters to be carefully selected, else the network is apt to converge to local minimum. An ant system is a nature inspired meta heuristic algorithm. It has been applied to several combinatorial optimization problems such as Traveling Salesman Problem, Scheduling Problems, etc. This paper will show an ant system may be used in tuning the network control parameters by a group of cooperated ants. The major advantage of this network is to adjust the network parameters automatically, avoiding a blind search for the set of control parameters. This network was tested on two TSP problems, 5 cities and 10 cities. The results have shown an obvious improvement.

A unified pre-training and adaptation framework for combinatorial optimization on graphs

Combinatorial optimization(CO)on graphs is a classic topic that has been extensively studied across many scientific and industrial fields.Recently,solving CO problems on graphs through learning methods has attracted great attention.Advanced deep learning methods,e.g.,graph neural networks(GNNs),have been used to effectively assist the process of solving COs.However,current frameworks based on GNNs are mainly designed for certain CO problems,thereby failing to consider their transferable and generalizable abilities among different COs on graphs.Moreover,simply using original graphs to model COs only captures the direct correlations among objects,which does not consider the mathematical logicality and properties of COs.In this paper,we propose a unified pre-training and adaptation framework for COs on graphs with the help of the maximum satisfiability(Max-SAT)problem.We first use Max-SAT to bridge different COs on graphs since they can be converted to Max-SAT problems represented by standard formulas and clauses with logical information.Then we further design a pre-training and domain adaptation framework to extract the transferable and generalizable features so that different COs can benefit from them.In the pre-training stage,Max-SAT instances are generated to initialize the parameters of the model.In the fine-tuning stage,instances from CO and Max-SAT problems are used for adaptation so that the transferable ability can be further improved.Numerical experiments on several datasets show that features extracted by our framework exhibit superior transferability and Max-SAT can boost the ability to solve COs on graphs.

Urban Drainage Network Scheduling Strategy Based on Dynamic Regulation: Optimization Model and Theoretical Research

With the acceleration of urbanization in China,the discharge of domestic sewage and industrial wastewater is increasing,and accidents of sewage spilling out and polluting the environment occur from time to time.Problems such as imperfect facilities and backward control methods are com-mon in the urban drainage network systems in China.Efficient drainage not only strengthens infrastructure such as rain and sewage diversion,pollution source monitoring,transportation,drainage and storage but also urgently needs technical means to monitor and optimize production and operation.Aiming at the optimal control of single-stage pumping stations and the coordinated control between two-stage pumping stations,this paper studies the modelling and optimal control of drainage network systems.Based on the Long Short Term Memory(LSTM)water level prediction model of the sewage pumping stations,and then based on the mechanism analysis of drainage pipe network,the factors that may cause the water level change of pumping station are obtained.Grey correlation analysis is carried out on these influencing factors,and the prediction model is established by taking the factors with a high correlation degree as input.The research results show that compared with the traditional prediction model,the LSTM model not only has higher prediction accuracy but also has better inflection point tracking ability.

A Chaotic Annealing Neural Network with Gain Sharpening and Its Application to 0-1 Constrained Optimization Problems

In this article, we propose sharpening the gain of the chaotic annealing neural network to solve 0 1 constrained optimization problem. During the chaotic annealing, the gain of the neurons gradually increases and finally arrives at a large value. This strategy can accelerate the convergence of the network to the binary state and keep the satisfaction of the constrains. The simulations, which take the knapsack problems as examples, demonstrate that the approach is efficient both in approximating the global solution and the number of iterations.

Bridging Reinforcement Learning and Planning to Solve Combinatorial Optimization Problems with Nested Sub-Tasks

Combinatorial Optimization(CO)problems have been intensively studied for decades with a wide range of applications.For some classic CO problems,e.g.,the Traveling Salesman Problem(TSP),both traditional planning algorithms and the emerging reinforcement learning have made solid progress in recent years.However,for CO problems with nested sub-tasks,neither end-to-end reinforcement learning algorithms nor traditional evolutionary methods can obtain satisfactory strategies within a limited time and computational resources.In this paper,we propose an algorithmic framework for solving CO problems with nested sub-tasks,in which learning and planning algorithms can be combined in a modular way.We validate our framework in the Job-Shop Scheduling Problem(JSSP),and the experimental results show that our algorithm has good performance in both solution qualities and model generalizations.

IOPS:computational graph optimization based on inter-operators parallel scheduling

To improve the inference efficiency of convolutional neural networks(CNN),the existing neural networks mainly adopt heuristic and dynamic programming algorithms to realize parallel scheduling among operators.Heuristic scheduling algorithms can generate local optima easily,while the dynamic programming algorithm has a long convergence time for complex structural models.This paper mainly studies the parallel scheduling between operators and proposes an inter-operator parallelism schedule(IOPS)scheduling algorithm that guarantees the minimum similar execution delay.Firstly,a graph partitioning algorithm based on the largest block is designed to split the neural network model into multiple subgraphs.Then,the operators that meet the conditions is replaced according to the defined operator replacement rules.Finally,the optimal scheduling method based on backtracking is used to schedule the computational graph.Network models such as Inception-v3,ResNet-50,and RandWire are selected for testing.The experimental results show that the algorithm designed in this paper can achieve a 1.6×speedup compared with the existing sequential execution methods.

Effective Neural Algorithms for Combinatorial Optimization

This paper provides an overview on the current status of the researches in the field of neural algorithms for combinatorial optimization and makes some comments on the recent development. Meanwhile,we point out that such optimization networks suffer from some serious problems. At the end of this paper, we present the readers some aspects which need more researches in the future.

Original optimal method to solve the all-pairs shortest path problem: Dhouib-matrix-ALL-SPP

The All-pairs shortest path problem(ALL-SPP)aims to find the shortest path joining all the vertices in a given graph.This study proposed a new optimal method,Dhouib-matrix-ALL-SPP(DM-ALL-SPP)to solve the ALL-SPP based on column-row navigation through the adjacency matrix.DM-ALL-SPP is designed to generate in a single execution the shortest path with details among all-pairs of vertices for a graph with positive and negative weighted edges.Even for graphs with a negative cycle,DM-ALL-SPP reported a negative cycle.In addition,DM-ALL-SPP continues to work for directed,undirected and mixed graphs.Furthermore,it is characterized by two phases:the first phase consists of adding by column repeated(n)iterations(where n is the number of vertices),and the second phase resides in adding by row executed in the worst case(n∗log(n))iterations.The first phase,focused on improving the elements of each column by adding their values to each row and modifying them with the smallest value.The second phase is emphasized by rows only for the elements modified in the first phase.Different instances from the literature were used to test the performance of the proposed DM-ALL-SPP method,which was developed using the Python programming language and the results were compared to those obtained by the Floyd-Warshall algorithm.

A Hybrid TCNN Optimization Approach for the Capacity Vehicle Routing Problem

A novel approximation algorithm was proposed for the problem of finding the minimum total cost of all routes in Capacity Vehicle Routing Problem (CVRP). CVRP can be partitioned into three parts: the selection of vehicles among the available vehicles, the initial routing of the selected fleet and the routing optimization. Fuzzy C-means (FCM) can group the customers with close Euclidean distance into the same vehicle according to the principle of similar feature partition. Transiently chaotic neural network (TCNN) combines local search and global search, possessing high search efficiency. It will solve the routes to near optimality. A simple tabu search (TS) procedure can improve the routes to more optimality. The computations on benchmark problems and comparisons with other results in literatures show that the proposed algorithm is a viable and effective approach for CVRP.

Recurrent Neural Network for Nonconvex Economic Emission Dispatch

In this paper, an economic emission dispatch(EED) model is developed to reduce fuel cost and environmental pollution emissions. Considering the development of new energy sources in recent years, the EED problem involves thermal units with the valve point effect and WTs. Meanwhile, it complies with demand constraint and generator capacity constraints. A recurrent neural network(RNN) is proposed to search for local optimal solution of the introduced nonconvex EED problem. The optimality and convergence of the proposed dynamic model are given. The RNN algorithm is verified on a power generation system for the optimization of scheduling and minimization of total cost. Moreover, a particle swarm optimization(PSO) algorithm is compared with RNN under the same problematic frame. Numerical simulation results demonstrate that the optimal scheduling given by RNN is more precise and has lower total cost than PSO. In addition, the dynamic variation of power load demand is considered and the power distribution of eight generators during 12 time periods is depicted.

A Genetic Algorithm for the Flowshop Scheduling Problem

The flowshop scheduling problem is NP complete. To solve it by genetic algorithm, an efficient crossover operator is designed. Compared with another crossover operator, this one often finds a better solution within the same time.

A Water Line Network Failure Application of Network Design Problems

This study investigated a water supply recovery problem involving municipal water service piping. The problem consisted in recovering full service after network failure, in order to rapidly satisfy all urgent citywide demands. The optimal recovery solution was achieved through the application of so-called network design problems （NDPs）, which are a form of combinatorial optimization problem. However, a conventional NDP is not suitable for addressing urgent situations because （1） it does not utilize the non-failure arcs in the network, and （2） it is solely concerned with stable costs such as flow costs. Therefore, to adapt the technique to such urgent situations, the conventional NDP is here modified to deal with the specified water supply problem. In addition, a numerical illustration using the Sendai water network is presented.

基于生产数据的混合流水车间动态调度方法研究

在智能制造背景下,物联网等信息技术为制造系统积累了大量数据,同时人工智能等先进方法为车间数据分析和实时控制提供了有效手段。因此,针对不相关并行机混合流水车间调度问题,提出了一种基于生产数据的动态调度方法,以实现订单完工时间最小化。首先以高质量调度方案为基础,从中提取生产特征和调度规则完成样本构建。其次使用Relief F算法过滤冗余生产特征,获得用于训练和预测的调度样本。然后采用融合鲸鱼优化算法的概率神经网络作为调度模型,实现基于调度样本的训练和预测过程。最后,实验结果表明,所提方法具有良好的特征选择能力和较高的预测精度,与其他实时调度方法相比具有更加优越的性能,可以有效地根据车间实时状态指导制造执行过程。