Separation and extension of cover inequalities for second-order conic knapsack constraints with GUBs

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.