Are “swap move factories” worth the effort?

Question

I noticed that for problems such as Cloudbalancing, move factories exist to generate moves and swaps. A "move move" transfers a cloud process from one computer to another. A "swap move" swaps any two processes from their respective computers.

I am developing a timetabling application.

1. A subjectTeacherHour (a combination of subject and teacher) have only a subset of Periods to which they may be assigned. If Jane teaches 6 hours at a class, there are 6 subjectTeacherHours each which have to be allocated a Period, from a possible 30 Periods of that class ;unlike the cloudbalance example, where a process can move to any computer.
2. Only one subjectTeacherHour may be allocated a Period (naturally).

It tries to place subjectTeacherHour to eligible Periods , till an optimal combination is found.

---

Pros

The manual seems to recommend it.

...However, as the traveling tournament example proves, if you can remove a hard constraint by using a certain set of big moves, you can win performance and scalability...

...The `[version with big moves] evaluates a lot less unfeasible solutions, which enables it to outperform and outscale the simple version....

...It's generally a good idea to use several selectors, mixing fine grained moves and course grained moves:...

While only one subjectTeacher may be allocated to Period, the solver must temporarily break such a constraint to discover that swapping two certain Period allocations lead to a better solution. A swap move "removes this brick wall" between those two states.

So a swap move can help lead to better solutions much faster.

Cons

A subjectTeacher have only a subset of Periods to which they may be assigned. So finding intersecting (common) hours between any two subjectTeachers is a bit tough (but doable in an elegant way: Good algorithm/technique to find overlapping values from objects' properties? ) .

Will it only give me only small gains in time and optimality?

I am also worried about crazy interactions having two kinds of moves may cause, leading to getting stuck at a bad solution.

Answer 1

Swap moves are crucial.

Consider 2 courses assigned to a room which is fully booked. Without swapping, it would have to break a hard constraint to move 1 course to a conflicted room and chose that move as the step (which is unlikely).

You can use the build-in generic swap MoveFactory. If you write your own, you can say the swap move isDoable() false when your moving either sides to an ineligible period.