1 Operations Research, Department of Management Engineering, Technical University of Denmark2 Department of Management Engineering, Technical University of Denmark
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.