article · 2011

A Polyhedral Study of the Semi-Continuous Knapsack Problem

Ismael Regis, Ming Zhao

Cited by 0Abstract and details only

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. Besides being important in its own right, the semi-continuous knapsack problem arises in a number of other contexts, e.g. it is a relaxation of general mixed-integer programming. 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.

Cite this paper

APA 7

Regis, I., & Zhao, M. (2011). A Polyhedral Study of the Semi-Continuous Knapsack Problem.

MLA 9

Regis, Ismael, and Ming Zhao. “A Polyhedral Study of the Semi-Continuous Knapsack Problem.” 2011.

Chicago

Regis, Ismael, and Ming Zhao. 2011. “A Polyhedral Study of the Semi-Continuous Knapsack Problem.”

Harvard

Regis, I. and Zhao, M. (2011) ‘A Polyhedral Study of the Semi-Continuous Knapsack Problem’.

BibTeX

@article{regis2011polyhedral,
  title = {{A Polyhedral Study of the Semi-Continuous Knapsack Problem}},
  author = {Regis, Ismael and Zhao, Ming},
  year = {2011}
}

Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.