Staffing Problem - NLP Solver does not allow integer problems - "Bad Problem Type"

SSTEAD — Mon, 29 Oct 2018 23:06:18 GMT

I have a fairly simple staffing problem. Optimize the minimum number of unfilled hourly slots and number of FTEs per shift with all possible 8 hours shifts in a 24 hour period. All FTEShifts are integer.
The log message from SAS is as follows: The NLP Solver does not allow integer problems". Results says "bad problem type".
Removing the integer restriction allows execution, but it is the not the desired solution, as I need integer solutions with the best fit.
How should I proceed? Thank you for your review.
The code sample is below:

data goal;
input day $ Hr00 Hr01 Hr02 Hr03 Hr04 Hr05 Hr06 Hr07 Hr08 Hr09 Hr10 Hr11 Hr12 Hr13 Hr14 Hr15 Hr16 Hr17 Hr18 Hr19 Hr20 Hr21 Hr22 Hr23;
datalines;
Hol 0.5 0.5 0.5 0.44 0.47 0.61 0.5 1.72 2.28 2.6 2.49 2.52 2.03 1.65 1.42 0.93 1.03 0.75 0.73 0.43 0.54 0.36 0.39 0.25
;

data weight;
input Hr00 Hr01 Hr02 Hr03 Hr04 Hr05 Hr06 Hr07 Hr08 Hr09 Hr10 Hr11 Hr12 Hr13 Hr14 Hr15 Hr16 Hr17 Hr18 Hr19 Hr20 Hr21 Hr22 Hr23;
datalines;
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
;

data Staffing_Shifts;
input Start_Time :TIME5. End_Time :TIME5. Shift_Number Shift_Label :$11. Shift_Duration Hr00 Hr01 Hr02 Hr03 Hr04 Hr05 Hr06 Hr07 Hr08 Hr09 Hr10 Hr11 Hr12 Hr13 Hr14 Hr15 Hr16 Hr17 Hr18 Hr19 Hr20 Hr21 Hr22 Hr23;
format Start_Time End_Time TIME5.;
datalines;
00:00 08:00 01 00:00-08:00 8 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
01:00 09:00 02 01:00-09:00 8 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
02:00 10:00 03 02:00-10:00 8 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
03:00 11:00 04 03:00-11:00 8 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0
04:00 12:00 05 04:00-12:00 8 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0
05:00 13:00 06 05:00-13:00 8 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0
06:00 14:00 07 06:00-14:00 8 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0
07:00 15:00 08 07:00-15:00 8 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0
08:00 16:00 09 08:00-16:00 8 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0
09:00 17:00 10 09:00-17:00 8 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0
10:00 18:00 11 10:00-18:00 8 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0
11:00 19:00 12 11:00-19:00 8 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0
12:00 20:00 13 12:00-20:00 8 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0
13:00 21:00 14 13:00-21:00 8 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0
14:00 22:00 15 14:00-22:00 8 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0
15:00 23:00 16 15:00-23:00 8 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0
16:00 00:00 17 16:00-00:00 8 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
17:00 01:00 18 17:00-01:00 8 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1
18:00 02:00 19 18:00-02:00 8 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1
19:00 03:00 20 19:00-03:00 8 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1
20:00 04:00 21 20:00-04:00 8 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1
21:00 05:00 22 21:00-05:00 8 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1
22:00 06:00 23 22:00-06:00 8 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1
23:00 07:00 24 23:00-07:00 8 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
;

%let name=Ver0.1;
TITLE "&name - Version 1" ;

%let NPERIODS=24;
%let NSHIFTS=24;
%let MAXSHIFTS=10;

proc optmodel PRINTLEVEL=2;
var FTEPerShift{1..24} >= 0 <= &MAXSHIFTS integer;

/* Shifts - each has different start and stop time periods, and total times
Rooms - number of rooms needed at each time period
Weights - relative importance of each time period
*/

set PERIODS = 0..23;
set SHIFTS = 1..24;

/* http://support.sas.com/documentation/cdl/en/ormpug/59679/HTML/default/viewer.htm#optmodel_sect44.htm */
str GoalWeekDay;
num InputPeriods{PERIODS};
read data goal into
GoalWeekDay=day
{ p in PERIODS} < InputPeriods[p]=col("Hr"||put(p,z2.) ) >;
print GoalWeekDay InputPeriods ;

/* Round up for GOAL per Period */
num Goal{PERIODS};
for {p in PERIODS}
Goal[p] = round(InputPeriods[p]+0.5,1);
print Goal;

/* Get Weighting per Period */
num Weighting{PERIODS};
read data weight into
{ p in PERIODS} < Weighting[p]=col("Hr"||put(p,z2.) ) >;
print Weighting;

