topic Re: Assign object to a place constrained to totals in Mathematical Optimization, Discrete-Event Simulation, and OR

Assign object to a place constrained to totals

ciro — Thu, 03 Nov 2022 13:58:19 GMT

Hi,

I am not sure whether this is the right forum.

I have to assign to each object in dataset 'have1' a place of dataset 'have2' such that in the output dataset, the total number of place x group is equal to the variable 'n' in dataset 'have2'.

for each object the assignation should be random within the given constraint.

the output dataset should have the same number of observations of dataset 'have1' and be like:

object group place

172 IF 1

173 IF 5

........

any suggestion, and especially code, is greatly appreciated.

Even more appreciated would be different options (OR, datasetp, IML...)

thank you very much in advance

Re: Assign object to a place constrained to totals

RobPratt — Thu, 03 Nov 2022 17:16:56 GMT

Here's one approach that uses the MILP solver in PROC OPTMODEL:

proc optmodel;
   /* declare parameters and read data */
   set OBJECTS;
   str group {OBJECTS};
   read data have1 into OBJECTS=[object] group;

   set <str,num> GROUP_PLACE;
   num n {GROUP_PLACE};
   read data have2 into GROUP_PLACE=[group place] n;

   set OBJECT_GROUP_PLACE = {o in OBJECTS, <g,p> in GROUP_PLACE: group[o] = g};

   /* X[o,g,p] = 1 if object o is assigned to group g and place p; 0 otherwise */
   var X {OBJECT_GROUP_PLACE} binary;

   /* assign each object to exactly one group-place */
   con AssignOnce {o in OBJECTS}:
      sum {<(o),g,p> in OBJECT_GROUP_PLACE} X[o,g,p] = 1;

   /* assign correct number of objects to each group-place */
   con Cardinality {<g,p> in GROUP_PLACE}:
      sum {<o,(g),(p)> in OBJECT_GROUP_PLACE} X[o,g,p] = n[g,p];

   /* call MILP solver with no objective */
   solve noobj;

   /* create output data set */
   create data want from [object group place]={<o,g,p> in OBJECT_GROUP_PLACE: X[o,g,p].sol > 0.5};
quit;

If you had some measure of desirability of placing object o in group g and place p, you could instead maximize the total desirability rather than assigning arbitrarily.

Re: Assign object to a place constrained to totals

FreelanceReinh — Thu, 03 Nov 2022 17:21:07 GMT

Hi @ciro,

Here's an elementary approach:

/* Expand list of places */

data temp / view=temp;
call streaminit('MT64',27182818);
set have2;
do n=1 to n;
  r=rand('uniform');
  output;
end;
run;

/* Sort list of places randomly within groups */

proc sort data=temp out=places(keep=place);
by group r;
run;

/* Assign objects to groups (HAVE1 must be sorted by GROUP!) */

data want;
merge have1 places;
run;

/* Optional: Verify the constraint */

proc freq data=want noprint;
tables place*group / out=chk(drop=percent) sparse;
run;

proc compare data=have2(rename=(n=count)) c=chk method=absolute;
run;

Note that 20 of the 48 values of variable N in dataset HAVE2 are not exact integers (but close enough so that the DO loop in the first step works correctly).