Separation and extension of cover inequalities for second-order conic knapsack constraints with GUBs

Alper Atamtürk, Laurent Flindt Muller, David Pisinger

    Research output: Book/ReportReport

    592 Downloads (Pure)

    Abstract

    We consider the second-order conic equivalent of the classic knapsack polytope where the variables are subject to generalized upper bound constraints. We describe and compare a number of separation and extension algorithms which make use of the extra structure implied by the generalized upper bound constraints in order to strengthen the second-order conic equivalent of the classic cover cuts. We show that determining whether a cover can be extended with a variable is NP-hard. Computational experiments are performed comparing the proposed separation and extension algorithms. These experiments show that applying these extended cover cuts can greatly improve solution time of second-order cone programs.
    Original languageEnglish
    Place of PublicationKgs. Lyngby
    PublisherDTU Management
    Number of pages20
    Publication statusPublished - 2011
    SeriesDTU Management 2011
    Number6

    Fingerprint

    Dive into the research topics of 'Separation and extension of cover inequalities for second-order conic knapsack constraints with GUBs'. Together they form a unique fingerprint.

    Cite this