在当今大数据背景下，从实际应用中抽象出来的线性规划问题的规模越来越大，复杂性越来越高，因此数据预处理技术在线性规划问题求解中的重要性日渐突显。对偶性不仅有助于原始问题的算法（如对偶单纯形法）求解，而且是进行算法求解前的预处理步的重要组成部分。针对后者，本文基于有上下界的线性规划模型，详细分析总结了将对偶性应用于预处理中的两种方法：优先列和比例列的处理，并利用无效约束的概念证明了弱优先列的性质，最后应用C语言将预处理方法进行编程实现，以国际通用题库中变量个数大于1500的标准线性规划问题为实例进行测试。实例测试结果表明：（1）对于一般线性规划问题而言，对偶性在预处理中的应用能够有效减小问题规模，一方面体现在直接减少问题的变量数和非零元数，另一方面通过影响其他预处理方法间接减少问题的约束个数；（2）从减小问题规模的角度，对大部分问题而言比例列的预处理效果优于优先列。
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.
[1] 孙贵吉, 曹晓威. 大规模线性优化系统的设计与实现[J]. 吉林大学学报, 2004, 22(3): 258-259.
[2] Ye Yinyu. Multi-block alternating direction method of multipliers: Are there better algorithms for linear programming[R]. Beijing: The International Congress on Industrial and Applied Mathematics, 2015.
[3] 成孟金, 赵飞. 线性规划模型预处理的研究与实现[J]. 甘肃科技, 2008, 24(23): 87-89.
[4] Gondzio J, Terlaky T. A computational view of interior-point methods for linear programming[J]. Advanced in Linear and Integer Programming. 1995, 36(3): 103-144.
[5] Brearley A L, Mitra G, Willianms H P. Analysis of mathematical programming problems prior to applying the simplex algorithm[J]. Mathematical Programming. 1975, 8(1):54-83.
[6] Andersen E D, Andersen K D. Presolving in linear programming[J]. Math Programming, 1995, 71(2): 221-245.
[7] Gondzio J. Presolve analysis of linear programs prior to applying an interior point method[J]. Informs Journal on Computing, 1994, 13(1): 73-91.
[8] Paulraj S, Sumathi P. A comparative study of redundant constraints identification methods in linear programming problems[J]. Mathematical Problems in Engineering, 2010, 2010(1): 242-256.
[9] 李博, 张国光, 吕香奋. 线性规划模型预处理技术[C]. 中国自动化学会. 第27届中国控制会议论文集. 北京:北京航空航天大学出版社, 2008.
[10] 魏子銮, 吴力. 线性规划问题的数据预处理[J]. 数值计算与计算机应用, 1991,12(4): 197-202.
[11] 高引民, 甘仞初. 线性规划问题非有效约束条件性质研究[J]. 系统工程与电子技术, 2005, 27(6): 1041-1043.
[12] Paulraj S, Sumathi M P. A new approach for selecting a constraint in linear programming problems to identify the redundant constraints[J]. International Journal of Scientific & Engineering Research, 2012, 3(8): 1-4.
[13] Mészáros C, Suhl U H. Advanced preprocessing techniques for linear and quadratic programming[J]. OR Spectrum, 2003,25(4): 575-595.
[14] Sadhana V V. Efficient presolving in linear programming[D]. USA: University of Florida. 2002.
[15] Heinz S, Schulz J, Beck J C. Using dual presolving reductions to reformulate cumulative constraints[J]. Constraints, 2013, 18(18): 166-201.
[16] Gamrath G, Koch T, Martin A, et al. Progress in presolving for mixed integer programming[J]. Mathematical Programming Computation, 2015, 7(4): 1-32.
