Lifted inequalities for 0-1 mixed integer programming

In this thesis, we introduce the mixed 0-1 knapsack polytope, which is defined by a single knapsack constraint that contains 0-1 and continuous variables. This polytope is important since it appears as a relaxation of many mixed integer programs and also as a relaxation of the simplex tableau rows of mixed integer programs.;We develop algorithms for the lifting of continuous variables as a way to derive facets of the mixed 0-1 knapsack polytope. In particular, we introduce the concept of superlinear lifting and emphasize its computational advantages. We also show how it can be used to obtain families of facet-defining inequalities for the 0-1 mixed integer knapsack polytope. We present separation algorithms to use these valid inequalities in branch-and-cut algorithms for 0-1 mixed integer programs. We also describe how they can be used directly as simplex tableau cuts and how they yield a finitely convergent algorithm. Finally, we report computational experiments that indicate that these inequalities can significantly help in the solution of practical 0-1 mixed integer problems.