A comparison study of optimization methods for the bipartite matching problem (BMP)
- 1 January 1988
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
A comparison study of optimization methods for the bipartite matching problem (BMP) with independent random distances between the points is presented. It is shown that the results obtained are in reasonable agreement with the theoretical prediction despite the relatively small samples considered. In the first four intervals, which include more than 80% of the valid solutions considered, the theoretical results are within one standard deviation of the results obtained by all methodologies. The average computation times per valid solution obtained using VSA (variant of simulated annealing) is superior to the average time of other methodologies. Another interesting result is the fact that the MSA (microcanonical simulated annealing) average time is as much as four times smaller than the FSA (fast simulated annealing) average time.Keywords
This publication has 6 references indexed in Scilit:
- Replicas and optimizationJournal de Physique Lettres, 1985
- Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of ImagesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1984
- Microcanonical simulation of Ising systemsNuclear Physics B, 1984
- Optimization by Simulated AnnealingScience, 1983
- Microcanonical Monte Carlo SimulationPhysical Review Letters, 1983
- Equation of State Calculations by Fast Computing MachinesThe Journal of Chemical Physics, 1953