Lifting for mixed integer programs with variable upper bounds
We investigate the convex hull of the set defined by a single inequality with continuous and binary variables, which are additionally related by variable upper bound constraints. First we elaborate on general sequence dependent lifting for this set and present a dynamic program for calculating lifting coefficients. Then we study variable fixings of this set to knapsack covers and to the single binary variable polytope. We explicitly give lifting coefficients of continuous variables when lifting the knapsack cover inequality. We provide two new families of facet-defining inequalities for the single binary variable polytope and we prove that combined with the trivial inequalities they give a full description of this polytope.
mixed integer programming polyhedral theory