# Example: TSPP

# The Traveling Salesman Problem with Profits (TSPP) is a BOCO problem that can be described as follows: let G = (V, E) be a complete undirected graph, with V = {0, 1, . . . , n} the set of nodes, and E the set of edges. Let p_{i} be the proﬁt of node i, and let c_{e} be the cost of edge e ∈ E. A service carrier, starting from node 0 may visit any subset of nodes. Visiting a subset S of nodes implies a proﬁt p(S) = ∑_{i∈S} p_{i}, and a cost c(S) which is the cost of a shortest Hamiltonian tour among the nodes in S. The carrier wishes to maximize collected proﬁt and minimize incurred cost, and thus faces a bi-objective problem.

_{i}be the proﬁt of node i, and let c

_{e}be the cost of edge e ∈ E. A service carrier, starting from node 0 may visit any subset of nodes. Visiting a subset S of nodes implies a proﬁt p(S) = ∑

_{i∈S}p

_{i}, and a cost c(S) which is the cost of a shortest Hamiltonian tour among the nodes in S. The carrier wishes to maximize collected proﬁt and minimize incurred cost, and thus faces a bi-objective problem.

**Cardinality of the efficient set**

Let us deﬁne the node proﬁts and edge costs as follows:

- p
_{i}= 2^{i−1}for all i = 0, 1, . . . , n; - c
_{ij}= 2^{j−1}for all (i, j) ∈ E with i < j.

Notice that the input size of the instance is O(n^{2}).

It is not hard to see that with this choice of profits and costs every subset of nodes containing the depot 0 correspond to a Pareto optimal solution and thus to an efficient point in the objective space. It follows that the cardinality of the efficient frontier is O(2^{n}), clearly exponential in the input size.

When n = 3, the instance can be depicted as follows. On the left, the blue figures are costs and the red ones are profits. On the right, the efficient set is plotted in the objective space.

Notice that the efficient set is composed by 2^{3} = 8 points.

We shall illustrate on this example the two tasks mentioned in CONCEPTS AND CHALLENGES.

**Challenge 1: given a required maximum error ε, ﬁnd a Pareto ε-approximation of minimum cardinality**

In the following picture, red points form Pareto 1.50-approximation of the efficient set; shaded rectangles show regions of the objective space approximated by red points. On the left, we have an approximation with cardinality 3. Notice that the approximation is minimal, in the sense that if we remove any point we have no more a valid approximation. However, there is also 1.50-approximation with cardinality 2, shown on the right.

Consider the following picture. On the left, we have a Pareto 0.50-approximation with cardinality 4. Again, the approximation is minimal: we cannot remove any point. Furthermore, 0.50 is the minimum error such that these 4 points form an ε-approximation. However, on the right we see that with 4 efficient points it is possible to get a Pareto 0.25-approximation of the whole efficient set.

**Challenge 2: given a maximum cardinality M, find a Pareto ε-approximation of cardinality M such that ε is minimum**