A polyhedral study of the semi-continuous knapsack problem

Ismael Regis De Farias, Ming Zhao

Research output: Contribution to journalArticlepeer-review

9 Scopus citations


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 languageEnglish
Pages (from-to)169-203
Number of pages35
JournalMathematical Programming
Issue number1-2
StatePublished - Dec 2013


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


Dive into the research topics of 'A polyhedral study of the semi-continuous knapsack problem'. Together they form a unique fingerprint.

Cite this