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

Alper Atamtürk, Laurent Flindt Muller, David Pisinger

    Research output: Contribution to journalJournal articleResearchpeer-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 languageEnglish
    JournalI N F O R M S Journal on Computing
    Volume25
    Issue number3
    Pages (from-to)420-431
    ISSN1091-9856
    DOIs
    Publication statusPublished - 2013

    Keywords

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

    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