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

    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. {\circledC} 2013 INFORMS.",
    keywords = "Application programs, Combinatorial optimization, Convex programming, Experiments, Heuristic algorithms, Integer programming, Separation",
    author = "Alper Atamtü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",

    }

    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 journalJournal articleResearchpeer-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 -