topic Re: Redistributing numbers in Mathematical Optimization, Discrete-Event Simulation, and OR

Redistributing numbers

mlogan — Wed, 09 Apr 2025 01:17:27 GMT

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

Re: Redistributing numbers

mkeintz — Wed, 09 Apr 2025 03:01:03 GMT

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?

Re: Redistributing numbers

andreas_lds — Wed, 09 Apr 2025 06:34:35 GMT

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;

Re: Redistributing numbers

Ksharp — Wed, 09 Apr 2025 07:03:40 GMT

[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;

Re: Redistributing numbers

quickbluefish — Wed, 09 Apr 2025 11:26:44 GMT

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

Re: Redistributing numbers

quickbluefish — Wed, 09 Apr 2025 11:50:59 GMT

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;

Re: Redistributing numbers

mlogan — Wed, 09 Apr 2025 15:39:34 GMT

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.

Re: Redistributing numbers

mlogan — Wed, 09 Apr 2025 15:45:42 GMT

Re: Redistributing numbers

RobPratt — Wed, 09 Apr 2025 17:31:11 GMT

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?

Re: Redistributing numbers

mlogan — Wed, 09 Apr 2025 17:56:23 GMT

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.

Re: Redistributing numbers

RobPratt — Wed, 09 Apr 2025 18:02:48 GMT

@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.

Re: Redistributing numbers

mlogan — Wed, 09 Apr 2025 18:18:13 GMT

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

Updating Media

Re: Redistributing numbers

mlogan — Wed, 09 Apr 2025 18:20:02 GMT

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

Re: Redistributing numbers

mlogan — Wed, 09 Apr 2025 18:24:57 GMT

Hi RobPratt, I ran your whole code and it gives me the following table. Should I get rid of any part of your code? Thanks.

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

Re: Redistributing numbers

RobPratt — Wed, 09 Apr 2025 18:50:50 GMT

Did you get any error message in the log? I suspect that your SAS version does not support indicator constraints (IMPLIES), in which case you should instead use the second (commented out) version of the RespectCapacity constraint.

Re: Redistributing numbers

mkeintz — Wed, 09 Apr 2025 19:22:57 GMT

@RobPratt

It appears to me that your OPTMODEL code maximizes the total number of SEATS available in unused rooms. Do I have that correct?

But the OP appears to ask to maximize the number of unused ROOMS (minimize number of rooms used, actually). Could there not be a configuration of room sizes that satisfy your objective but would not satisfy the OP's original request?

For instance, if there are six rooms with sizes 7, 6, 6, 5, 2, and 2.

For total load 13, I believe your code would select a 7 and 6, maximizing the number of seats in unused rooms (6+5+2+2=15). And that result would also satisfy the objective of maximizing unassigned rooms.
For total load 11, I think your code would use three rooms (7, and both 2's,) leaving 3 rooms (6+6+5=17) unused, maximizing seats in unused rooms. However, the minimum number of ROOMS needed for the total load would be two (7 and either 5 or 6), leaving 4 rooms free, but with smaller total capacity.

Maybe the OP doesn't care about this issue. But is there code that would do two levels of optimizing?First, minimize the count of used rooms. Then, for all combinations satisfying that objective, find one that maximizes your objective - total seats in unused rooms.

Re: Redistributing numbers

RobPratt — Wed, 09 Apr 2025 19:36:20 GMT

@mkeintz Yes, I included both objectives, with one of them commented out.

Yes, you can optimize multiple objectives sequentially, with a primary objective, secondary objective, tertiary objective, and so on. Here is one such example: SAS Help Center: Distribution 1: Which Factories and Depots to Supply Which Customers

Re: Redistributing numbers

Ksharp — Thu, 10 Apr 2025 00:55:57 GMT

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

Re: Redistributing numbers

Ksharp — Thu, 10 Apr 2025 01:24:25 GMT

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;