@TECHREPORT\{IMM2003-02524,
    author       = "T. Thomadsen and T. Stidsen",
    title        = "The Quadratic Selective Travelling Salesman Problem",
    year         = "2003",
    keywords     = "Ring Networks, (Selective) Traveling Salesman Problem, Branch-and-Cut, Integer Programming",
    number       = "",
    series       = "IMM-Technical Report-2003-17",
    institution  = "Informatics and Mathematical Modelling, Technical University of Denmark, {DTU}",
    address      = "Richard Petersens Plads, Building 305, {DK-}2800 Kgs. Lyngby",
    type         = "",
    url          = "http://www2.compute.dtu.dk/pubdb/pubs/2524-full.html",
    abstract     = "A well-known extension of the Travelling Salesman Problem (TSP) is the Selective {TSP} (STSP): Each node has an associated profit and instead of visiting all nodes, the most profitable set of nodes, taking into account the tour cost, is visited. The Quadratic {STSP} (QSTSP) adds the additional complication that each pair of nodes have an associated profit which can be gained only if both nodes are visited. The {QSTSP} is a subproblem when constructing hierarchical ring networks.

We describe an integer linear programming model for the {QSTSP}. The {QSTSP} is solved by two construction heuristics and by a branch-and-cut algorithm. Computational results are presented for two budget constraints limiting the length of the ring and the number of nodes in the ring respectively. It is investigated how the tightness of the budgets affect the running time of the branch-and-cut algorithm and correspondingly how this affect the solution quality of the construction heuristics.

The construction heuristics have difficulties in finding good solutions. One heuristic is best when tight budgets are considered, the other heuristic is best when loose budgets are considered. The branch-and-cut algorithm finds the optimal solutions at a cost of much higher running time. All problems with up to 50 nodes are solved within one hour."
}