The polyhedral structure of the convex hull of the 0-1 mixed knapsack polytope defined by a knapsack inequality with continuous and binary variables with upper bounds is investigated. This polytope arises as subpolytope of more general mixed integer problems such as network flow problems, facility location problems, and lot-sizing problems.;Two sets of valid inequalities for the polytope are developed. We derive the first set of valid inequalities by adding a new subset of variables to the flow cover inequalities. We show that, under some conditions, this set is facet defining. Computational results show the effectiveness of these inequalities.;The second set of valid inequality is generated by sequence independent lifting of the flow cover inequalities. We show that computing exact lifting coefficients is NP-hard. As a result, an approximate lifting procedure is developed. We give computational results that show the effectiveness of the valid inequalities and the lifting procedure.
展开▼
