BookmarkSubscribeRSS Feed
🔒 This topic is solved and locked. Need further help from the community? Please sign in and ask a new question.
PaalNavestad
Pyrite | Level 9

Hi, I'm struggling to formulate/program an assignment problem. In real life the problem is filling an Emergency preparedness crew. 

The problem can be described as follows:

Assume that yo have 5 workers P1..P5. These shall be assigned the roles A,B,C,D

P1  can fill A and B, P2 can fill B,C,D, P3 can fill C, P4 can fill A,B,D and P5 can fill A,B,C,D.

If you are assigned Role A you cannot be assigned any other role. If you are assigned role B You cannot fill role C. 

For Role A you need 1 person, For Roles B, C and D you need 2 persons. 

I'm struggling to get a decent formulation for the problem. I can express all assignements explicitly but struggle to find the right combinations. 

 

Can somebody please give me some ideas on how to get the problem formulated?

1 ACCEPTED SOLUTION

Accepted Solutions
RobPratt
SAS Super FREQ

Hi, Paal.  Here's one way:

data indata;
   input worker $ role $;
   datalines;
P1 A
P1 B
P2 B
P2 C
P2 D
P3 C
P4 A
P4 B
P4 D
P5 A
P5 B
P5 C
P5 D
;

proc optmodel;
   set <str,str> WORKERS_ROLES;
   read data indata into WORKERS_ROLES=[worker role];
   set WORKERS = setof {<w,r> in WORKERS_ROLES} w;
   set ROLES = setof {<w,r> in WORKERS_ROLES} r;
   
   /* Assign[w,r] = 1 if worker w is assigned to role r; 0 otherwise */
   var Assign {WORKERS_ROLES} binary;

   /* If you are assigned Role A you cannot be assigned any other role. */
   con Con1 {w in WORKERS: <w,'A'> in WORKERS_ROLES}:
      sum {<(w),r> in WORKERS_ROLES: r ne 'A'} Assign[w,r] <= card(ROLES) * (1 - Assign[w,'A']);

   /* If you are assigned role B You cannot fill role C. */
   con Con2 {w in WORKERS}:
      sum {<(w),r> in WORKERS_ROLES: r in /B C/} Assign[w,r] <= 1;

   /* For Role A you need 1 person. */
   con Con3:
      sum {<w,'A'> in WORKERS_ROLES} Assign[w,'A'] = 1;

   /* For Roles B, C and D you need 2 persons. */
   con Con4 {r in /B C D/}:
      sum {<w,(r)> in WORKERS_ROLES} Assign[w,r] = 2;

   solve;
   print Assign;
quit;

Alternatively, you can combine constraints 3 and 4:

   con Con34 {r in ROLES}:
      sum {<w,(r)> in WORKERS_ROLES} Assign[w,r] = (if r = 'A' then 1 else 2);

View solution in original post

4 REPLIES 4
RobPratt
SAS Super FREQ

Hi, Paal.  Here's one way:

data indata;
   input worker $ role $;
   datalines;
P1 A
P1 B
P2 B
P2 C
P2 D
P3 C
P4 A
P4 B
P4 D
P5 A
P5 B
P5 C
P5 D
;

proc optmodel;
   set <str,str> WORKERS_ROLES;
   read data indata into WORKERS_ROLES=[worker role];
   set WORKERS = setof {<w,r> in WORKERS_ROLES} w;
   set ROLES = setof {<w,r> in WORKERS_ROLES} r;
   
   /* Assign[w,r] = 1 if worker w is assigned to role r; 0 otherwise */
   var Assign {WORKERS_ROLES} binary;

   /* If you are assigned Role A you cannot be assigned any other role. */
   con Con1 {w in WORKERS: <w,'A'> in WORKERS_ROLES}:
      sum {<(w),r> in WORKERS_ROLES: r ne 'A'} Assign[w,r] <= card(ROLES) * (1 - Assign[w,'A']);

   /* If you are assigned role B You cannot fill role C. */
   con Con2 {w in WORKERS}:
      sum {<(w),r> in WORKERS_ROLES: r in /B C/} Assign[w,r] <= 1;

   /* For Role A you need 1 person. */
   con Con3:
      sum {<w,'A'> in WORKERS_ROLES} Assign[w,'A'] = 1;

   /* For Roles B, C and D you need 2 persons. */
   con Con4 {r in /B C D/}:
      sum {<w,(r)> in WORKERS_ROLES} Assign[w,r] = 2;

   solve;
   print Assign;
quit;

Alternatively, you can combine constraints 3 and 4:

   con Con34 {r in ROLES}:
      sum {<w,(r)> in WORKERS_ROLES} Assign[w,r] = (if r = 'A' then 1 else 2);
PaalNavestad
Pyrite | Level 9

Thanks a million Rob. I was a bit further along than when I wrote the post, but far from a solution.

 

For Con1 and Con2 here you've coded the roles you can't have together. In real life there is approx. 20 roles to fill all with different roles you can't fullfill at the same time. on the top of your head is there a more dynamic way to write this constraint. If no it is not a large problem as the constraints can be created in a preceding macro.

 

Also in real life some persons have clear preferences for certain roles. This is for an offshore platform where the personnel change rapidly. Since there in most cases are several solutions to the problem you can be assigned role A day 1 and then role B day 2. My thoughts on how to avoid this is to give the role you have the day before the value 1 and your preferred role Value 2. From that i would just hav a Var multiplying value and assign and maximize on that. Do you see any problems with that approach?

 

Again thanks a lot.

RobPratt
SAS Super FREQ

Here's a more compact way to prohibit those conflicts, replacing Con1 and Con2:

data conflictdata;
   input role1 $ role2 $;
   datalines;
A B
A C
A D
B C
;
   set <str,str> CONFLICTS;
   read data conflictdata into CONFLICTS=[role1 role2];
   con ConflictCon {w in WORKERS, <r1,r2> in CONFLICTS}:
      sum {<(w),r> in WORKERS_ROLES: r in {r1,r2}} Assign[w,r] <= 1;

Regarding preferences, you can certainly include an objective to maximize the linear function that you proposed.

PaalNavestad
Pyrite | Level 9

Thanks again. I owe you a large beer:-)

SAS INNOVATE 2024

Innovate_SAS_Blue.png

Registration is open! SAS is returning to Vegas for an AI and analytics experience like no other! Whether you're an executive, manager, end user or SAS partner, SAS Innovate is designed for everyone on your team. Register for just $495 by 12/31/2023.

If you are interested in speaking, there is still time to submit a session idea. More details are posted on the website. 

Register now!

Multiple Linear Regression in SAS

Learn how to run multiple linear regression models with and without interactions, presented by SAS user Alex Chaplin.

Find more tutorials on the SAS Users YouTube channel.

Discussion stats
  • 4 replies
  • 507 views
  • 0 likes
  • 2 in conversation