In this paper, we studied the polyhedra of the Quadratic Knapsack Problem and the Quadratic Selective Travelling Salesman Problem. For each of these poly-topes, we established its dimension, identified a number of strong constraints, and proved that these constraints are indeed facet-defining cuts. Various math-ematical techniques were used in proving these results.
These results are of great significance in the implementation of a branch-and-cut method for obtaining exact solutions. The benefit of using such facet-defining cuts is that it improves the quality of the linear programming relaxation bounds.
Bibliography
[1] Balas, E.(1989) The prize collecting traveling salesman problem.Networks 19621–636
[2] Balas, E.(1995) The prize collecting traveling salesman problem. II. Poly-hedral results.Networks25199–216
[3] Bauer, P. (1997) The circuit polytope: Facets.Mathematics of Operations Research22110–145
[4] Bauer, P., Linderoth J.T., Savelsbergh M.W.P. (2002) A branch and cut approach to the cardinality constrained circuit problem.Mathematical Pro-gramming Ser. A91307–348
[5] Billionnet, A., Calmels, F.(1996) Linear programming for the 0-1 quadratic knapsack problem.European Journal of Operational Research92 310–325
57
[6] Caprara, A., Pisinger, D., Toth, P.(1999) Exact solution of the quadratic knapsack problem.INFORMS Journal on Computing11125–137
[7] Erkut, E. (1990) Discretep-dispersion problem. European Journal of Op-erational Research16 48–60
[8] Fischetti, M., Salazar Gonzalez, J.J., Toth, P.(1995) The symmetric gener-alized traveling salesman polytope.Networks26113–123
[9] Fischetti, M., Salazar Gonzalez, J.J., Toth, P.(1997) A branch-and-cut algo-rithm for the symmetric generalized traveling salesman problem.Operations Research45378–394
[10] Fischetti, M., Salazar Gonzalez, J.J., Toth, P.(1998) Solving the Orienteer-ing Problem through Branch-and-Cut. INFORMS Journal on Computing 10133–148
[11] Gendreau, M., Labbe, M., Laporte, G. (1995) Efficient heuristics for the design of ring networks.Telecommunication Systems - Modeling, Analysis, Design and Management4177–188
[12] Gendreau, M., Laporte, G., Semet, F. (1998) A branch-and-cut algorithm for the undirected selective traveling salesman problem.Networks32263–
273
[13] Gouveia, L., Manuel Pires, Jose(2001) Models for a Steiner ring network design problem with revenues. European Journal of Operational Research 13321–31
[14] Gr¨otschel, M., Padberg, M.W. (1985) “Polyhedral Theory” in E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan, D.B. Shmoys,The Travelling Salesman ProblemWiley
[15] Johnson, E.L., Mehrotra, A., Nemhauser, G.L.(1993) Min-cut clustering.
Mathematical Programming62133–151
[16] Laporte, G., Martello, S.(1990) The selective travelling salesman problem.
Discrete Applied Mathematics26193–207
[17] Nemhauser, G.L., Wolsey, L.A. (1998) Integer and Combinatorial Opti-mizationWiley.
[18] Pisinger, D.(1999) Exact Solution of “p”-dispersion Problems. DIKU-rapport 99/14
[19] Stidsen, T., Thomadsen, T. Optimal Design of Hierarchical Ring Networks using Branch-and-Price.Work in progress.
58
Appendix B
A Branch-and-Cut Algorithm for the Quadratic Selective Travelling Salesman Problem
Submitted forTelecommunication Systems
60 Appendix B
A Branch-and-Cut Algorithm for the Quadratic Selective Travelling Salesman Problem
Tommy Thomadsen1and Thomas Stidsen2
Abstract
A well-known extension of the Travelling Salesman Problem (TSP) is the Selective TSP (STSP). In the STSP, each node has an associated revenue and instead of visiting all nodes, the most profitable nodes, taking the travelling costs into account, are visited. The Quadratic STSP (QSTSP) possesses the additional complication that a revenue is associated with each pair of nodes, which can be gained only if both nodes are visited. The QSTSP resemble ring network design and is a subproblem when designing hierarchical ring networks.
We describe an integer linear programming model for the QSTSP. The QSTSP is solved both by applying two construction heuristics and by applying a branch-and-cut algorithm.
Computational results are presented for two types of budget constraints limiting the length of the ring and the number of nodes in the ring, respectively. In addition, more or less restrictive budgets are considered.
The construction heuristics are fast, but obtain solutions which are far from optimal. One heuristic is best when restrictive budgets are consid-ered, the other heuristic is best when ample budgets are considered. The branch-and-cut algorithm determines optimal solutions at much higher computation times than the heuristics. The computation time depends on the budget and is highest for budgets that are neither ample nor restrictive. All problems with up to 50 nodes are solved within one hour of computation time.
Keywords: Ring Networks, (Selective) Traveling Salesman Problem, Branch-and-Cut, Integer Programming
1Informatics and Mathematical Modelling, Technical University of Denmark, Lyngby, Den-mark. Email: tt@imm.dtu.dk
2Informatics and Mathematical Modelling, Technical University of Denmark, Lyngby, Den-mark. Email: tks@imm.dtu.dk
B.1 Introduction 61
B.1 Introduction
When building telecommunication networks, the ring topology is widely used due to its inherent single link/node breakdown protection and its simple and fast restoration scheme. When a service provider chooses to build a ring, it is of major importance to build a ring which affords a good tradeoff between the revenue obtained and the node- and link-costs of building the ring. The ring should also be implementable in the technology chosen, e.g. the number of nodes and/or the length of the ring may be limited due to transmission delay.
Single-ring design can be generalized to multi-ring design where the service provider is contracted to provide service to a set of customers using one or more rings. In that case the same tradeoff as for single-ring design is apparent, but for more rings at the same time. Evaluating the quality of single rings is a good start when evaluating such multi-ring designs. In particular one could imagine generating a set of potentially good rings and choosing a subset of those which covers all customers.
The single-ring design can be seen as an extension to the classical Travelling Salesman Problem (TSP) and it has been termed, both the Orienteering prob-lem, Prize collecting TSP, and Selective TSP (STSP). We will use the term STSP. In the STSP, a revenue is associated with each customer and the idea is then to establish a good tradeoff between the design cost and the revenue obtained for including nodes in the ring. The STSP is studied in e.g. [2], [3], [9], [11], and [12]. A related problem is the Generalized TSP (GTSP) which is considered in [6] and [7]. In GTSP the set of nodes is divided into disjoint subsets denoted clusters and the shortest ring which passes at least one node in each cluster must be determined.
The most notable difference between the different versions of the STSP and the GTSP is how the size of the ring is limited. The limit may be a minimum size or a maximum size determined directly or indirectly. Some of the possibilities, which are sometimes combined are: 1) A tradeoff in design cost and revenue collected, i.e. both the design cost and the revenue are present in the objective [2, 3]; 2) A lower bound on the revenue collected [2, 3]; 3) An upper bound on the design cost [9, 11, 12]; and 4) Controlled by clusters of nodes as in GTSP [6, 7].
Another notable difference between the STSP and the GTSP is whether a par-ticular node, usually denoted the depot, is required to be in the ring [9, 11, 12]
or not [2, 3, 6, 7]. In [9], a non-empty subset of nodes is required to be in the ring. Finally GTSP [6, 7] falls a bit out of category. Here, a set of clusters of nodes are given, and for each of the clusters one node in the cluster has to be
62 Appendix B
in the ring, but which node is to be determined.
The Quadratic STSP (QSTSP) possesses the additional complication that a revenue is associated with each pair of nodes, which can be gained only ifboth nodes are in the ring. The QSTSP is considered in [8] and [10]. In [8] a model for the QSTSP with quadratic objective is presented and heuristics are developed and tested. The size of the ring is controlled by an upper limit on the design cost combined with a tradeoff in the objective between the design cost and the revenue associated with each pair of nodes. No nodes are required to be in the ring. In [10] alternative models for the QSTSP are considered. The size of the ring is controlled by a bound on the number of nodes in the ring and also some nodes are required to be in the ring. Three integer linear models are evaluated by solving test instances with up to 80 nodes using Cplex. For the test instances, all pairs of nodes have a demand, but only a fixed number of the shortest edges are considered. For the largest instances with 80 nodes, only the 200 shortest edges are considered. Some instances cannot be solved within 24 hours. Finally [13] presents a polyhedral study of the QSTSP.
We present an integer linear programming model for the QSTSP and suggest a branch-and-cut algorithm. Given the similarities with the GTSP, cuts and corresponding separation-routines in [7] have been found very useful.
The outline of the paper is as follows. We present the model for the QSTSP in Section B.2. In Section B.3 we describe the branch-and-cut algorithm and in Section B.4 we describe two construction heuristics. In Section B.5 we test the algorithms with two budget constraints limiting the length of the ring and the number of nodes in the ring respectively. Finally we give conclusions in Section B.6.