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 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. © 2013 INFORMS.
Original language | English |
---|---|
Journal | I N F O R M S Journal on Computing |
Volume | 25 |
Issue number | 3 |
Pages (from-to) | 420-431 |
ISSN | 1091-9856 |
DOIs | |
Publication status | Published - 2013 |
Keywords
- Application programs
- Combinatorial optimization
- Convex programming
- Experiments
- Heuristic algorithms
- Integer programming
- Separation