How to Encode Many-to-Many Assignment Problems Where Order Doesn't Matter

[makaimann]

Hey Timefold team, thanks for all your work on this awesome tool! I’m new to Timefold so let me know if this is the wrong place to ask a question like this.

I’m hoping to get some intuition on how to best encode a particular problem.

Problem

I have a robotics task assignment problem where robots can service multiple tasks if the tasks are near each other. However, I don’t actually care about the order. My goal is to get Timefold to cluster nearby tasks and assign teams of robots that have the right capabilities and meet some minimum number (some tasks may be collaborative).

This is actually a many-to-many relationship between robots and tasks but where order doesn’t matter. If we explicitly model clusters, then each task and robot only has a single cluster.

Ideas

At most there can be as many clusters as there are tasks. I had two main ideas:

• Represent clusters with an int that gets assigned to both robot and task planning entities (but then I have more than one PlanningEntity)
• Have a cluster planning entity with list variables of robots and tasks
  • Disable all the moves that just reorder within a list

With these ideas there are a bunch of symmetries. For example, you can permute all the cluster integer identities, or swap entire lists without changing the meaning. My two main questions are the following:

• does it make sense to add symmetry breaking constraints that enforce a certain order? I.e. order the list variables and enforce that if a list is empty, all the subsequent lists must also be empty.
  • or would you expect that's not worth the effort -- full permutations usually take multiple moves to achieve, so it's not easy to just prevent them from happening
• Is there a more Timefold-idiomatic way to approach this?

I will definitely evaluate different encodings, but I’m curious how Timefold experts would approach this!

[zepfred]

Hey @makaimann,

If I understand correctly, you can define a planning entity for the robot with a planning list variable tasks. Additionally, you can create a list of tags for the robot to indicate its capabilities, as well as a list of required capabilities for the problem fact task. Using the input data, create constraints that penalize scores for any missing required capabilities.

You can find inspiration for defining the capabilities and task requirements in the quick-start conference scheduling:

https://github.com/TimefoldAI/timefold-quickstarts/tree/stable/java/conference-scheduling.

Regarding the selection of "near" tasks, I'm not entirely clear on your use case. However, I would recommend creating a constraint that penalizes the "distance" between tasks for each robot. Implementing constraints that either reward or penalize solutions effectively aids the solver in exploring the solution space.

One helpful feature for incrementally calculating the "distance" between tasks is called shadow variables. This approach allows you to update the distance value when updating the task list. The VRP quick-start will provide ideas on calculating distance and creating related constraints:

https://github.com/TimefoldAI/timefold-quickstarts/tree/stable/java/vehicle-routing

[makaimann]

Hey @zepfred, thanks for your quick response! This makes sense. Although my concern with list variables is that order matters in a list variable, so unless I do something about it there will be lots of moves that have no impact (ex: swapping two tasks in the list). Basically, I’m wanting a “PlanningSetVariable” (but completely understand there is not).

Should I not be worried about that? And/or would you recommend configuring the moves to not include any that just permute order within one list?

Furthermore, list variables assume each task is only assigned once — but there could be multiple robots assigned to the same task, so having a planning list variable per robot wouldn’t work in this case.

Regarding nearness constraints — I already know how I’ll do that with a distance matrix and shadow variables if needed. I shouldn’t have even mentioned that because it distracts from my main question about assignments where order doesn’t matter. My mistake.

[zepfred]

The concern about using correct moves is completely valid, as the Solver depends on them to efficiently explore the solution space.

In that case, I have two suggestions:

1. Adjust your move list settings to apply filters that will eliminate unnecessary moves. This approach will help you achieve the related goals while continuing to use the built-in implementation. Additionally, I suggest benchmarking the problem-solving process to evaluate the impact of the filters.
2. Custom moves can also be a solution to this problem. This is likely more complex since you need to provide the implementation, but it may perform better as you know the requirements in advance. We perform certain validations by default to prevent score corruption, and this can be adjusted to obtain more useful information during the development phase: https://docs.timefold.ai/timefold-solver/latest/using-timefold-solver/running-the-solver#environmentModeAvailableModes

[makaimann]

Cool, thanks @zepfred. I’ll give those both a shot!

[triceo]

Personally, I wouldn't use the list variable for this - list variable semantics is that the list determines a chain of events. The solver will treat it like this everywhere - therefore if you decide to ignore that aspect, you will have to fight the solver every step of the way. And we will not accept feature requests/bug reports that come from such misuse of the list variable.

Instead, I recommend:

• Creating an entity where 1 robot is assigned to a task.
• If a task requires multiple robots, create an entity for each "part" and give them some shared group identification.
• Enforce nearness and anything else via constraints.
• Prevent any unnecessary moves either by move filtering, or by writing custom moves outright. (For example: I can already see that moving groups of robots between groups of tasks may be a very beneficial custom move.)

[makaimann]

Thanks @triceo that makes sense! I'd rather not abuse the solver 😅 I'll try your suggestion with an assignment entity. A custom move for groups of robots between groups of tasks is a great idea!