The Methods Of Presolving For Mixed Integer Programming

ABSTRACT:Mixed integer linear programming has applications in a large variety of domains, including highway traffic、air transport、economy and finance as well as communication. So the new requirements for solving mixed integer linear programming problems were raised constantly. Generally, however, because of the large scale of the mixed integer programming problems in real life, we have to use modeling tools for modeling. Therefore, the models inevitably contain a lot of redundant information which greatly hindered the solving of the problems and raised requirements for presolving. Presolving is a way to transform the given problem instance into an equivalent instance that is easier to solve. This paper mainly introduces some commonly used algorithms of presolving. The presolving algorithms contain presolving of linear constraints, presolving of equations, dual aggregation, and so on. Then do numerical experiment for some mixed integer programming instances according to the given presoving algorithms. The results of the numerical experiment shows that the common mixed integer programming will be easier to solve after presolving.