Redistributing numbers

[mlogan]

Hi there,

I have the following dataset of the school where one course is offered at different classrooms. But in this case some classrooms are not full (ROOM_LOAD) for a given course. I wanted to redistribute the students in classrooms where there is still a capacity left and thus clear out a room and make it available for other use. 

DATA HAVE;
    INPUT COURSE $ ROOM_NO $ ROOM_CAPACITY ROOM_LOAD;
    DATALINES;
CHEM101	C101	20	7
CHEM101	C102	20	11
CHEM101	C103	10	8
CHEM101	C104	15	10
BIO302	HB102	22	20
BIO302	HB106	24	12
BIO302	HB902	30	29
BIO302	W102	30	31
BIO302	AB102	40	27
;
RUN;

 As a output, I want a table like this which will give me new student number (NEW_ROOM_LOAD) of each room after redistribution and also flag the room that come available (Room_Status). I have about 150 courses. That's why I need help with a dynamic code. Any help will be appreciated. I will really appreciate any help you can provide. Thanks.

COURSE	ROOM_NO	ROOM_CAPACITY	ROOM_LOAD	NEW_ROOM_LOAD	Room_Status
CHEM101	C101	20	7	17
CHEM101	C102	20	11	19
CHEM101	C103	10	8	0	Available
CHEM101	C104	15	10	0	Available
BIO302	HB102	22	20	20
BIO302	HB106	24	12	0	Available
BIO302	HB902	30	29	30
BIO302	W102	30	31	30
BIO302	AB102	40	27	39

[mkeintz]

It might be the case that more than one combination of rooms yield the minimum number needed.  But those combinations may have different total capacity for the unneeded rooms.  Do you want to maximize the total unallocated capacity among all the minimum-used-room combinations?

[andreas_lds]

Sorting the rooms by descending capacity helped to get the expected result.

proc sort data= have;
    by course descending room_capacity;
run;

data want;
    num_students = 0;
    
    do _n_ = 1 by 1 until(last.course);
        set have;
        by course;
        
        num_students = num_students + room_load;
    end;
    
    do _n_ = 1 by 1 until(last.course);
        set have;
        by course;
        
        new_room_load = min(room_capacity, num_students);
        num_students = num_students - new_room_load;
        output;
    end;
        
    drop num_students;
run;

[Ksharp]

[Code has beed updated]

A very interesting question. I like it .

But I think you need the help from SAS/OR module for solving such optimization issue.

And calling @RobPratt .

Here is an example I wrote:

DATA HAVE;
    INPUT COURSE $ ROOM_NO $ ROOM_CAPACITY ROOM_LOAD;
    DATALINES;
CHEM101	C101	20	7
CHEM101	C102	20	11
CHEM101	C103	10	8
CHEM101	C104	15	10
BIO302	HB102	22	20
BIO302	HB106	24	12
BIO302	HB902	30	29
BIO302	W102	30	31
BIO302	AB102	40	27
;
RUN;

%macro room(course=);
data temp;
set have;
if COURSE="&course.";
run;

proc optmodel;
set <str> ROOM_NO;
num ROOM_CAPACITY{ROOM_NO};
num ROOM_LOAD{ROOM_NO};
num sum_ROOM_LOAD=sum{i in ROOM_NO} ROOM_LOAD[i];
read data temp into ROOM_NO=[ROOM_NO] ROOM_CAPACITY ROOM_LOAD;
var v{ROOM_NO} binary;
min TotalCost =  (sum{i in ROOM_NO} ROOM_CAPACITY[i]*v[i]) - sum_ROOM_LOAD ;
con con: sum{i in ROOM_NO} ROOM_CAPACITY[i]*v[i] >= sum_ROOM_LOAD;
solve ;
create data want from [ROOM]={i in ROOM_NO} 
                      ROOM_CAPACITY=ROOM_CAPACITY[i] 
                      ROOM_LOAD=ROOM_LOAD[i] 
                     flag=v[i].sol;
quit;
data want;
length COURSE ROOM $ 80;
set want;
COURSE="&course.";
run;
proc append base=final_want data=want force;run;
%mend;

