## Abstract

We study the convex hull of the feasible set of the semi-continuous knapsack problem, in which the variables belong to the union of two intervals. Such structure arises in a wide variety of important problems, e.g. blending and portfolio selection. We show how strong inequalities valid for the semi-continuous knapsack polyhedron can be derived and used in a branch-and-cut scheme for problems with semi-continuous variables. To demonstrate the effectiveness of these inequalities, which we call collectively semi-continuous cuts, we present computational results on real instances of the unit commitment problem, as well as on a number of randomly generated instances of linear programming with semi-continuous variables.

Original language | English |
---|---|

Pages (from-to) | 169-203 |

Number of pages | 35 |

Journal | Mathematical Programming |

Volume | 142 |

Issue number | 1-2 |

DOIs | |

State | Published - Dec 2013 |

## Keywords

- Branch-and-cut
- Disjunctive programming
- Mixed-integer programming
- Polyhedral combinatorics
- Semi-continuous variables
- Unit commitment problem