On Monte Carlo Methods in Congestion Problems: I. Searching for an Optimum in Discrete Situations

The crude Monte Carlo method is inefficient when searching for extreme points since it uses none of the information gained from earlier samples. If the possible situations are the permutations of a number of items, a method called Chain Monte Carlo is suggested that needs a measure of distance between two permutations. Examples are given and in some scheduling problems substantial savings in computation are observed.