proc freq data=have noprint;
table course/out=course;
run;
proc delete data=final_want;run;
data _null_;
set course;
call execute(catt('%room(course=',course,')'));
run;


proc print data=final_want noobs;run;

[quickbluefish]

@Ksharp - what does the 'flag' variable indicate here?  Agree this is an interesting question.

[Ksharp]

Flag=1 stands for NOT Available.
Flag=0 stands for Available.

[mlogan]

Mank thanks Ksharp. Would it be possible for you to populate the column NEW_ROOM_LOAD in the Final_want file so that I know how they were redistributed? I also wanted to ensure that room W102's number went down from 31 to 30. Thanks.

[Ksharp · Accepted solution]

Sure. But that would lead to many combinations , here is one of combination:

DATA HAVE;
    INPUT COURSE $ ROOM_NO $ ROOM_CAPACITY ROOM_LOAD;
    DATALINES;
CHEM101	C101	20	7
CHEM101	C102	20	11
CHEM101	C103	10	8
CHEM101	C104	15	10
BIO302	HB102	22	20
BIO302	HB106	24	12
BIO302	HB902	30	29
BIO302	W102	30	31
BIO302	AB102	40	27
;
RUN;

%macro room(course=);
data temp;
set have;
if COURSE="&course.";
run;

proc optmodel;
set <str> ROOM_NO;
num ROOM_CAPACITY{ROOM_NO};
num ROOM_LOAD{ROOM_NO};
num sum_ROOM_LOAD=sum{i in ROOM_NO} ROOM_LOAD[i];
read data temp into ROOM_NO=[ROOM_NO] ROOM_CAPACITY ROOM_LOAD;
var v{ROOM_NO} binary;
min TotalCost =  (sum{i in ROOM_NO} ROOM_CAPACITY[i]*v[i]) - sum_ROOM_LOAD ;
con con: sum{i in ROOM_NO} ROOM_CAPACITY[i]*v[i] >= sum_ROOM_LOAD;
solve ;
create data want from [ROOM]={i in ROOM_NO} 
                      ROOM_CAPACITY=ROOM_CAPACITY[i] 
                      ROOM_LOAD=ROOM_LOAD[i] 
                     flag=v[i].sol;
quit;
data want;
length COURSE ROOM $ 80;
set want;
COURSE="&course.";
run;
proc append base=final_want data=want force;run;
%mend;

proc freq data=have noprint ;
table course/out=course;
run;
proc delete data=final_want;run;
data _null_;
set course;
call execute(catt('%room(course=',course,')'));
run;




proc summary data=final_want ;
by course;
var room_load;
output out=sum(drop=_:) sum=sum;
run;
data final_want2;
 merge final_want sum;
 by course;
 if first.course then cum_ROOM_CAPACITY=0;
 new_room_load=0;
 if flag=1 then do; 
     cum_ROOM_CAPACITY+ROOM_CAPACITY;
     new_room_load=ifn(sum>=cum_ROOM_CAPACITY,ROOM_CAPACITY,ROOM_CAPACITY-cum_ROOM_CAPACITY+sum);
 end;
 drop sum cum_ROOM_CAPACITY;
run;

proc print data=final_want2 noobs;run;

[mlogan]

.

[quickbluefish]

Here's an edited version -- I changed the sort order based on what @andreas_lds said above (sorting by room capacity - ascending in this case, though - instead of by # of vacancies) - now produces the same result, though not nearly as short as his:

proc sort data=have; by course room_capacity; run;

title 'before';
proc print data=have; run;

proc sql noprint;
select max(nrecs) into :maxrecs trimmed 
from 
	(select course, count(*) as nrecs from have group by course);
quit;

data want;
set have;
by course;
array T {&maxrecs, 2} _temporary_;
array C {&maxrecs} $8 _temporary_;
length cnum 3;
if first.course then call missing(of T[*], of C[*], cnum);
cnum+1;
C[cnum]=room_no;
T[cnum, 1]=room_capacity;
T[cnum, 2]=room_load;
if last.course then do;
	if cnum=1 then goto write;
	do i=1 to (cnum-1);
		do j=(i+1) to cnum;
			avail=T[j,1]-T[j,2];
			moved=min(T[i,2],avail);
			T[j,2]+moved;
			T[i,2]+(-moved);
			if T[i,2]=0 then leave;
		end;
	end;
	write:
	do i=1 to cnum;
		room_no=C[i];
		room_capacity=T[i,1];
		room_load=T[i,2];
		output;
	end;
