# How should I choose the neighborhood structure for simulated annealing for my problem?

There are $n$ students and $m$ courses. Each student $i$ wants to attend a subset $C_i \subseteq \{1,\ldots,m\}$ of the courses. There are $k$ time slots on a weekly schedule. The goal is to select a time slot for each course such that the students can attend as many courses as possible, that is, find a mapping $f: \{1,\ldots,m\} \rightarrow \{1,\ldots,k\}$ such that the following objective function is maximized:

$$\sum_{i = 1}^n \big| \bigcup_{j \in C_i} \{f(j)\} \big|$$

For my (artificial) instance $n = 10^5, m = 5000, k = 25$, and any student wants to attend at most 16 courses. I have tried a hill climbing algorithm which moves in the search space by changing one course at a time in the mapping $f$ if it improves the objective function, until it can improve no more. This gives a local maximum, but I'd like to do better. I've tried to implement a simulated annealing approach with the same neighbourhood structure, but I haven't been able to tune the parameters to beat the hill climbing algorithm.

I've read that the number of moves from any part of the search space to another part should be small. In my solution I need at most $5000$ moves, is this too much? If make bigger changes into the mapping, the evaluation of the cost function becomes expensive, as I have to recompute the objective function for every student affected by the change. What kind of a neighbourhood structure would suit this problem the best?

Simulated annealing can cope with neighborhood structures where you have to walk quite a bit to reach a distant point. Of course, the minimum distance between two points in the state space should at most be polynomial in the problem size, but any reasonable optimization heuristics will also require this restriction. The 5000 moves are completely reasonable for simulated annealing, especially since this is linear in $m$.