Title: Integer Programs and Group Relaxations

In the past 5 years, there has been renewed interest in using Gomory's corner polyhedron and group relaxations for solving integer programs. We will describe the basic theory of how group relaxations can be used to generate cutting planes for general integer programs and review recent research results. Although much is understood theoretically about these group-based inequalities, few computational experiments have been performed to date, and many implementation issues have not been addressed. We will present three new approaches for separating group-based cutting planes. The first two methods, inspired by Gomory's original work, are theoretically sound but have detrimental computational inefficiencies. To address these inefficiencies, we introduce the Approximate Group Method, which avoids the computational difficulties of the first two methods and generates inequalities that appear to be almost as strong as the earlier inequalities. We conclude with computational results that compare the computational impact of each of these three methods to that of the most well-known class of group relaxation cuts, the Gomory mixed integer cut.