Can the value range of a planning variable be empty or have only one value?

[kentbill]

Hello everyone！
I had a sudden thought and discovered a doubt like this

There are 2 planning variables in a planning entity, and the value in one of them is meaningless in certain datasets.
For instance, in the TimeTable example, some courses only require remote teaching, but most other courses still require on-site. For those remote courses, I just need to give them a "virtual classroom" - home.

I can certainly restrict the location of these remote courses to home with a hard constraint, but if the value range provider is limited to only one value, can it reduce the search space? or cause other problems?

[TomCools]

Hi @kentbill.

You mention 2 planning variables, but you only implicitly mention 1 of them ("room?"). For the rest of my answer, i'll assume the other one is "Timeslot" just like our School Timetabling Quickstart. (https://github.com/TimefoldAI/timefold-quickstarts/blob/stable/java/school-timetabling/src/main/java/org/acme/schooltimetabling/domain/Lesson.java).

Problem Scale Impact

Here is the approximate problem scale (reported by the solver) by default, and after I have limited the value range provider (let's say, half of the lessons are remote):

• No Filter: (3,486744 ? 10^29)
• 10% remote: (3,874164 ? 10^28)
• 20% remote: (4,304632 ? 10^27).
• 50% remote: (5,904865 ? 10^24)

So yes, the search space is a lot smaller depending on how many lessons are remote., even 10 percent remote lessons reduces the search space by an other of magnitude.

// Simplified code example of the ValueRangeProvider in the lesson class, where half of the lessons are virtual: 
  private final static List<Room> VIRTUAL_ROOM_PLACEHOLDER = List.of(new Room("VIRTUAL","VIRTUAL"));
  
  @ValueRangeProvider
  public List<Room> getPossibleRoomList() {
      if (Long.parseLong(id) %2 == 0) { // or any other check for virtual, just did this to have 50% remote lessons
          return VIRTUAL_ROOM_PLACEHOLDER;
      } else {
          return getRooms();
      }
  }
    
 // Alternatively, you might use Polymorphism, inheritance and separate explicitly referenced ValueRangeProviders for VirtualLesson and Lesson objects.

Downsides

As mentioned in our documentation on this subject: https://docs.timefold.ai/timefold-solver/latest/using-timefold-solver/modeling-planning-problems#valueRangeProviderOnPlanningEntity

• ValueRangeProvider on an entity essentially creates a built in hard constraint. Always be mindful if this constraint is really a HARD constraint. In your case, I think it would indeed be hard constraint that remote classes don't need a room so it's probably ok.
• This built in hard constraint means the solver can never temporarily break it to escape a local optimum.
• This approach also consumes more memory than a single ValueRangeProvider, but if it's just pointer to the same objects, that overhead is usually pretty acceptable.

[kentbill]

Got it. thank you! @TomCools
It seems that I need to consider the advantages and disadvantages of this approach from multiple perspectives, including escape the local optimum and memory usage.

[TomCools]

Trying it out is the only real way to know the best path ;)