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 profit 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 profit 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 profit and minimize incurred cost, and thus faces a bi-objective problem.

Cardinality of the efficient set

Let us define the node profits and edge costs as follows:

• p_i = 2ⁱ⁻¹ 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²).

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ⁿ), 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³ = 8 points.

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

Challenge 1: given a required maximum error ε, find 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.

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

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.