str ShiftLabel{SHIFTS} ;
num StartTime{SHIFTS}, EndTime{SHIFTS}, ShiftDuration{SHIFTS} ;
set <num> ShiftNumber ;

num FTEperShiftPeriod{SHIFTS,PERIODS};

read data Staffing_Shifts into
ShiftNumber =[_N_]
ShiftLabel =shift_label
StartTime[_N_]=start_time
EndTime[_N_]=end_time
ShiftDuration[_N_]=Shift_Duration
{ p in PERIODS} < FTEperShiftPeriod[_N_,p]=col("Hr"||put(p,z2.) ) >;

print ShiftLabel StartTime EndTime ShiftDuration FTEperShiftPeriod ;

num FTEShiftPeriod{SHIFTS,PERIODS};
num FTEPeriod{PERIODS};

/* W O R K I N G S E C T I O N */
/* Calculate the number per Shift */

for {s in SHIFTS,p in PERIODS} FTEShiftPeriod[s,p] = FTEPerShift[s].sol * FTEperShiftPeriod[s,p];

/* */
for {p in PERIODS} FTEPeriod[p] = sum {s in SHIFTS} FTEShiftPeriod[s,p];

/* G O A L */
min TtlDifference = sum {p in PERIODS} ABS( Goal[p]-FTEPeriod[p] ) * Weighting[p];

expand;

solve;

print TtlShifts TtlDifference FTEPerShift;

quit;

/* *************************
* End of 01-SimnpleStaff24
* ************************* */

Re: Staffing Problem - NLP Solver does not allow integer problems - "Bad Problem Type"

RobPratt — Tue, 30 Oct 2018 15:54:51 GMT

You can linearize the absolute error objective as follows:

impvar FTEShiftPeriod {s in SHIFTS,p in PERIODS} = FTEPerShift[s] * FTEperShiftPeriod[s,p];
impvar FTEPeriod {p in PERIODS} = sum {s in SHIFTS} FTEShiftPeriod[s,p];
var Surplus {PERIODS} >= 0;
var Slack {PERIODS} >= 0;
con AbsErrorCon {p in PERIODS}:
   FTEPeriod[p] - Goal[p] = Surplus[p] - Slack[p];
min TtlDifference = sum {p in PERIODS} (Surplus[p] + Slack[p]) * Weighting[p];

Also see the attached example for two compact ways to handle the "wraparound" issue when a shift starts on one day but goes past midnight and ends the next day.

Re: Staffing Problem - NLP Solver does not allow integer problems - "Bad Problem Type"

SSTEAD — Tue, 30 Oct 2018 00:24:38 GMT

Thank you for the quick reply. Adding the two vars does now allow the program to run, but it does not iterate or solve. I am not sure how adding these vars works.

Did I miss something?

Thanks for the code example. I will review.

Re: Staffing Problem - NLP Solver does not allow integer problems - "Bad Problem Type"

RobPratt — Tue, 30 Oct 2018 15:56:33 GMT

Sorry, my first IMPVAR statement was missing an equals sign, which I have now added. Please try again. The MILP solver should return an optimal solution with objective value 4.

Re: Staffing Problem - NLP Solver does not allow integer problems - "Bad Problem Type"

SSTEAD — Tue, 30 Oct 2018 16:53:41 GMT

It now delivers an optimal solution, with the value of 4.

Thank you very much.

Why are the additional variables needed: Slack and Surplus? They seem extraneous.

I am clearly missing something here. Is is that the minimization formula has to have variables in it?

Thank you again.

Re: Staffing Problem - NLP Solver does not allow integer problems - "Bad Problem Type"

RobPratt — Tue, 30 Oct 2018 18:40:24 GMT

This is a standard linearization technique for absolute value (or L1 norm). At an optimal solution, at least one of Surplus[p] and Slack[p] will be zero, and their sum Surplus[p] + Slack[p] will be the absolute value of FTEPeriod[p] - Goal[p]. See examples 11 and 13 here.

topic Staffing Problem - NLP Solver does not allow integer problems - "Bad Problem Type" in Mathematical Optimization, Discrete-Event Simulation, and OR

Staffing Problem - NLP Solver does not allow integer problems - "Bad Problem Type"

Re: Staffing Problem - NLP Solver does not allow integer problems - "Bad Problem Type"

Re: Staffing Problem - NLP Solver does not allow integer problems - "Bad Problem Type"

Re: Staffing Problem - NLP Solver does not allow integer problems - "Bad Problem Type"

Re: Staffing Problem - NLP Solver does not allow integer problems - "Bad Problem Type"

Re: Staffing Problem - NLP Solver does not allow integer problems - "Bad Problem Type"