A polyhedral study of the semi-continuous knapsack problem (Q2434996)

This paper is on the inequality description of the closure of the convex hull of a knapsack constraint with variables belonging to the union of two intervals, i.e. the semi-continuous knapsack polyhedron. The authors study the inequalities of the polyhedron and use the inequalities as cuts in a branch and cut. A main contribution is the lifting technique and lifting results for non-trivial inequalities. Lifting coefficients of all variables can be approximated in quadratic time. Computational results show the effectiveness of semi-continuous cuts on real instances of the stochastic unit commitment problem with linear costs and on randomly generated linear programs with semi-continuous variables. The unit commitment problem is to find the right time to start and stop power generating units in order to minimize the total operating cost subject to satisfying the demand and technological constraints.