A polyhedral study of the semi-continuous knapsack problem

Research output: Contribution to journalArticlepeer-review

7 Scopus citations

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

Keywords

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

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

Cite this