Geri Dön

Outer approximation algorithms for convex vector optimization problems

Dışbükey vektör optimizasyon problemleri için dış yakınsama algoritmaları

  1. Tez No: 685057
  2. Yazar: İREM NUR KESKİN
  3. Danışmanlar: YRD. DOÇ. DR. FİRDEVS ULUS
  4. Tez Türü: Yüksek Lisans
  5. Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2021
  8. Dil: İngilizce
  9. Üniversite: İhsan Doğramacı Bilkent Üniversitesi
  10. Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. 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

  1. 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

    İngilizce

    2021

    Endüstri ve Endüstri Mühendisliğiİhsan Doğramacı Bilkent Üniversitesi

    Endüstri Mühendisliği Ana Bilim Dalı

    DR. ÖĞR. ÜYESİ FİRDEVS ULUS

    DR. ÖĞR. ÜYESİ ÇAĞIN ARARAT

  2. Algorithms for vector optimization problems

    Başlık çevirisi yok

    FİRDEVS ULUS

    Doktora

    İngilizce

    İngilizce

    2015

    Mühendislik BilimleriPrinceton University

    PROF. BIRGIT RUDLOFF

  3. Norm minimization-based convex vector optimization algorithms

    Norm enküçüklemeye dayalı dişbükey vektör eniyileme algoritmaları

    MUHAMMAD UMER

    Doktora

    İngilizce

    İngilizce

    2022

    Endüstri ve Endüstri Mühendisliğiİhsan Doğramacı Bilkent Üniversitesi

    Endüstri Mühendisliği ve Operasyon Yönetimi

    DR. ÖĞR. ÜYESİ FİRDEVS ULUS

    DR. ÖĞR. ÜYESİ ÇAĞIN ARARAT

  4. 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

    İngilizce

    2011

    Endüstri ve Endüstri Mühendisliğiİhsan Doğramacı Bilkent Üniversitesi

    Endüstri Mühendisliği Bölümü

    DOÇ. DR. EMRE ALPER YILDIRIM

    DOÇ. DR. HANDE YAMAN

  5. 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

    İngilizce

    2019

    Endüstri ve Endüstri MühendisliğiKoç Üniversitesi

    Endüstri Mühendisliği ve Operasyon Yönetimi

    DR. EMRE ALPER YILDIRIM