-
Robert Ricci authored
to accept new solutions, so that we don't give violtions any special treatment. This can greatly reduce 'thrasing' at low scores, allowing assign to converge on a solution much faster. For example, in the 1000-node topology used for the virtualization paper, assign's runtime dropped from nearly two hours to just over half an hour, with no degredation in scores found. You can get the old accept behavior by enabling the SPECIAL_VIOLATION_TREATMENT #define, which is on right now (hence, we are not using this change yet.) Here are the pertinent comments from the code: #ifdef SPECIAL_VIOLATION_TREATMENT /* * In this ifdef, we always accept new solutions that have fewer * violations than the old solution, and when we're trying to * determine whether or not to accept a new solution with a higher * score, we don't take violations into the account. * * The problem with this shows up at low temperatures. What can often * happen is that we accept a solution with worse violations but a * better (or similar) score. Then, if we were to try, say the first * solution (or a score-equivalent one) again, we'd accept it again. * * What this leads to is 'thrashing', where we have a whole lot of * variation of scores over time, but are not making any real * progress. This prevents the cooling schedule from converging for * much, much longer than it should really take. */ #else // no SPECIAL_VIOLATION_TREATMENT /* * In this branch of the ifdef, we give violations no special * treatment when it comes to accepting new solution - we just add * them into the score. This makes assign behave in a more 'classic' * simulated annealing manner. * * One consequence, though, is that we have to be more careful with * scores. We do not want to be able to get into a situation where * adding a violation results in a _lower_ score than a solution with * fewer violations. */
5a72226d