Informatica 39 (2015 ) 257-260 2 57 Inter Programming Models for the Target Visitation Problem Achim Hildenbrandt and Gerhard Reinelt Institut für Informatik, Universität Heidelberg, Im Neuenheimer Feld 368 D-69120 Heidelberg, Germany Keywords: target visitation problem, programming models Received: July 25, 2014 The target visitation problem (TVP) is concerned with finding a route to visit a set of targets starting from and returning to some base. In addition to the distance traveled a tour is evaluated by taking also preferences into account which address the sequence in which the targets are visited. The problem thus is a combination of two well-known combinatorial optimization problems: the traveling salesman and the linear ordering problem. In this paper we point out some polyhedral properties and develop a branch-and-cut algorithm for solving the TVP to optimality. Some computational results are presented. Povzetek: Prispevek obravnava iskanje poti v grafu, kjer je potrebno obiskati vec ciljev v najboljšem vrstnem redu. 1 Introduction Let Dn+1 = (Vn+i, An+i) be the complete digraph on n +1 nodes where we set Vn+1 = {0,1,..., n}. Furthermore let two types of arc weights be defined: weights dj (distances) for every arc (i,j), 0 < i, j < n, and weights pij (preferences) associated with every arc (i, j), 1 < i, j < n. The target visitation problem (TVP) consists of finding a Hamiltonian tour starting at node 0 visiting all remaining nodes (called targets) exactly once in some order and returning to node 0. Every tour can be represented by a permutation n of {1,2,..., n} where n(i) = j if target j is visited as i-th target. For convenience we also define n(0) = 0 and n(n + 1) = 0. So we are essentially looking for a traveling salesman tour, but for the TVP the profit of a tour depends on the two weights. Namely, the value of a tour is the sum of pairwise preferences between the targets corresponding to their visiting sequence minus the sum of distances traveled, i.e., it is calculated as n —1 n n pn(i)n(j) dn(i)n(i+1), i=1 j=i+1 i=0 and the task is to find a tour of maximum value. So we have a multicriteria objective function. The TVP was introduced in [4] and combines two classical combinatorial optimization problems: the asymmetric traveling salesman problem (ATSP) asking for a shortest Hamiltonian tour and the linear ordering problem (LOP) which is to find an acyclic tournament of maximum weight. (There is an obvious 1-1 correspondence between acyclic tournaments and linear orders of the node). Computational results of a genetic algorithm for problem instances with up to 16 targets have been reported in [1]. The original application of the TVP is the planning of routes for UAVs (un- armed aerial vehicles). But there is a wide field of applications, e.g. the delivery of relief supplies or any other routing problem where additional preferences should be considered (town cleaning, snow-plowing service, etc.). Obviously, the TVP is NP-hard because it contains the traveling salesman problem (p = 0) and the linear ordering problem (d = 0) as special cases. In this paper we present first polyhedral results for the TVP and develop an algorithm for solving it to optimality. In section 2 we introduce an integer programming model. Section 3 discusses some structural properties of the associated polytope. A branch-and-cut algorithm based on these results is described in section 4. The algorithm is then applied to a set of benchmark problems and the computational results are presented in section 5. A few remarks conclude the paper. 2 An integer programming model for the TVP For convenience we first transform the problem to a Hamil-tonian path problem and also get rid of the special base node. This transformation is well-known for the ATSP [7] and can be adapted for the TVP as follows. The key idea is to exploit the fact that each tour has to start at the base and return to it and that no preferences are to be taken into account for the base. In the TVP-path model we leave out this node and just search for a Hamil-tonian path which visits all targets exactly once. Following [7] we make the following modifications. (i) Transform the distance matrix by setting dj = dij -di0 - d0j, for all pairs i and j of nodes, 1 < i, j < n i = j. 258 Informatica 39 (2015 ) 257-260 A. Hildenbrandt et al. (ii) Change the computation of the distance part of the objective function to Xij € {0,1}, 1 < i, j < n, i = j (9) n-1 E d n(i)n(i+1) - ^ di0 1 i=1 -E di0 -E' laX E Z^ij Wij - Z di i=1j = 1 i=1j=1 j=i j=i n n YjYjxij =n -1, i=1 j=1 j=i EE Xij 2 nodes. W.l.o.g. we can assume that the node set is {1, 2,..., k} and the subtour is given as {(1, 2), (2,3),..., (k - 1, k), (k, 1)}. Hence X12 = X23 = ... = Xk-1,k = Xk1 = 1, implying because of (8) that W12 = W23 = ... = Wk-1,k = Wk1 = 1. This is a contradiction to the requirement that the w-variables represent an acyclic tournament. So we can eliminate the exponentially many constraints (3) and obtain a TVP formulation with a polynomial number (cubic in n) of constraints. For our algorithm it will be useful to calculate the position of a node i in the path. This can easily be done using Inter Programming Models for the Target. Informatica 39 (2015 ) 257-260 259 the LOP variables. The value n - J2 wij gives the position 3 = 1 of node i. Note that because of the tournament equations we can substitute an LOP variable wij, j > i, by 1 - w^. Now the 3-dicycle inequalities are turned into 1 > + wjk - wik > 0 for all 1 < i < j < k < n and the part of the objective function for the LOP variables reads EL-! En=i+i[(pij -Pji)wij + pji]. 2.1 Extended formulation of the basic model The use of extended formulations is a common technique with is used to strengthen the LP Formulation of a combinatorial optimization problem. The key idea of this approach is to add new variables and constraints to a given IP formulation so that the gap between the solution of the LP relaxation and the optimal integral solution becomes much smaller. In the case of TVP we can obtain an extended formulation for the TVP by adding three-indexed variables, which are a generalization of the linear ordering variables to the standard model. In detail this new variables wij k are than defined as follows: S Ç {1, .. .,n}, 2 < |S| < n - 1, Wij + Wjk + Wki < 2, 1 < i, j, k < n, i < j, i < kj = k, Wij + Wjik + Wjki + Wkji = 1 1 < i, j, k < n, i < j Xij - Wijk - Wkij < 0 1 < i, j, k < n, i < j Xij - Wij < 0, 1 < i, j < n, ij G{0,1}, 1 < i,j < G{0,1}, 1 < i,j < Wijk € {0, 1}, 1 < i, j, k < n. (15) (16) (17) (18) (19) (20) (21) (22) 3 The edge-node-formulation The key idea of the next model is to combine the w and x variables of the -Model to new three index variables which states the relation between a node n and an fixed edge (i, j). More precisely we define: Wj0- := 1 if k = n(a), i = n(b) and j = n(b + 1) for some 1 < a < b < n — 1 , ^ 0 otherwise. and analogously : 1 if i = n(a), j = n(b) and k = n(c) Wijk := \ for some 1 < a < b < c < n - 1 , ^ 0 otherwise. So as one see this new type of variables is a straight forward extension of the wij -variables. In the objective function we assign zero coefficients to the new variables. In order to extend our standard model we also need to introduce two new classes of constraints to make sure that the solution of the new variables match with the old Xij and Wij variables. In detail the extended formulation looks a follows: 1 if i = n(a), j = n(a + 1) and k = n(b) n n n n max mm pij Wij- mm dij xij i=i j=i i=i j=i j=i j=i s.t. nn mmxij=n -1, i=1 j=1 j=i xij < 1, 1 < j < n, i=i n xij < 1 , 1 < i < n, (11) (12) (13) (14) j=i mm xij