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

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

0.00 Avg rating0 Votes
Article ID: iaor20134942
Volume: 25
Issue: 3
Start Page Number: 420
End Page Number: 431
Publication Date: Jun 2013
Journal: INFORMS Journal on Computing
Authors: , ,
Keywords: heuristics
Abstract:

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 is 𝒩𝒫‐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.

Reviews

Required fields are marked *. Your email address will not be published.