du.sePublikationer
Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • chicago-author-date
  • chicago-note-bibliography
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
GRASP and statistical bounds for heuristic solutions to combinatorial problems
Högskolan Dalarna, Akademin Industri och samhälle, Statistik.ORCID-id: 0000-0003-2317-9157
Högskolan Dalarna, Akademin Industri och samhälle, Statistik.ORCID-id: 0000-0003-4212-8582
2016 (Engelska)Rapport (Övrigt vetenskapligt)
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.

Ort, förlag, år, upplaga, sidor
2016.
Serie
Working papers in transport, tourism, information technology and microdata analysis, ISSN 1650-5581 ; 2016:06
Nyckelord [en]
optimization;statistical bounds
Nationell ämneskategori
Sannolikhetsteori och statistik
Forskningsämne
Komplexa system - mikrodataanalys, Allmänt Mikrodataaanalys - metod
Identifikatorer
URN: urn:nbn:se:du-22581OAI: oai:DiVA.org:du-22581DiVA, id: diva2:946358
Tillgänglig från: 2016-07-05 Skapad: 2016-07-05 Senast uppdaterad: 2019-08-26Bibliografiskt granskad

Open Access i DiVA

fulltext(610 kB)83 nedladdningar
Filinformation
Filnamn FULLTEXT01.pdfFilstorlek 610 kBChecksumma SHA-512
b885ef66317e8a870e2f04bc8ffd9ebfd8f3ff966686886ca08971e6230a1415e260a58e046d358ff4ac4221dd4978a5c8434d5cc00e2db86a353661e7405e85
Typ fulltextMimetyp application/pdf

Personposter BETA

Carling, Kenneth

Sök vidare i DiVA

Av författaren/redaktören
Carling, KennethHan, Mengjie
Av organisationen
Statistik
Sannolikhetsteori och statistik

Sök vidare utanför DiVA

GoogleGoogle Scholar
Totalt: 83 nedladdningar
Antalet nedladdningar är summan av nedladdningar för alla fulltexter. Det kan inkludera t.ex tidigare versioner som nu inte längre är tillgängliga.

urn-nbn

Altmetricpoäng

urn-nbn
Totalt: 531 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • chicago-author-date
  • chicago-note-bibliography
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf