A polyhedral study of the semi-continuous knapsack problem

• 成果类型: Article
• 署名作者: de Farias, Ismael Regis, Jr.; Zhao, Ming
• 署名单位: Texas Tech University System; Texas Tech University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-012-0566-3
• 发表日期: 2013
• 页码: 169-203
• 关键词: branch-and-cut; programming-problems; binary variables; unit commitment; cutting-planes; optimization; polytope; facets; models

摘要

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.