Disjunctive Cut Generation for Mixed 0-1 Programs: Duality and Lifting

We analyse a class of mathematical programs that enable the generation of disjunctive cutting planes for mixed 0--1 programming. Through duality theory we provide a natural geometric interpretation of these problems. A simplification step allows us to solve the mathematical programs in a lower dimensional space. The optimal solution is then lifted to the original space of variables. 1 Introduction There has recently been a renewed interest in mixed 0--1 linear programming models with no underlying combinatorial structure. The main goal of this line of research in integer programming is to develop solution techniques, based on cutting plane algorithms, that do not rely on a problemspecific analysis of the polyhedral structure of the integer program. Disjunctive cutting planes rely solely on the fact that some of the variables are integer constrained and have proven to be quite effective when used within a branch-and-cut algorithm. These cuts are selected among the valid inequalities of ..