Polyhedral combinatorics of the cardinality constrained quadratic knapsack problem and the quadratic selective travelling salesman problem
In: Journal of combinatorial optimization, Jg. 11 (2006), Heft 4, S. 421-434
Online
academicJournal
- print, 18 ref
Zugriff:
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.
Titel: |
Polyhedral combinatorics of the cardinality constrained quadratic knapsack problem and the quadratic selective travelling salesman problem
|
---|---|
Autor/in / Beteiligte Person: | MAK, Vicky ; THOMADSEN, Tommy |
Link: | |
Zeitschrift: | Journal of combinatorial optimization, Jg. 11 (2006), Heft 4, S. 421-434 |
Veröffentlichung: | Norwell, MA: Springer, 2006 |
Medientyp: | academicJournal |
Umfang: | print, 18 ref |
ISSN: | 1382-6905 (print) |
Schlagwort: |
|
Sonstiges: |
|