• Robert Ricci's avatar
    A faily fundamental change in assign - change the criteria we use · 5a72226d
    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
anneal.cc 32.3 KB