Gomory cutting plane algorithm using exact arithmetic.

摘要

One of the most studied problems in Operations Research is linear programming. These are problems that are maximization or minimization of a linear objective function subject to linear constraints. If we have the added burden of having restrictions that some of the variables must also be integral then we have a Mixed Integer Programming Problem. If all of the variables must be integral then this is a Pure Integer Programming Problem. These are the types of problems taken up in this thesis. One method used to solve Integer Programming Problems is the use of cutting planes. There are many different types of cutting planes, we focus on Gomory cutting planes. Gomory cutting planes have been studied in depth and utilized in various commercial codes. We will show that by using exact arithmetic rather than floating point arithmetic, we can produce better cuts. The main reason for this is the addition of slack variables to the Gomory inequalities. For exact arithmetic, this slack variable has to itself be integral whereas for floating point arithmetic, the slack could be a floating point number.; We have written an exact arithmetic simplex program that incorporates LU factorization of the basis matrix and the steepest edge pivoting rule. We have explored the size of the certain key vectors in the simplex algorithm. We also wrote code that finds all of the various forms of Gomory cutting planes in exact arithmetic, adds them to the simplex tableau, and reoptimizes using dual simplex. Further, we wrote code that drop certain Gomory cuts when they are not useful any more. We explored the size of the Gomory cutting planes and how it relates to the size of vectors in the simplex algorithm. Since the majority of the time is spent reoptimizing, we wanted to find a way to utilize the power of the CPLEX solver with our exact Gomory cutting planes.; Another use for exact arithmetic is when we have dual degeneracy, or in other words alternate optima. We pivot to these alternate optima and cut off this additional solution, which reduces the number of total Gomory iterations by performing just one extra simplex pivot.