Primal-dual heuristics for solving the set covering problem
Küme örtüleme problemlerinin çözümü için temel-eşlenik sezgiseller
- Tez No: 309383
- Danışmanlar: DOÇ. DR. Ş.İLKER BİRBİL, YRD. DOÇ. DR. KEREM BÜLBÜL
- Tez Türü: Yüksek Lisans
- Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2009
- Dil: İngilizce
- Üniversite: Sabancı Üniversitesi
- Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 50
Özet
Küme örtüleme problemi çizelgeleme, üretim, hizmet planlama, ağ eniyilemesi, uziletişim gibi pek çok alanda uygulanan iyi bilinen bir birleşi eniyileme problemidir. Küme örtüleme probleminin NP-zor olduğu kanıtlanmış olup, problemin etkin bir şekilde çözümüne yönelik çok sayıda birerleme algoritmaları ve sezgiseller geliştirilmiştir. Bu çalışmanın temel amacı küme örtüleme problemi için etkin bir sezgisel geliştirmektir. Sezgisel temel-eşlenik yaklaşımına dayalı olup literatürde NP-zor birleşi eniyileme problemlerini yaklaşıklamak için kullanılmaktadır.Bu çalışmada, sezgiselin başarımını değerlendirmek için sayısal çözümlemelerle birlikte sezgiselin geliştirilme aşamalarında elde ettiğimiz gözlemler sunulmaktadır. Elde edilen sonuçlar sezgiselin çözüm kalitesi ve hesaplama zamanı açısından iyi sonuçlar verdiğini göstermektedir. Bunun yanısıra sezgiselin basit, kolay uygulanabilir, ve büyük ölçekli problemleri etkin bir şekilde çözme potansiyeli olduğunu göstermektedir.
Özet (Çeviri)
The set covering problem (SCP) is a well known combinatorial optimization problem applied widely in areas such as; scheduling, manufacturing, service planning, network optimization, telecommunications, and so on. It has been already shown that SCP is NP-hard in the strong sense. Therefore, many heuristic and enumerative algorithms have been developed to solve SCP effectively. The primary purpose of the present study is to develop an effective heuristic for SCP. The heuristic is based on a primal-dual approach which is commonly used in the literature for approximating NP-hard optimization problems.In this study, we present numerical results to evaluate the performance of the heuristics as well as our observations throughout the development process. Our results indicate that the heuristic is able to produce good results in terms of both solution quality and computation time. Moreover, we show that the proposed heuristic is simple, easy to implement and has a potential to solve large-scale SCPs efficiently.
Benzer Tezler
- Efficient algorithms for the minimum cost perfect matching problem on general graphs
Genel çizelgede en küçük maliyetli tam eşleme problemi için etkin algoritmalar
ALPER ATAMTÜRK
Yüksek Lisans
İngilizce
1993
Endüstri ve Endüstri Mühendisliğiİhsan Doğramacı Bilkent ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. MUSTAFA AKGÜL
- Sıkıştırılmış algılamada sezgisel algoritmaların kullanımına dayalı yöntemlerin incelenmesi ve geliştirilmesi
Analyzing and development of heuristic algorithms in compressed sensing
MURAT EMRE ERKOÇ
Yüksek Lisans
Türkçe
2017
Elektrik ve Elektronik MühendisliğiErciyes ÜniversitesiElektrik-Elektronik Mühendisliği Ana Bilim Dalı
PROF. DR. NURHAN KARABOĞA
- Ağ tasarım problemlerinde farklı bağlantılılıkların incelenmesi
The examination of different connectivities on network design problems
HAKAN KUTUCU
- Yöneylem araştırmasında şebeke modellerine vekil kısıt uygulamaları
Surrogate constraint applications to network models in operations research
AYŞE SAKALLIOĞLU
Yüksek Lisans
Türkçe
2019
MatematikGiresun ÜniversitesiMatematik Ana Bilim Dalı
DR. ÖĞR. ÜYESİ HANDE GÜNAY AKDEMİR
- İç nokta algoritmaları ve simpleks yöntemi ile zamansal karşılaştırma
Interior point algorithms and comparsion regarding time with the simplex method
E. ESER BAYLAKOĞLU