Change search
ReferencesLink to record
Permanent link

Direct link
Confidence in heuristic solutions?
Dalarna University, School of Technology and Business Studies, Statistics.ORCID iD: 0000-0003-2317-9157
Dalarna University, School of Technology and Business Studies, Statistics.ORCID iD: 0000-0003-2970-9622
2014 (English)Report (Other academic)
Abstract [en]

Solutions to combinatorial optimization problems frequently rely on heuristics to minimize an objective function. The optimum is sought iteratively and pre-setting the number of iterations dominates in operations research applications, which implies that the quality of the solution cannot be ascertained. Deterministic bounds offer a mean of ascertaining the quality, but such bounds are available for only a limited number of heuristics and the length of the interval may be difficult to control in an application. A small, almost dormant, branch of the literature suggests using statistical principles to derive statistical bounds for the optimum. We discuss alternative approaches to derive statistical bounds. We also assess their performance by testing them on 40 test p-median problems on facility location, taken from Beasley’s OR-library, for which the optimum is known. We consider three popular heuristics for solving such location problems; simulated annealing, vertex substitution, and Lagrangian relaxation where only the last offers deterministic bounds. Moreover, we illustrate statistical bounds in the location of 71 regional delivery points of the Swedish Post. We find statistical bounds reliable and much more efficient than deterministic bounds provided that the heuristic solutions are sampled close to the optimum. Statistical bounds are also found computationally affordable.

Place, publisher, year, edition, pages
Borlänge: Högskolan Dalarna, 2014. , 26 p.
Working papers in transport, tourism, information technology and microdata analysis, ISSN 1650-5581 ; 2014:12
National Category
Economic Geography Probability Theory and Statistics
Research subject
Komplexa system - mikrodataanalys
URN: urn:nbn:se:du-14457OAI: diva2:727755
Available from: 2014-06-23 Created: 2014-06-23 Last updated: 2015-05-07Bibliographically approved

Open Access in DiVA

Confidence in heuristic solutions(1068 kB)101 downloads
File information
File name FULLTEXT01.pdfFile size 1068 kBChecksum SHA-512
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Carling, KennethMeng, Xiangli
By organisation
Economic GeographyProbability Theory and Statistics

Search outside of DiVA

GoogleGoogle Scholar
Total: 101 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 644 hits
ReferencesLink to record
Permanent link

Direct link