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

Alper Atamtürk; Laurent Flindt Muller; David Pisinger

doi:10.1287/ijoc.1120.0511

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

Alper Atamtürk, Laurent Flindt Muller, David Pisinger

Research output: Contribution to journal › Journal article › Research › peer-review

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	https://doi.org/10.1287/ijoc.1120.0511
Publication status	Published - 2013

Keywords

Application programs
Combinatorial optimization
Convex programming
Experiments
Heuristic algorithms
Integer programming
Separation

Access to Document

10.1287/ijoc.1120.0511

Fingerprint Dive into the research topics of 'Separation and Extension of Cover Inequalities for Conic Quadratic Knapsack Constraints with Generalized Upper Bounds'. Together they form a unique fingerprint.

Cite this

@article{8677bcc32cf44d9ea740a16cdaa23fd2,

title = "Separation and Extension of Cover Inequalities for Conic Quadratic Knapsack Constraints with Generalized Upper Bounds",

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. {\textcopyright} 2013 INFORMS.",

keywords = "Application programs, Combinatorial optimization, Convex programming, Experiments, Heuristic algorithms, Integer programming, Separation",

author = "Alper Atamt{\"u}rk and Muller, {Laurent Flindt} and David Pisinger",

year = "2013",

doi = "10.1287/ijoc.1120.0511",

language = "English",

volume = "25",

pages = "420--431",

journal = "I N F O R M S Journal on Computing",

issn = "1091-9856",

publisher = "Institute for Operations Research and the Management Sciences (I N F O R M S)",

number = "3",

}

TY - JOUR

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

AU - Atamtü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 -