The Group-Theoretic Approach to Generating Cutting Planes in Mixed Integer
Programming: Theory and Perspectives

By: Dr. Jean Philippe Richard


Abstract: 
One of the most fundamental questions in mixed integer programming is that of
deriving strong valid inequalities for unstructured problems. In this talk, we
provide an overview of the mathematical foundations and recent theoretical and
computational advances in the study of the group-theoretic approach to the
generation of cutting planes in mixed integer programming. Starting from the seminal
work of Gomory (1969) and Gomory and Johnson (1972), we motivate the definition of
group relaxation of mixed integer programs and describe fundamental results about
its valid inequalities. We also describe new proof techniques that have been
proposed to show that given inequalities are strong (extreme) for the group problem.
We then present some recent methods we proposed to derive candidate extreme
inequalities.