对偶性在线性规划预处理中的应用分析

在当今大数据背景下，从实际应用中抽象出来的线性规划问题的规模越来越大，复杂性越来越高，因此数据预处理技术在线性规划问题求解中的重要性日渐突显。对偶性不仅有助于原始问题的算法（如对偶单纯形法）求解，而且是进行算法求解前的预处理步的重要组成部分。针对后者，本文基于有上下界的线性规划模型，详细分析总结了将对偶性应用于预处理中的两种方法：优先列和比例列的处理，并利用无效约束的概念证明了弱优先列的性质，最后应用C语言将预处理方法进行编程实现，以国际通用题库中变量个数大于1500的标准线性规划问题为实例进行测试。实例测试结果表明：（1）对于一般线性规划问题而言，对偶性在预处理中的应用能够有效减小问题规模，一方面体现在直接减少问题的变量数和非零元数，另一方面通过影响其他预处理方法间接减少问题的约束个数；（2）从减小问题规模的角度，对大部分问题而言比例列的预处理效果优于优先列。

Analysis of Using Duality for Presolving in Linear Programming

With today's large number of data, the use of linear programming is facing the real big size of applications with increasing complexity, so data presolving techniques for solving linear programming problems become very important. Duality not only help to solve the original problems (such as dual simplex method), but also is an important part of presolving techniques before solving the problems. For presolving, based on a model of linear programming problems with upper and lower bounds, two methods:dominated columns and duplicated columns in detail to realize using duality in presolving are analyzed and summarized, and the nature of weak dominated columns is proved by using invalid constraints concept. Finally, algorithm is implemented with C programming language for testing standard internationally accepted linear programming problems with number of variables greater than 1500. The results for tested problems show that:(1) For general linear programming problems, using duality in presolving can reduce the size of the problems effectively in two ways:by directly reducing the number of variables and non-zero elements of the problem and by influencing other presolving methods to reduce the number of constraints indirectly. (2) From the view of reducing problem size, most of the problems have shown that results of presolving process for dominated columns are better than those for duplicated columns. Apart from verifying and proving the importance and feasibility of using duality in presolving, new references are also provided for future researchers on presolving methods and techniques in order to come up with more valuable presolving methods.