New tools in combinatorial optimization
James Byron Nelson · Proceedings of the 40th IEEE Conference on Decision and Control (Cat. No.01CH37228) · 2003
Two tools are further explored in applications to combinatorial optimization. The waiting-time distribution (WTD) is formed by running several hundred examples of a given algorithm as applied to a specific optimization problem. This distribution allows direct comparison of algorithms for a given problem. It also motivates restarting the algorithm from the beginning in order to (sometimes greatly) speed up the solution. A second tool is similar. The algorithm is run several hundred times to a maximum number of steps (the threshold) and the criterion value achieved to this point is recorded. The subsequent criterion-value distribution (CVD) allows the algorithm to be tuned quite conveniently for the problem at hand. Finally, an example is shown of the application of these tools to the comparison of a new optimization algorithm SOAR to random search for a moderately hard combinatorial-optimization problem.