Polyhedral combinatorics of the cardinality constrained quadratic knapsack problem and the quadratic selective travelling salesman problem
Data(s) |
01/06/2006
|
---|---|
Resumo |
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.<br /> |
Identificador | |
Idioma(s) |
eng |
Publicador |
Springer-Verlag |
Relação |
http://dro.deakin.edu.au/eserv/DU:30003902/n20061222.pdf http://dx.doi.org/10.1007/s10878-006-8462-5 |
Direitos |
2006, Springer Science+Business Media, LLC |
Palavras-Chave | #quadratic knapsack #quadratic selective travelling salesman #polyhedral analysis #facets |
Tipo |
Journal Article |