du.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
GRASP and statistical bounds for heuristic solutions to combinatorial problems
Dalarna University, School of Technology and Business Studies, Statistics.ORCID iD: 0000-0003-2317-9157
Dalarna University, School of Technology and Business Studies, Statistics.
2016 (English)Report (Other academic)
Abstract [en]

The quality of a heuristic solution to a NP-hard combinatorial problem is hard to assess. A few studies have advocated and tested statistical bounds as a method for assessment. These studies indicate that statistical bounds are superior to the more widely known and used deterministic bounds. However, the previous studies have been limited to a few metaheuristics and combinatorial problems and, hence, the general performance of statistical bounds in combinatorial optimization remains an open question. This work complements the existing literature on statistical bounds by testing them on the metaheuristic Greedy Randomized Adaptive Search Procedures (GRASP) and four combinatorial problems. Our findings confirm previous results that statistical bounds are reliable for the p-median problem, while we note that they also seem reliable for the set covering problem. For the quadratic assignment problem, the statistical bounds has previously been found reliable when obtained from the Genetic algorithm whereas in this work they found less reliable. Finally, we provide statistical bounds to four 2-path network design problem instances for which the optimum is currently unknown.

Place, publisher, year, edition, pages
2016.
Series
Working papers in transport, tourism, information technology and microdata analysis, ISSN 1650-5581 ; 2016:06
Keyword [en]
optimization;statistical bounds
National Category
Probability Theory and Statistics
Research subject
Complex Systems – Microdata Analysis, General Microdata Analysis - methods
Identifiers
URN: urn:nbn:se:du-22581OAI: oai:DiVA.org:du-22581DiVA: diva2:946358
Available from: 2016-07-05 Created: 2016-07-05 Last updated: 2016-09-08Bibliographically approved

Open Access in DiVA

fulltext(610 kB)40 downloads
File information
File name FULLTEXT01.pdfFile size 610 kBChecksum SHA-512
b885ef66317e8a870e2f04bc8ffd9ebfd8f3ff966686886ca08971e6230a1415e260a58e046d358ff4ac4221dd4978a5c8434d5cc00e2db86a353661e7405e85
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Carling, KennethHan, Mengjie
By organisation
Statistics
Probability Theory and Statistics

Search outside of DiVA

GoogleGoogle Scholar
Total: 40 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: 357 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf