Here's one way, iterating between the MILP solver and the network (TSP) solver in a loop with PROC OPTMODEL. The master MILP problem prescribes which nodes to visit, and the TSP subproblem determines whether those nodes can be visited within the allotted time (or distance).
proc optmodel printlevel=0;
/* declare parameters and read data */
set NODES;
num x {NODES};
num y {NODES};
num score {NODES};
str name {NODES};
read data indata into NODES=[_N_] x y score name;
set ARCS = {i in NODES, j in NODES diff {i}};
num source;
for {i in NODES: score[i] = 0} do;
source = i;
leave;
end;
num distance {<i,j> in ARCS} =
(if j = source then 0 else sqrt((x[i]-x[j])^2+(y[i]-y[j])^2));
/* declare optimization model */
var UseNode {NODES} binary;
max TotalScore = sum {i in NODES} score[i] * UseNode[i];
num numsols init 0;
set SOLS = 1..numsols;
set NODES_s {SOLS};
con ExcludeSol {s in SOLS}:
sum {i in NODES_s[s]} UseNode[i] <= card(NODES_s[s]) - 1;
fix UseNode[source] = 1;
/* declare parameters used by network solver */
set TSP_NODES = {i in NODES: UseNode[i].sol > 0.5};
set <num,num> TOUR;
/* row generation loop */
do while (1);
/* call MILP solver */
put 'Solving MILP master...';
solve;
put TSP_NODES=;
/* call network (ATSP) solver */
put 'Solving ATSP subproblem...';
solve with network / TSP graph_direction=directed
subgraph=(nodes=TSP_NODES) links=(weight=distance) out=(tour=TOUR);
put TOUR=;
/* check feasibility and either exit loop or include new row */
if _NETWORK_OBJECTIVE_.sol <= &distance_budget then leave;
else do;
numsols = numsols + 1;
NODES_s[numsols] = TSP_NODES;
end;
end;
quit;
This version uses Euclidean distance, except that the distance back to the source node is 0.
... View more
