Minimum hub cover problem: Solution methods and applications
En küçük göbek kapsama problemi: Çözüm metodları ve uygulamalar
- Tez No: 389474
- Danışmanlar: PROF. DR. ŞEVKET İLKER BİRBİL, DOÇ. DR. KEREM BÜLBÜL
- Tez Türü: Doktora
- Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2014
- 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ı: 127
Özet
En küçük göbek kapsama problemi, çizge veri tabanları üzerinde sorgulama alanında literatüre kazandırılmış yeni bir eniyileme problemidir. Problem, çizge sorgularının hızlandırılması için yeni bir çizge gösterim şekli olarak önerilmiştir. Bu gösterim şekli ile bir çizge veritabanı, o çizgenin düğümlerinin bir alt kümesi cinsinden ifade edilmektedir. Bu alt küme üzerinden sorgu işlemek, sorgu süresinin azalmasını ve sorgu sürecinin verimliliğinin artmasını sağlamaktadır. Bu çalışmada en az sayıda düğümle bir çizgeyi ifade etme problemini en küçük göbek kapsama problemi olarak tanımlıyoruz. Bu alt küme üzerinden sorgulama işlemi yapılmasının sorgu verimliliğini artırdığını ve mevcut yöntemlere göre avantaj sağladığını gösteriyoruz. Bu çalışmada en küçük göbek kapsama problemi içlerinde 0-1 tamsayılı programlama formülasyonu ile ikinci dereceden tamsayılı programla modelinin de olduğu farklı matematiksel programlama modelleri tanıtıyoruz. İkinci dereceden tamsayılı programlama modelinin gevşetilmesini kullanarak yarıbelgili programlama formülasyonu elde ediyoruz. Doğrusal ve yarıbelgili gevşetme modellerini kullanan yuvarlama yöntemleri önererek bu yöntemlerin deneysel performanslarını karşılaştırıyoruz. Ayrıca düzeysel çizge veri tabanlarında nesne tanımlama, biyometrik kimlik belirleme gibi sorgu işleme uygulamaları olan düzeysel çizgelere odaklanıp iyi çözümler üreten hızlı sezgisel geliştiriyoruz. En küçük göbek kapsama problemini düzeysel çizgeler üzerinde performans garantisi veren bir yaklaşıklama algoritması tanıtıyoruz. Çeşitli sayısal çalışmalar ile tezde önerilen çözüm yöntemlerinin deneysel performanslarını ölçüyoruz.
Özet (Çeviri)
The minimum hub cover is a new NP-hard optimization problem that has been recently introduced to the literature in the context of graph query processing on graph databases. The problem has been proposed as a new graph representation model to expedite graph queries. With this representation, a graph database can be represented by a small subset of graph vertices. Searching over only that subset of vertices decreases the response time of a query and increases the efficiency of graph query processing. We introduce the problem of finding a subgraph including the minimum number of vertices as an optimization problem referred to as the minimum hub cover problem. We demonstrate that searching a query over the vertices in minimum hub cover increases the efficiency of query processing and surpasses the existing search methods. We also introduce several mathematical programming models. In particular, we give two binary integer programming formulations as well as a novel quadratic integer programming formulation. We use the linear programming relaxations of the binary integer programming models. Our relaxation for the quadratic integer programming model leads to a semidefinite programming formulation. We also present several rounding heuristics to obtain integral solutions after solving the proposed relaxations. We also focus on planar graphs which have many applications in planar graph query processing and devise fast heuristics with good solution quality for minimum hub cover. We also study an approximation algorithm with a performance guarantee to solve the minimum hub cover problem on planar graphs. We conduct several numerical studies to analyze the empirical performances of solution methods proposed in this thesis.
Benzer Tezler
- Elektrikli bisikletler için fırçasız doğru akım motoru tasarımı ve üretimi
Design and implementation of brushless dc motor for electric bicycles
GAMZE TANÇ
Yüksek Lisans
Türkçe
2014
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiElektrik Mühendisliği Ana Bilim Dalı
DOÇ. DR. ÖZGÜR ÜSTÜN
- Konteyner kapasite ve taşıma planlama politikalarının sistem dinamiği yaklaşımı ile modellemesi
The system dynamics modelling for container capacity & transportation planning policies
MEHMET ÇAĞATAY BAHADIR
Doktora
Türkçe
2020
Endüstri ve Endüstri Mühendisliğiİstanbul Teknik Üniversitesiİşletme Mühendisliği Ana Bilim Dalı
PROF. DR. HATİCE CAMGÖZ AKDAĞ
- Ham petrol ve doğal gaz fiyatlarında oynaklık modellemesi
Volatility modelling in crude oil and natural gas prices
ÖMÜR SALTIK
- Rüzgar türbini göbeğinin yapısal tasarımı ve optimizasyonu
Structural design and optimization of wind turbine hub
SERKAN DEMİRCİ
Yüksek Lisans
Türkçe
2011
Mühendislik BilimleriKocaeli ÜniversitesiMakine Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. MURAT MAKARACI
- Hub location problem for air-ground transportation systems with time restrictions
Hava ve kara taşımacılık sisteminde zaman kısıtlı ana dağıtım üssü yer seçimi problemi
SEDA ELMASTAŞ
Yüksek Lisans
İngilizce
2006
Endüstri ve Endüstri Mühendisliğiİhsan Doğramacı Bilkent ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
Y.DOÇ. BAHAR YETİŞ KARA
Y.DOÇ. HANDE YAMAN