TY - RPRT
T1 - Facets for the Cardinality Constrained Quadratic Knapsack Problem and the Quadratic Selective Travelling Salesman Problem
AU - Mak, Vicky
AU - Thomadsen, Tommy
PY - 2004
Y1 - 2004
N2 - A well-known extension of the Travelling Salesman Problem (TSP) is the Selective (or Prize-collecting) TSP: In addition to the edge-costs, each node has an associated reward (denoted the node-reward) and instead of visiting all nodes, only profitable nodes are visited. The Quadratic Selective TSP (QSTSP) has the additional complications: (1) each pair of nodes have an associated reward (denoted the edge-reward) which can be gained only if both nodes are visited; and (2) a constraint on the number of nodes selected is imposed, which we refer to as the cardinality constraint. The objective of an QSTSP is to maximize the total node-reward and edge-rewards gained minus the edge-costs incurred subject to the satisfaction of the cardinality constraint.
AB - A well-known extension of the Travelling Salesman Problem (TSP) is the Selective (or Prize-collecting) TSP: In addition to the edge-costs, each node has an associated reward (denoted the node-reward) and instead of visiting all nodes, only profitable nodes are visited. The Quadratic Selective TSP (QSTSP) has the additional complications: (1) each pair of nodes have an associated reward (denoted the edge-reward) which can be gained only if both nodes are visited; and (2) a constraint on the number of nodes selected is imposed, which we refer to as the cardinality constraint. The objective of an QSTSP is to maximize the total node-reward and edge-rewards gained minus the edge-costs incurred subject to the satisfaction of the cardinality constraint.
KW - Quadratic Knapsack; Quadratic Selective Travelling Salesman; Polyhedral Analysis; Facets
M3 - Report
BT - Facets for the Cardinality Constrained Quadratic Knapsack Problem and the Quadratic Selective Travelling Salesman Problem
PB - Informatics and Mathematical Modelling, Technical University of Denmark, DTU
ER -