Event and clock based representations of time in mathematical optimization
Matematiksel eniyilemede zamanın olay ve saat tabanlı gösterimi
- Tez No: 356940
- Danışmanlar: PROF. DR. İSMAİL KUBAN ALTINEL
- Tez Türü: Yüksek Lisans
- Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2014
- Dil: İngilizce
- Üniversite: Boğaziçi Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 121
Özet
Zamanın gösterimi işlem süresi ve verim açısından matematiksel programlamada en önemli konulardan biridir. Kesikli zaman gösterimi problemlerin çözüm süresini etkileyen pek çok sayıda ikili değişken içermektedir. Zamanın geleneksel eş uzunluklu aralıklar kullanılarak kesiklenmesi yerine, olay tabanlı gösterim uzun zaman planına sahip örnekler için önerilmektedir. Olay tabanlı yaklaşımda, olaylar dizgede değişiklik yaratan durumlardır ve matematiksel model bu olay noktalarına göre kurulur. Bu çalışmada ilk olarak iki yaklaşımın temel özelliklerini gözden geçirdik ve her iki yaklaşımın artı ve eksilerini özetledik. Daha sonra iki problemin olay tabanlı gösterimlenmesine odaklandık: kablosuz duygaç ağlarında yer seçimi-çizelgeleme ve rıhtım paylaştırma problemlemleri. Olay tabanlı gösterimi değişik problemlerde uygulamak üzere genelleştirmeye çalıştık ve geliştirmek için güçlendirici kısıtlar önerdik. Son olarak, modelleri olaylara göre ayrıştıran yeni bir dal-eder algoritması geliştirdik. Olağan gösterimin doğrusal program gevşetmesinden daha iyi olan bir sınır bulsa da, dal-eder algoritmasının başarımı sınırlıdır. Ayrıca iyi olurlu sonuçlar elde etmek için basit sezgisel yöntemler de önerdik. Deneylerimizde, her iki yaklaşımı bir karışık tam sayılı programlama çözücüsü ile çözerek karşılaştırdık ve dal-eder algoritmasının doğruluğunu sınadık. Deneylerimize göre, genel olarak olay tabanlı gösterim daha az çözüm süresine gereksinmektedir. Ancak, en iyi çözümü veren olay sayısını bulmak bilgisayısal anlamda çok emek isteyen bir iştir. Karar verici en iyi gösterimi her iki yaklaşımın artı ve eksilerini çözmek istediği problem özelinde karşılaştırarak seçmelidir.
Özet (Çeviri)
Time representation is one of the most important issues in mathematical optimization in terms of computational time and efficiency. The discrete time formulation requires large number of binary variables which affects the solution time of the problems. Instead of relying on the traditional uniform discretization of the time horizon, the event-based formulations are proposed to deal with the instances that have a long horizon. In the event-based approach, events are the situations that cause a change in the system and mathematical model is constructed based on the events. In this study, first, we briefly review the main characteristics of the two approaches and outline their advantages and disadvantages. Then, we focus on the event-based formulations of the two problems: location and scheduling problem (LASP) in wireless sensor networks (WSN) and berth allocation problem (BAP). We try to generalize the event-based formulations for different types of problems. In order to enhance the event-based formulations, we strengthen the constraints. Finally, we propose a branch and price algorithm by decomposing the models based on events. Although it provides bounds, which are better than the linear programming relaxation of original formulation, the branch and price algorithm is not very efficient. We also propose simple heuristics to find good feasible solutions. In our experiments, we compare two modeling approaches by solving the formulations using a state-of-the-art solver on the generated test bed. Then, we assess the performance of the branch and price algorithm. According to our experiments, generally the event-based formulations require less computational time. However, finding an optimum event number can require considerable computational effort. The decision maker should choose the best representation of time based on the advantages and disadvantages of the two approaches.
Benzer Tezler
- Gömülü sistemlerde sesli komut tanıma
Voice command recognation in embedded systems
CAN ÇETİN
Yüksek Lisans
Türkçe
2020
Mekatronik Mühendisliğiİstanbul Teknik ÜniversitesiMekatronik Mühendisliği Ana Bilim Dalı
PROF. DR. MUSTAFA DOĞAN
- Anahtarlı kapasite filtre devrelerinin gerçeklenmesi ve spice programı ile analizi
Realization of switched capacitor filters and analysing by spice program
CEVAT ÖNAL
Yüksek Lisans
Türkçe
1997
Elektrik ve Elektronik MühendisliğiSakarya ÜniversitesiElektrik-Elektronik Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. ABDULLAH FERİKOĞLU
- Dijital işaret işleme ve FIR filtre tasarımı algoritmaları
Digital signal processing and FIR filter design algorithms
METİN KALAYCI
Yüksek Lisans
Türkçe
1992
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiDOÇ. DR. MEHMET BÜLENT ÖRENCİK
- Anklaşman sistemi yazılım modelinin model sınamasının yapılması
Model verification of interlocking software model
DAVUT POLAT
Yüksek Lisans
Türkçe
2015
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. TOLGA OVATMAN
- Purchase prediction and item prediction with RNN using different user-item interactions
Farklı kullanıcı-ürün etkileşim türlerini kullanarak özyineli sinir ağları ile ürün ve satış tahminlemesi
FULYA ÇELEBİ SARIOĞLU
Yüksek Lisans
İngilizce
2019
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DR. ÖĞR. ÜYESİ YUSUF YASLAN