Separation and Extension of Cover Inequalities for Conic Quadratic Knapsack Constraints with Generalized Upper Bounds

作     者：Atamtuerk, Alper Muller, Laurent Flindt Pisinger, David 

作者机构：Univ Calif Berkeley Dept Ind Engn & Operat Res Berkeley CA 94720 USA Tech Univ Denmark Dept Engn Management DK-2800 Lyngby Denmark 

出 版 物：《INFORMS JOURNAL ON COMPUTING》 (美国运筹学与管理学会计算杂志)

年 卷 期：2013年第25卷第3期

页      面：420-431页

核心收录：

学科分类：1201[管理学-管理科学与工程(可授管理学、工学学位)] 08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：programming: integer nonlinear convex constraints computational analysis 

摘      要：Motivated by addressing probabilistic 0-1 programs we study the conic quadratic knapsack polytope with generalized upper bound (GUB) constraints. In particular, we investigate separating and extending GUB cover inequalities. We show that, unlike in the linear case, determining whether a cover can be extended with a single variable NP-hard. We describe and compare a number of exact and heuristic separation and extension algorithms which make use of the structure of the constraints. Computational experiments are performed for comparing the proposed separation and extension algorithms. These experiments show that a judicious application of the extended GUB cover cuts can reduce the solution time of conic quadratic 0-1 programs with GUB constraints substantially.