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