Polyhedral combinatorics of the cardinality constrained quadratic knapsack problem and the quadratic selective travelling salesman problem |
| |
Authors: | Vicky Mak Tommy Thomadsen |
| |
Institution: | (1) School of Information Technology, Deakin University, Australia;(2) Informatics and Mathematical Modelling, Technical University of Denmark, Lyngby, Denmark |
| |
Abstract: | 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.
Author now works at Motorola. (2005 onwards) |
| |
Keywords: | Quadratic knapsack Quadratic selective travelling salesman Polyhedral analysis Facets |
本文献已被 SpringerLink 等数据库收录! |