×

Cost distributions in large combinatorial optimisation problems. (English) Zbl 0706.90064

Summary: We have examined the cost distribution of locally optimal solutions in certain combinatorial optimization problems. This distribution is found to be peaked about a value characteristic of the algorithm involved, with a width that decreases with the system size N. It is shown that the distribution of costs \(\epsilon\) is of the form exp(Ng(\(\epsilon\))) and that g(\(\epsilon\)) is self-averaging. Consequently, estimation of the optimal cost is best achieved by curve fitting to g(\(\epsilon\)). Possible forms for g(\(\epsilon\)) are proposed.

MSC:

90C27 Combinatorial optimization
90C60 Abstract computational complexity for mathematical programming problems
90C06 Large-scale problems in mathematical programming
PDFBibTeX XMLCite
Full Text: DOI Link