We consider the second-order conic equivalent of the classic knapsack polytope where the variables are subject to generalized upper bound constraints. We describe and compare a number of separation and extension algorithms which make use of the extra structure implied by the generalized upper bound constraints in order to strengthen the second-order conic equivalent of the classic cover cuts. We show that determining whether a cover can be
extended with a variable is NP-hard. Computational experiments are performed comparing the proposed separation and extension algorithms. These experiments show that applying these extended cover cuts can greatly improve solution time of second-order cone programs.
|Place of Publication||Kgs. Lyngby|
|Number of pages||20|
|Publication status||Published - 2011|
|Series||DTU Management 2011|