You can model this problem as mixed integer linear programming, with a binary decision variable that indicates whether each group-subject-area is assigned. It turns out that the resulting problem is totally unimodular, which means that you can instead solve the linear programming relaxation and still get integer values for the variables. The following PROC OPTMODEL code illustrates four alternatives, but you need only one SOLVE statement:
proc optmodel;
/* declare parameters and read data */
set <num,str> GROUPS_AREAS;
num n {GROUPS_AREAS};
read data lib.have_constraints into GROUPS_AREAS=[group area] n;
set <num,num,str> GROUPS_SUBJECTS_AREAS;
num distance {GROUPS_SUBJECTS_AREAS};
read data lib.have into GROUPS_SUBJECTS_AREAS=[group subject area] distance;
set GROUPS_SUBJECTS = setof {<g,s,a> in GROUPS_SUBJECTS_AREAS} <g,s>;
/* declare variables */
/* Assign[g,s,a] = 1 if group g and area a is assigned subject s; 0 otherwise */
var Assign {GROUPS_SUBJECTS_AREAS} binary;
/* declare objective */
min TotalDistance = sum {<g,s,a> in GROUPS_SUBJECTS_AREAS} distance[g,s,a] * Assign[g,s,a];
/* declare constraints */
con OneAreaPerGroupSubject {<g,s> in GROUPS_SUBJECTS}:
sum {<(g),(s),a> in GROUPS_SUBJECTS_AREAS} Assign[g,s,a] = 1;
con CardinalityPerGroupArea {<g,a> in GROUPS_AREAS}:
sum {<(g),s,(a)> in GROUPS_SUBJECTS_AREAS} Assign[g,s,a] = n[g,a];
/* call MILP solver */
solve;
/* call MILP solver with decomposition algorithm */
solve with milp / decomp=(method=concomp);
/* call LP solver */
solve relaxint;
/* call LP solver with network simplex algorithm */
solve relaxint with lp / algorithm=ns;
/* create output data */
create data lib.want from [group subject area]={<g,s,a> in GROUPS_SUBJECTS_AREAS: Assign[g,s,a].sol > 0.5} distance;
quit;
You can also model this problem as minimum-cost network flow and use the network solver with the MINCOSTFLOW option:
proc optmodel;
/* declare parameters and read data */
set <num,str> GROUPS_AREAS;
num n {GROUPS_AREAS};
read data lib.have_constraints into GROUPS_AREAS=[group area] n;
set <num,num,str> GROUPS_SUBJECTS_AREAS;
num distance {GROUPS_SUBJECTS_AREAS};
read data lib.have into GROUPS_SUBJECTS_AREAS=[group subject area] distance;
set GROUPS_SUBJECTS = setof {<g,s,a> in GROUPS_SUBJECTS_AREAS} <g,s>;
/* construct bipartite network */
num numNodes init 0;
set NODES = 1..numNodes;
num group {NODES};
num subject {NODES} init .;
str area {NODES} init '';
num supply {NODES};
num nodeId_g_s {GROUPS_SUBJECTS};
num nodeId_g_a {GROUPS_AREAS};
for {<g,s> in GROUPS_SUBJECTS} do;
numNodes = numNodes + 1;
group[numNodes] = g;
subject[numNodes] = s;
supply[numNodes] = 1;
nodeId_g_s[g,s] = numNodes;
end;
for {<g,a> in GROUPS_AREAS} do;
numNodes = numNodes + 1;
group[numNodes] = g;
area[numNodes] = a;
supply[numNodes] = -n[g,a];
nodeId_g_a[g,a] = numNodes;
end;
set <num,num> ARCS init {};
num weight {ARCS};
for {<g,s,a> in GROUPS_SUBJECTS_AREAS} do;
ARCS = ARCS union {<nodeId_g_s[g,s],nodeId_g_a[g,a]>};
weight[nodeId_g_s[g,s],nodeId_g_a[g,a]] = distance[g,s,a];
end;
num flow {ARCS};
/* call network solver */
solve with network / mincostflow
direction=directed nodes=(lower=supply) links=(weight=weight) out=(flow=flow);
/* create output data */
create data lib.want from [from to]={<from,to> in ARCS: flow[from,to] > 0.5}
group[from] subject[from] area[to] distance=weight;
quit;
In SAS Viya, because you have a separate problem for each group, you could also use the BY statement in PROC OPTNETWORK (with MINCOSTFLOW) or the groupBy parameter in the runOptmodel action.
