Research On Parameter Configuration Method Of Constrained Optimization Algorithm Via Graph Clustering

With the progress of industrial technology and enterprise development,constrained optimization problems are more and more widely used,and many optimization algorithms or solvers for such problems are produced.The performances and solving effects of these algorithms or solvers are usually affected by their parameters.Reasonable adjustment of the parameters of the algorithms or solvers can effectively improve the efficiency and quality of solving constrained optimization problems.When the number of parameters to be adjusted is large,the options for parameter configuration are huge.The manual adjustment methods based on expert experience cannot solve this problem well,so the realization of automatic configuration of algorithm parameters has theoretical significance and application value.This thesis takes CPLEX as the research object and studies the parameter configuration of solving mixed integer programming(MIP)problems based on instance features.An algorithm configuration method based on graph clustering(GCAC)is proposed,which extracts the features of MIP problem instances automatically,optimizes the parameter configuration of multi-source instances and improves the solving efficiency of MIP problem instances.And this thesis develops an algorithm configuration software.The specific works are as follows.Firstly,an algorithm parameter automatic configuration method based on graph clustering is proposed.First of all,the original feature information is extracted from the MIP problem instance.The bipartite graph method is used to construct the graph structure of the MIP problem instance,and the original feature information is extracted from the graph structure based on the random walk algorithm,which gives consideration to both the numerical information and the structural information of the instance,and makes the feature extraction more comprehensive.Then,based on auto-encoder,the graph embedding model is built and trained to realize the extraction of instance embedding features after dimensionality reduction automatically.Finally,according to the embedding features,the clustering method is used to divide problem instance clusters,and the algorithm parameter configuration training is carried out for each instance cluster,which realizes the optimization of parameter configuration scheme and the improvement of problem solving efficiency under the input of multi-source problem instances.Secondly,this thesis uses CPLEX solver and three multi-source MIP instance sets to design the cluster analysis experiment,the configuration effect experiment and the generalization ability experiment for the proposed method.The clustering analysis experiment verifies that k-means clustering algorithm has better performance in the proposed method by discussing the selection of clustering algorithm in this thesis.In the configuration effect and generalization ability experiments,by comparing with other algorithm parameters automatic configuration methods,the experimental results verify that the parameters configuration schemes of CPLEX solver configurated by the method of this thesis have better configuration optimization results,and show stronger generalization ability in test data sets with different sizes.The method of this thesis is more efficient for solving multi-source MIP problem instances.Thirdly,according to the actual requirements,this thesis designs and develops the algorithm configuration software.The software is designed with three layers,which consists of user layer,application layer and data layer.SQLite3 is used as the database.The software provides users with optimization algorithm configuration training,instance solving application,project file management and other functions.The running results verify the effectiveness of the designed software,which can meet the needs of users for automatic parameter configuration of the optimization algorithm.