[Solved]: How should I choose the neighborhood structure for simulated annealing for my problem?

Problem Detail: 

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?

Asked By : jnalanko

Answered By : Thomas Klimpel

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$.

Don't implement any moves which would be very expensive to evaluate. The strength of simulated annealing is that it can work with moves which are cheap to evaluate, and hence evaluate a large number of candidate solutions. But if your state space is large, then you should also let simulated annealing evaluate a large number of candidate solutions. So your cool down schedule becomes important in this case. I could go into more detail here, but the question was about the neighborhood structure only, and the answer to this question is that your neighborhood structure is basically OK, and you should not use a neighborhood structure which would lead to expensive recomputations.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/33881