Gomory Cutting Plane Algorithm Using Exact Arithmetic

Kristin Farwell

PhD Thesis, January 2006

Mathematical Sciences

Rensselaer Polytechnic Institute

Advisor: John Mitchell

Download the thesis, in pdf

Abstract:

In the field of Operations Research (OR) we solve problems dealing with optimization. One of the most studied problems in OR is linear programming problems. 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 on some of the variables that 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 that we are going to be studying more in depth. One method used to solve Integer Programming Problems are known as cutting planes. There are many different types of cutting planes. One type of cutting plane is known as 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.

What we have done is write an exact arithmetic simplex program which incorporates some of the recent advances like LU factorization of the basis matrix and steepest edge pivoting rule. We have explored the size of the certain key vectors in the simplex algorithm. We also wrote code that finds the all of the various forms of Gomory cutting planes in exact arithmetic and adds them to the simplex tableau and reoptimizes using dual simplex. We also wrote code that drops certain Gomory cuts when they are not useful anymore. 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 CPLEX solver and our exact Gomory cutting planes.

Another use for exact arithmetic is when we have dual degeneracy or in other words, alternate optima for two dimensional problems. We pivoted to these alternate optima and cut off this additional solution which reduced the number of total Gomory iterations by performing just one extra simplex pivot.

Library listing.

Download the thesis, in pdf.