作为运筹学重要内容之一的混合整数规划问题,在制造业、农业、航空运输业和金融业等领域具有广泛应用。线性规划问题发展至今,已提出和发展了多种多样的用于解决不同类型问题的算法和先进求解器。而针对不同类型和难度的问题,应当选择最合适的算法或者求解器进行求解,从而能降低计算成本,同时提高解的质量。因此,通过对问题的求解难度进行预估,有助于判断应采用何种算法或如何设置求解器参数进行求解。本文利用社交网络分析方法,将其创新性地应用于数学领域。用网络图表达混合整数规划问题,并从不同社交网络分析指标,对不同求解难度的混合整数规划问题进行统计分析,筛选出能反映求解难度的关键特征并由此建立难度预测模型,此外还基于关键特征提出了优化混合整数规划问题求解效率的改进算法。最后以实际印刷电路板装配线平衡问题以及大学课程时间表安排问题为研究案例,将基于社交网络分析的混合整数规划问题的特征分析方法、求解难度预估模型以及求解优化方法应用于其中,发现所提出的模型与方法具有良好的理论意义和实用价值。本文研究工作和主要成果如下:(1)分析了混合整数规划问题的研究现状以及MIPLIB(The Mixed Integer Programming Library)所提供的带有求解难度标签的混合整数规划问题集特征,采用交邻图对混合整数规划问题样本集进行可视化表达,并按照类别标签进行分类。应用社交网络分析方法,选取了能良好反映网络凝聚性、中心性、传递性以及最短路径等的社交网络指标,对交邻图进行特征提取,并将数据按类别标签进行区分。(2)针对含有交邻图社交网络特征的数据,在进行数据预处理后,对每一分析指标下的数据按类别标签分类,并以箱型图、小提琴图和抖动图相结合的方式展示数据分布情况,给出了描述性统计分析结果。应用Shapiro-Wilk正态性检验方法检验得到数据并不符合正态分布,因此采用非参数检验方法进行后续显著性检验。利用Kruskal-Wallis显著性检验方法,检验每一分析指标下不同类别的数据是否具有显著性差异。再利用其事后检验方法,Dunn检验方法就两两类别之间做显著性差异检验。(3)基于在Kruskal-Wallis检验和Dunn检验的双重检验下,保留在不同类别间具有显著性差异的分析指标作为关键特征。采用Bootstrap重采样方法,估计不同类别的数据在每一关键特征下的中位数和均值,以呈现具有不同类别标签的混合整数规划问题在各个关键指标下的平均水平。(4)对关键特征进行了Spearman相关性分析,以相关性矩阵图的形式阐释了关键特征之间具有较高的相关性,即具有多重共线性。应用主成分分析消除了数据之间的多重共线性,避免了多重共线性对线性分类模型分类效果的影响。并采用累计方差比例和Kaiser-Guttman规则,选择了保留了80%以上原始数据信息的主成分,完成了数据降维。在降维数据的基础上,采用逻辑回归、线性判别分析以及随机森林构建了预测模型。对带有类别标签的降维数据分为了训练集和测试集,对每一个分类模型都进行了10次10折交叉验证,并采用SMOTE采样技术解决数据不平衡问题。从预测结果准确率、Kappa值、AUC以及运行时间等角度,对三类预测模型进行了性能比较,最终得到三者表现性能相当且分类准确率可达86%左右,其中线性判别分析分类模型相对最好。(5)基于关键特征提出两种了优化混合整数规划问题求解效率的优化算法,一种是基于混合整数规划问题结构特性,即变量数量和约束条件数量,提出从分支定界法的线性松弛规划算法角度,针对不同的变量与约束条件数量之比,提出优化算法;另一种是基于混合整数规划问题对偶交邻图的社交网络特性,度中心性和中介中心性,对混合整数规划问题模型做出优化。两种优化算法经算例验证,具有可靠性和有效性。(6)开展了实例分析,其中实际应用案例包括印刷电路板装配线平衡问题和基于课程设置的课程时间表问题。通过构建实际应用案例的混合整数规划数学模型,生成交邻图,再结合上述的分析方法和构建的预测模型,对相应的混合整数规划问题进行特征分析和求解难度预测。对应不同类型的问题,采用不同优化算法进行求解,并比较了不同的优化算法的求解性能,验证了预测模型和算法的可行性和有效性。