Sequence independent lifting in mixed integer programming

We investigate lifting, i.e., the process of taking a valid inequality for a polyhedron and extending it to a valid inequality in a higher dimensional space. Lifting is usually applied sequentially, that is, variables in a se t are lifted one after the other. This may be computationally unattractive since it involves the solution of an optimization problem to compute a lift ing coefficient for each variable. To relieve this computational burden, we study sequence independent lifting, which only involves the solution of on e optimization problem. We show that if a certain lifting function is super additive, then the lifting coefficients are independent of the lifting sequ ence. We introduce the idea of valid superadditive lifting functions to obt ain good aproximations to maximum lifting. We apply these results to streng then Balas' lifting theorem for cover inequalities and to produce lifted fl ow cover inequalities for a single node flow problem.