Difficulty Prediction And Applications Of Mixed-Integer Programming Problems Based On Social Network Analysis

As an important part of operations research,mixed integer programming problems have been widely used in the fields of manufacturing,agriculture,air transportation,finance,etc.Since the problems of linear programming has been proposed,a variety of algorithms and stateof-the-art solvers have been developed for different types of problems.But the algorithms have their own advantages and disadvantages.Selecting the most suitable algorithm for different types of problems can efficiently reduce the calculation cost and may help improve the quality of solutions.Before determining the algorithm or the solver adopted for a mixed integer programming problem,a preliminary judgment can be made by estimating the difficulty of the problem.In this thesis,social network analysis method is applied innovatively to the field of mathematics.From different aspects of social network indicators,statistical analysis is performed on mixed integer programming problems with different difficulty labels provided by MIPLIB,key features involve solving difficulty are selected and difficulty prediction models are established based on key features.In addition,improved algorithms based on key features are proposed to improve the solution efficiency of mixed integer programming problems.The practical printed circuit board assembly line balance problem and the curriculum based course timetabling problem are taken as research cases.The feature analysis methods,difficulty prediction models of the mixed integer programming problem based on social network analysis and improved algorithms are applied to the practical cases,which have proved the theoretical significance and practical values of the methods proposed in the thesis.The main research contents and results are as follows:(1)The research status of mixed integer programming problems and the characteristics of mixed integer programming problem collection set with difficulty labels provided by the Mixed Integer Programming Library(MIPLIB)are analyzed.The intersection graph is used to visualize the mixed integer programming problem and the intersection graphs are classified according to category labels.Several social network indicators which can reflect the network cohesion,centrality,transitivity,and the shortest paths are selected.And the features of intersection graphs from the aspect of social network analysis are extracted,which consists of the data set with category labels that is analyzed in this research work.(2)The data containing the characteristics of the social network of the intersection graphs is preprocessed first,and the data under each analysis index is classified by category labels.Data distributions in each category are displayed through combination plots that integrate box plots,violin plots,and jitter plots.And the results of descriptive statistical analysis are given.The results of Shapiro-Wilk normality test show that the data is not of normal distribution,therefore,a series of non-parametric tests are applied for subsequent significance tests.The Kruskal-Wallis significance test is used to test whether different categories of data have significant differences under each analysis indicator.The post hoc test of Kruskal-Wallis significance test,Dunn's test is employed to test the significant differences between each pair of categories.(3)Based on the results obtained from the Kruskal-Wallis test and Dunn test,analysis indicators with significant differences between different categories are retained as key indicators.The Bootstrap resampling method is used to estimate the median and mean values of different categories of data under each key indicator to present the average level of mixed integer programming problems with different category labels.The Spearman correlation analysis is performed on the key indicators,and the correlations between the key indicators are presented in the form of a correlation matrix diagram.And the result shows that the key indicators are highly correlated with each other,which means there is multicollinearity in the model.(4)The application of principal component analysis eliminates multicollinearity between the data and avoids the impact of multicollinearity on the classification effect of the linear classification model.And the data dimension reduction is performed based on the cumulative variance ratio and the Kaiser-Guttman rule,the main component that retains more than 80% of the original data information is selected.On the basis of dimensionality reduction data,the logistic regression,linear discriminant analysis,and random forest are employed to construct prediction models.The dimension-reduced data with category labels is divided into training set and test set.The 10-fold cross-validation is conducted for 10 times for each classifier and the SMOTE sampling technology is used to deal with the unbalanced data.From the perspective of accuracy of prediction results,Kappa value,AUC,and running time,the classification performance of the three prediction models is compared.Finally,the three model's performance is comparable,and the classification effects are good.The classification accuracy rate of three models are about 86%,and the linear discriminant analysis classification model performs relatively best.(5)Based on the key features,two optimization methods are proposed to optimize the efficiency of mixed integer programming problem solutions.One is based on the characteristics of mixed integer programming problem structures,that are,the number of variables and the number of constraints.From the perspective of the linear relaxation programming algorithm of the branch and bound method,an optimization algorithm is proposed based on the ratio of the number of variables and constraints;the other is to optimize the mixed integer programming model based on the social network characteristics of dual intersection graphs,that are,degree centrality,and betweenness centrality.The reliability and effectiveness of two optimization methods are verified by several randomly selected numerical instances from MIPLIB.(6)The case analysis is carried out through two practical application cases include printed circuit board assembly line balance problem and course schedule issues based on curriculum settings.By constructing mathematical models of mixed integer programming for practical application cases,corresponding intersection graphs are generated.The proposed analysis methods are applied to analyze the characteristics of practical mixed integer programming problems of two cases,and the solving difficulties of each mixed integer programming model is predicted through the prediction model.In addition,different improved algorithms are used to solve hard MIP problems,and the performance of different algorithms in mixed integer programming problems are compared,which verifies the feasibility and effectiveness of the prediction model and improved algorithms.