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.
HU Yan-jie, HUANG Si-ming, N. Adrien, WU Yu
. Analysis of Using Duality for Presolving in Linear Programming[J]. Chinese Journal of Management Science, 2016
, 24(12)
: 117
-126
.
DOI: 10.16381/j.cnki.issn1003-207x.2016.12.014
[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.