A Polyhedral Study of the Semi-Continuous Knapsack Problem
Ismael de Farias(ismael.de-fariasttu.edu)
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.
Entry Submitted: 06/01/2011
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|