end;
keep course room_:;
run;

title 'after';
proc print data=want; run;
title;

[RobPratt]

Here's one way to solve the problem with PROC OPTMODEL:

proc optmodel;
   /* declare parameters and read input data set */
   set <str,str> COURSE_ROOM;
   num capacity {COURSE_ROOM};
   num load {COURSE_ROOM};
   read data HAVE into COURSE_ROOM=[course room_no] capacity=room_capacity load=room_load;

   /* calculate demand per course */
   set <str> COURSES init {};
   num demand {COURSES} init 0;
   for {<c,r> in COURSE_ROOM} do;
      COURSES = COURSES union {c};
      demand[c] = demand[c] + load[c,r];
   end;

   /* declare decision variables */
   var NewRoomLoad {<c,r> in COURSE_ROOM} >= 0 <= capacity[c,r];
   var IsAvailable {COURSE_ROOM} binary;

   /* declare objective */
/*   max NumAvailable = sum {<c,r> in COURSE_ROOM} IsAvailable[c,r];*/
   max AvailableCapacity = sum {<c,r> in COURSE_ROOM} capacity[c,r] * IsAvailable[c,r];

   /* declare constraints */
   con RespectCapacity {<c,r> in COURSE_ROOM}:
      IsAvailable[c,r] = 1 implies NewRoomLoad[c,r] = 0;
/*   con RespectCapacity {<c,r> in COURSE_ROOM}:*/
/*      NewRoomLoad[c,r] <= NewRoomLoad[c,r].ub * (1 - IsAvailable[c,r]);*/
   con SatisfyDemand {c in COURSES}:
      sum {<(c),r> in COURSE_ROOM} NewRoomLoad[c,r] = demand[c];

   /* call MILP solver */
   solve;

   /* create output data set */
   create data WANT from [COURSE	ROOM_NO]={<c,r> in COURSE_ROOM}
      ROOM_CAPACITY=capacity ROOM_LOAD=load NEW_ROOM_LOAD=NewRoomLoad Room_Status=(if IsAvailable[c,r] > 0.5 then 'Available' else '');
quit;

The first MAX statement (commented out) maximizes the number of available rooms.  The second MAX statement maximizes the available capacity.  For your sample data, both objectives yield the same available rooms:

COURSE	ROOM_NO	ROOM_CAPACITY	ROOM_LOAD	NEW_ROOM_LOAD	Room_Status
CHEM101	C101	20	7	20
CHEM101	C102	20	11	16
CHEM101	C103	10	8	0	Available
CHEM101	C104	15	10	0	Available
BIO302	HB102	22	20	19
BIO302	HB106	24	12	0	Available
BIO302	HB902	30	29	30
BIO302	W102	30	31	30
BIO302	AB102	40	27	40

If you are using a SAS version that does not support indicator constraints (IMPLIES), you can use the second (commented out) RespectCapacity constraint instead.

It might also be worth considering a secondary objective like minimizing the number of reassigned students.  Also, is there any concern about the reassignments introducing schedule conflicts where the same student is enrolled in different courses that meet at the same time?

[mlogan]

Thank you RobPratt. It looks like we can move all students (12) from room HB106 and put them on AB102 and make room HB106 fully available. Also, I want the Room_Status flagged as AVAILABLE only when NEW_ROOM_LOAD=0. Would you please help a bit more.

[RobPratt]

@mlogan Yes, my solution already does that.  HB106 has NEW_ROOM_LOAD = 0.  And Room_Status = 'Available' if and only if NEW_ROOM_LOAD = 0.

[mlogan]

Hi RobPratt, I ran your whole code and it gives me the following table:

Updating Media

[mlogan]

Hi RobPratt, I ran your whole code and it gives me the following table: