Polyhedral combinatorics of the cardinality constrained quadratic knapsack problem and the quadratic selective travelling salesman problem

Vicky Mak, Tommy Thomadsen

    Research output: Contribution to journalJournal articleResearchpeer-review

    Abstract

    This paper considers the cardinality constrained quadratic knapsack problem (QKP) and the quadratic selective travelling salesman problem (QSTSP). The QKP is a generalization of the knapsack problem and the QSTSP is a generalization of the travelling salesman problem. Thus, both problems are NP hard. The QSTSP and the QKP can be solved using branch-and-cut methods. Good bounds can be obtained if strong constraints are used. Hence it is important to identify strong or even facet-defining constraints. This paper studies the polyhedral combinatorics of the QSTSP and the QKP, i.e. amongst others we identify facet-defining constraints for the QSTSP and the QKP, and provide mathematical proofs that they do indeed define facets
    Original languageEnglish
    JournalJournal of Combinatorial Optimization
    Volume11
    Issue number4
    Pages (from-to)421-434
    ISSN1382-6905
    Publication statusPublished - 2006

    Fingerprint

    Dive into the research topics of 'Polyhedral combinatorics of the cardinality constrained quadratic knapsack problem and the quadratic selective travelling salesman problem'. Together they form a unique fingerprint.

    Cite this