Deakin home > Deakin University Library > Deakin Research Online > Polyhedral combinatorics of the cardinality constrained quadratic knapsack problem and the quadratic selective travelling salesman problem

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

Mak, Vicky and Thomadsen, Tommy 2006, Polyhedral combinatorics of the cardinality constrained quadratic knapsack problem and the quadratic selective travelling salesman problem, Journal of combinatorial optimization, vol. 11, no. 4, pp. 421-434.

Attached Files (Some files may be inaccessible until you login with your Deakin Research Online credentials)
Name Description MIMEType Size Downloads

Title Polyhedral combinatorics of the cardinality constrained quadratic knapsack problem and the quadratic selective travelling salesman problem
Author(s) Mak, Vicky
Thomadsen, Tommy
Journal name Journal of combinatorial optimization
Volume number 11
Issue number 4
Start page 421
End page 434
Publisher Springer-Verlag
Place of publication Dordrecht, Netherlands
Publication date 2006-06
ISSN 1382-6905
1573-2886
Keyword(s) quadratic knapsack
quadratic selective travelling salesman
polyhedral analysis
facets
Summary 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.
Language eng
Field of Research 010206 Operations Research
HERDC Research category C1 Refereed article in a scholarly journal
Copyright notice ©2006, Springer Science+Business Media, LLC
Persistent URL http://hdl.handle.net/10536/DRO/DU:30003902

Document type: Journal Article
Collection: School of Engineering and Information Technology
Connect to link resolver
 
Unless expressly stated otherwise, the copyright for items in Deakin Research Online is owned by the author, with all rights reserved.

Versions
Version Filter Type
Citation counts: TR Web of Science Citation Count  Cited 1 times in TR Web of Science
Scopus Citation Count Cited 1 times in Scopus
Access Statistics: 366 Abstract Views, 0 File Downloads  -  Detailed Statistics
Created: Mon, 07 Jul 2008, 09:06:27 EST