File(s) under permanent embargo
Polyhedral combinatorics of the cardinality constrained quadratic knapsack problem and the quadratic selective travelling salesman problem
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.
History
Journal
Journal of combinatorial optimizationVolume
11Issue
4Pagination
421 - 434Publisher
Springer-VerlagLocation
Dordrecht, NetherlandsPublisher DOI
ISSN
1382-6905eISSN
1573-2886Language
engPublication classification
C1 Refereed article in a scholarly journalCopyright notice
2006, Springer Science+Business Media, LLCUsage metrics
Categories
No categories selectedKeywords
Licence
Exports
RefWorks
BibTeX
Ref. manager
Endnote
DataCite
NLM
DC