In this lecture we will consider a particular methodology for the solution of integer linear programming problems, known as the cutting plane method. Cutting plane algorithms were first introduced in the `50s and have shown their efficiency especially when applied to solving integer linear models of combinatorial problems.
However, in this lecture we will review some procedures for the solution of general integer linear programming problems, that is to say problems without a particular structure.
First we are going to look at a few definitions and basic geometric properties of integer linear programming that are at the basis of the cutting plane approach and the general scheme of the procedure. Then we are going to review two particular types of algorithms: the first one is based on the Chavatal - Gomory inequalities, the second one, more recent, is based on a convexification method and works for mixed 0-1 problems.