Article ID: | iaor2007465 |
Country: | Netherlands |
Volume: | 11 |
Issue: | 4 |
Start Page Number: | 421 |
End Page Number: | 434 |
Publication Date: | Jun 2006 |
Journal: | Journal of Combinatorial Optimization |
Authors: | Mak Vicky, Thomadsen Tommy |
Keywords: | programming: markov decision |
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.