Proc Optmodel MILP Scheduling: Pausing resource reallocation and giving preference to allocations

[Fibo1123]

Hello. I recently posted a question on giving soft preferences to resource allocations but decided I might get a better response if I developed some example code. I have included the plain .sas files to generate the input data and execute the optimization. It's a small example, so the required data and optimization can be recreated in a few seconds. I am using SAS Enterprise Guide v8.3 (Base 9.4_M7).

TLDR: I need help defining two scheduling constraints in Proc Optmodel (MILP):

#1) If a product is scheduled on a given day, it cannot be scheduled again for the next N days.

#2) Given info about preferred time/day slots for a particular set of products, I would like the optimizer to schedule the products on these time/day slots if feasible but if it will result in an infeasible solution, then relax the condition so one/more/all of the products can be assigned to other times/days. 

I am working on a resource scheduling problem, allocating a finite set of products to a finite set of time/day slots over a month. I have a table (INPUT_DATA) of product IDs (PROD_ID), and predicted sales amounts when the PROD_ID is sold during a particular time/day slot. I am using Proc Optmodel MILP to maximize the total predicted sales amount for the month by allocating the PROD_IDs to available slots.

Current Working Constraints:

1. One_Var_Per_Slot: Only a single PROD_ID may be assigned to a given time/day slot (i.e. products 'AAA' and 'BBB' may not both be assigned to the 9am slot on Day 3.)
2. Max_2_Consecutive_Slots: A PROD_ID may not be assigned to the same time slot on two consecutive days (i.e. product 'AAA' may be assigned the 9am slot on Day 1 and 9am on Day 2, but then not at 9am on Day 3).
3. Prod_Fixed_Shows: The table in FIXED_PRODS contains a list of PROD_IDs and day/time combinations in which they *must* be assigned. This constraint enforces that requirement.
4. Prod_Fixed_Shows2: Additionally, fixed PROD_IDs may not be assigned to any other day/time other than those specified in theFIXED_PRODS table.

Desired Constraints:

1. If a PROD_ID has been assigned to one (or more) time slots on any given day, then it may not be assigned to any time slots over the next N days. For example, let N=2. If PROD_ID='AAA'  is assigned to one or more time slots on Day_3, then it cannot be assigned to any time slot on Day_4 or Day_5. It can potentially be assigned again on Day_6. If it is, then it would not be assignable again on Day_7 and Day_8. 
2. The table in PREF_PRODS contains a list of PROD_IDs and day/time slot in which I would like to assign the PROD_IDs if possible, but do not want to make this a hard constraint. That is, I would like SAS to assign them to these slots if feasible but if it will result in an infeasible solution, then one/more/all of the scheduling preferences can be relaxed. It would be better if the solution would allow for the relaxing of just the infeasible preferences while maintaining any feasible preferences.

Thank you for any help you can provide.

[RobPratt · Accepted solution]

Here's one way to enforce your first desired constraint:

   num dayToNum {DayNumbers};
   num count init 0;
   for {d in DayNumbers} do;
      count = count + 1;
      dayToNum[d] = count;
   end;
   print dayToNum;
   num N = 2;
   con DesiredConstraint1 {<PROD_ID, slot, day> in PROD_SLOT_DAY, <(PROD_ID), slot2, day2> in PROD_SLOT_DAY: dayToNum[day2] in dayToNum[day]+1..dayToNum[day]+N}:
      PROD_ASSIGN[PROD_ID, slot, day] + PROD_ASSIGN[PROD_ID, slot2, day2] <= 1;

But notice that this conflicts with your fixed assignments of AAA to days 6, 7, and 8, so the resulting problem is infeasible.

For your second desired constraint, you can use multiple objectives as follows:

   max NumPreferences = sum {<PROD_ID, slot, day> in PREF_PROD_SHOWCD inter PROD_SLOT_DAY} PROD_ASSIGN[PROD_ID, slot, day];
   solve obj NumPreferences;
   con ObjectiveCut: NumPreferences >= NumPreferences.sol;
   solve obj TotalPreferenceWeight with milp / primalin;

The idea is to first maximize the number of preferences that can be satisfied, then impose a constraint that enforces that maximum, and then maximize your original objective function.  I have used the PRIMALIN option to warm start the second solve with the solution from the first solve.

[Fibo1123]

@RobPratt  Thank you so much. That was brilliant. Now that you point it out, I can see my toy example was infeasible given my requested constraints. However, I'm happy to report that your solution worked perfectly out-of-the box when I inserted it into my real-world project. 

{<PROD_ID, slot, day> in PROD_SLOT_DAY, <(PROD_ID), slot2, day2> in PROD_SLOT_DAY: dayToNum[day2] in dayToNum[day]+1..dayToNum[day]+N}

I've been struggling with set notation in Proc Optmodel and you opened up a lot of possibilities to me with this. Please let me know if my pseudo-code understanding of this set is correct.

Your statement creates a single set from two sub-sets.
One, <PROD_ID, slot, day> in PROD_SLOT_DAY
and
Two, for each PROD_ID above (thus the (PROD_ID) notation):
extract slot2 and  day2 from from the same set, PROD_SLOT_DAY, 
where the numeric equivalent of day2  is in [day+1, day+6]

[RobPratt]

Glad to help.  Yes, your understanding is correct (assuming N=6).  You can also use the EXPAND statement to help verify what is happening.  For example:

   expand DesiredConstraint1;

Here are the first several lines of the resulting output:

Constraint DesiredConstraint1[AAA,9,DAY_1,11,DAY_2]: PROD_ASSIGN[AAA,9,DAY_1] +                   
PROD_ASSIGN[AAA,11,DAY_2] <= 1                                                                    
Constraint DesiredConstraint1[AAA,9,DAY_1,11,DAY_3]: PROD_ASSIGN[AAA,9,DAY_1] +                   
PROD_ASSIGN[AAA,11,DAY_3] <= 1                                                                    
Constraint DesiredConstraint1[AAA,9,DAY_1,12,DAY_2]: PROD_ASSIGN[AAA,9,DAY_1] +                   
PROD_ASSIGN[AAA,12,DAY_2] <= 1                                                                    
Constraint DesiredConstraint1[AAA,9,DAY_1,12,DAY_3]: PROD_ASSIGN[AAA,9,DAY_1] +                   
PROD_ASSIGN[AAA,12,DAY_3] <= 1                                                                    
Constraint DesiredConstraint1[AAA,9,DAY_1,9,DAY_3]: PROD_ASSIGN[AAA,9,DAY_1] +                    
PROD_ASSIGN[AAA,9,DAY_3] <= 1                                                                     
Constraint DesiredConstraint1[AAA,9,DAY_1,9,DAY_2]: PROD_ASSIGN[AAA,9,DAY_1] +                    
PROD_ASSIGN[AAA,9,DAY_2] <= 1                                                                     
Constraint DesiredConstraint1[AAA,9,DAY_1,10,DAY_3]: PROD_ASSIGN[AAA,9,DAY_1] +                   
PROD_ASSIGN[AAA,10,DAY_3] <= 1                                                                    
Constraint DesiredConstraint1[AAA,9,DAY_1,10,DAY_2]: PROD_ASSIGN[AAA,9,DAY_1] +                   
PROD_ASSIGN[AAA,10,DAY_2] <= 1