Outer approximation algorithms for convex vector optimization problems
Dışbükey vektör optimizasyon problemleri için dış yakınsama algoritmaları
- Tez No: 685057
- Danışmanlar: YRD. DOÇ. DR. FİRDEVS ULUS
- Tez Türü: Yüksek Lisans
- Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2021
- Dil: İngilizce
- Üniversite: İhsan Doğramacı Bilkent Ü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ı: 93
Özet
Literatürde, polyhedral kümeler ile dışbükey vektör optimizasyonu problemlerinin üst görüntüsünü yakınsayan bazı algoritmalar bulunmaktadır. Bu algoritmalar, her yinelemede bir köşe noktası sıralama problemi, bir de skalarizasyon problemi çözerler. Köşe noktası sıralama problemi güncel dış yakınsak kümeyi oluşturan yarı-uzayların kesiştiği köşeleri bulmak için kullanılmaktadır. Skalarizasyon problemleri hem üst görüntü üzerinde bir C-minimal eleman bulmayı hem de üst görüntüye teğet bir yarı-uzay bulunmasını sağlamaktadır. Bu çalışmada, Pascoletti-Serafini skalarizasyonu kullanan bu tip algoritmalar için genel bir algoritma yapısı sunmaktayız. Bu skalarizasyon tekniği bir referans noktasından belli bir yönde ilerleyerek üst görüntü ile referans noktası arasındaki uzaklığı bulmaktadır. Referans noktası ve yön parametresi bu skalarizasyonun parametreleridir ve referans noktası genellikle dış yakınsak kümenin bir köşe noktasıdır. Bu çalışmadaki ana motivasyonumuz Pascoletti-Serafini skalarizasyonunun parametrelerini verimli bir şekilde seçecek yöntemler geliştirmek ve bu seçimlerin algoritma verimliliği üzerindeki etkisini gözlemlemektir. Bu sebeple öncelikle yön parametresini seçmek için üç yöntem sunulmuş ve bunların algoritma üzerindeki etkisini inceleyen öncü bir hesaplama çalışması yapılmıştır. Bu öncü çalışmada köşe noktası seçimi için basit farklı yöntemler denenmiştir. Bu çalışma doğrultusunda ileride kullanılmak üzere bir yön parametresi sabitlenmiştir. Beklendiği gibi bu çalışma bize köşe noktası seçiminin de algoritmanın performansı üzerinde önemli bir etkiye sahip olduğunu göstermiştir. Bu sebeple üst görüntünün sınırında iyi dağılım gösterme potansiyeli olabilecek üç adet ek köşe noktası seçim yöntemi sunulmuştur. Bu yöntemler, literatürde bulunan köşe noktası seçimi yöntemlerinin aksine ek modeller çözmeyi gerektirmemektedir. Farklı problem kümeleri üzerinde hata payı, toplam süre ve çözüm kümesinin eleman sayısı olmak üzere üç durma kriteri kullanılarak bir hesaplamalı çalışma yapılmıştır. Önerilen varyantlar literatürdeki bazı algoritmalarla bu durma kriterlerine göre karşılatırılmıştır. Ek olarak, başka bir yakınsama ölçüsü olan hiperhacim farkı da varyantların karşılaştırılmasında kullanılmıştır. Bu çalışmanın sonucunda önerilen varyantların tatmin edici sonuçlar verdiğini gözlemlemekteyiz. Hata payı durma kriteri olarak alındığında önerilen varyantlar, literatürdeki varyantlardan daha kısa sürede problemi çözmektedir. Sabit süre alındığındaysa yakınsama ölçüleri bakımından önerilen varyantlar genellikle daha iyi sonuçlar bulmaktadır. Sabit çözüm kümesi durma kriteri olarak alındığında literatürdeki algoritmalar genellikle problemleri daha iyi yakınsamakta ancak bu durumda çözüm süreleri önerilen varyantlardan daha uzun olmaktadır.
Özet (Çeviri)
There are different outer approximation algorithms in the literature that are designed to solve convex vector optimization problems in the sense that they approximate the upper image using polyhedral sets. At each iteration, these algorithms solve vertex enumeration and scalarization problems. The vertex enumeration problem is used to find the vertex representation of the current outer approximation. The scalarization problem is used in order to generate a weakly C-minimal element of the upper image as well as a supporting halfspace that supports the upper image at that point. In this study, we present a general framework of such algorithm in which the Pascoletti-Serafini scalarization is used. This scalarization finds the minimum `distance' from a reference point, which is usually taken as a vertex of the current outer approximation, to the upper image through a given direction. The reference point and the direction vector are the parameters for this scalarization. The motivation of this study is to come up with efficient methods to select the parameters of the Pascoletti-Serrafini scalarization and analyze the effects of these parameter selections on the performance of the algorithm. We first propose three rules to choose the direction parameter at each iteration. We conduct a preliminary computational study to observe the effects of these rules under various, rather simple rules for vertex selection. Depending on the results of the preliminary analysis, we fix a direction selection rule to continue with. Moreover, we observe that vertex selection also has a significant impact on the performance, as expected. Then, we propose additional vertex selection rules, which are slightly more complicated than the previous ones, and are designed with the motivation that they generate a well-distributed points on the boundary of the upper image. Different from the existing vertex selection rules from the literature, they do not require to solve additional single-objective optimization problems. Using some test problems, we conduct a computational study where three different measures set as the stopping criteria: the approximation error, the runtime, and the cardinality of the solution set. We compare the proposed variants and some algorithms from the literature in terms of these measures that are used as the stopping criteria as well as an additional proximity measure, hypervolume gap. We observe that the proposed variants have satisfactory results especially in terms of runtime. When the approximation error is chosen as the stopping criteria, the proposed variants require less CPU time compared to the algorithms from the literature. Under fixed runtime, they return better proximity measures in general. Under fixed cardinality, the algorithms from the literature yield better proximity measures, but they require significantly more CPU time than the proposed variants.
Benzer Tezler
- A new geometric duality and approximation algorithms for convex vector optimization problems
Dışbükey vektör eniyileme problemleri için yeni bir geometrik çifteşlik teorisi ve dış yaklaşıklama algoritmaları
SİMAY TEKGÜL
Yüksek Lisans
İngilizce
2021
Endüstri ve Endüstri Mühendisliğiİhsan Doğramacı Bilkent ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DR. ÖĞR. ÜYESİ FİRDEVS ULUS
DR. ÖĞR. ÜYESİ ÇAĞIN ARARAT
- Norm minimization-based convex vector optimization algorithms
Norm enküçüklemeye dayalı dişbükey vektör eniyileme algoritmaları
MUHAMMAD UMER
Doktora
İngilizce
2022
Endüstri ve Endüstri Mühendisliğiİhsan Doğramacı Bilkent ÜniversitesiEndüstri Mühendisliği ve Operasyon Yönetimi
DR. ÖĞR. ÜYESİ FİRDEVS ULUS
DR. ÖĞR. ÜYESİ ÇAĞIN ARARAT
- Outer approximation algorithms for the congested p-median problem
Kalabalık p-ortanca problemi için dış yaklaşım algoritması
SELVA SELFUN
Yüksek Lisans
İngilizce
2011
Endüstri ve Endüstri Mühendisliğiİhsan Doğramacı Bilkent ÜniversitesiEndüstri Mühendisliği Bölümü
DOÇ. DR. EMRE ALPER YILDIRIM
DOÇ. DR. HANDE YAMAN
- On outer approximations of copositive formulations of various nonconvex optimization problems
Çeşitli konveks olmayan problemlerin kopozitif formulasyonlarının dıştan yaklaşımları üzerine
YAKUP GÖRKEM GÖKMEN
Doktora
İngilizce
2019
Endüstri ve Endüstri MühendisliğiKoç ÜniversitesiEndüstri Mühendisliği ve Operasyon Yönetimi
DR. EMRE ALPER YILDIRIM