# Prize-collecting / orienteering tour
#
# Chooses which customers are worth visiting as well as the order. The
# degree constraints are equalities against y_i rather than against 1, so a
# skipped node has no arcs at all; that single change turns a routing
# problem into a selection-and-routing problem.
#
# Technique: Visiting is optional — a per-node binary y_i gates its degree
# constraints, and the objective trades collected prize against
# travel.
#
# On this instance the optimum is 25 (maximisation), confirmed
# independently by exhaustive enumeration before publication.
#
# Reference: Balas, E. (1989). The prize collecting traveling salesman
# problem. Networks 19(6), 621–636.
model m
set V = {1, 2, 3, 4}
set C = {2, 3, 4}
const c = {{0, 6, 12, 1},
{6, 0, 10, 4},
{12, 10, 0, 2},
{1, 4, 2, 0}}, forall i in V, forall j in V
const p = {0, 19, 11, 14}, forall i in V
const N = 4
bin x, forall i in V, forall j in V
bin y, forall i in V
int 1 <= u <= 4, forall i in V
# prize collected, less the distance travelled
max sum_{i in C}{p_{i} * y_{i}} - sum_{i in V}{sum_{j in V setminus {i}}{c_{i,j} * x_{i,j}}}
# a node has one in-arc and one out-arc exactly when it is visited
constr sum_{i in V setminus {j}}{x_{i,j}} = y_{j}, forall j in C
constr sum_{j in V setminus {i}}{x_{i,j}} = y_{i}, forall i in C
# the tour leaves and returns to the depot once, if it goes anywhere
constr sum_{j in C}{x_{1,j}} = y_{1}
constr sum_{i in C}{x_{i,1}} = y_{1}
constr y_{j} <= y_{1}, forall j in C
constr u_{i} - u_{j} + N * x_{i,j} <= N - 1, forall i in C, forall j in C setminus {i}
end
import elytica
Read this through MCP: read with path: "formulations/prize-collecting-tsp", or resource hlpl://formulations/prize-collecting-tsp.