Abstract
| 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
Cite this
}
Separation and Extension of Cover Inequalities for Conic Quadratic Knapsack Constraints with Generalized Upper Bounds. / Atamtürk, Alper; Muller, Laurent Flindt; Pisinger, David.
In: I N F O R M S Journal on Computing, Vol. 25, No. 3, 2013, p. 420-431.Research output: Contribution to journal › Journal article › Research › peer-review
TY - JOUR
T1 - Separation and Extension of Cover Inequalities for Conic Quadratic Knapsack Constraints with Generalized Upper Bounds
AU - Atamtürk, Alper
AU - Muller, Laurent Flindt
AU - Pisinger, David
PY - 2013
Y1 - 2013
N2 - 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.
AB - 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.
KW - Application programs
KW - Combinatorial optimization
KW - Convex programming
KW - Experiments
KW - Heuristic algorithms
KW - Integer programming
KW - Separation
U2 - 10.1287/ijoc.1120.0511
DO - 10.1287/ijoc.1120.0511
M3 - Journal article
VL - 25
SP - 420
EP - 431
JO - I N F O R M S Journal on Computing
JF - I N F O R M S Journal on Computing
SN - 1091-9856
IS - 3
ER -