Optimization Online


A Polyhedral Study of the Semi-Continuous Knapsack Problem

Ismael de Farias(ismael.de-farias***at***ttu.edu)
Ming Zhao(ming.zhao***at***sas.com)

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.

Keywords: Semi-continuous variables, mixed-integer programming, disjunctive programming, polyhedral combinatorics, branch-and-cut, unit commitment problem

Category 1: Integer Programming

Citation: Technical report, Department of Industrial Engineering, Texas Tech University, June, 2011.

Download: [PDF]

Entry Submitted: 06/01/2011
Entry Accepted: 06/01/2011
Entry Last Modified: 06/01/2011

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society