Algorithms for on-line vertex enumeration problem
Çevrimiçi köşe noktası problemi için algoritmalar
- Tez No: 472906
- 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: köşe noktası sayma, çevrimiçi köşe noktası sayma, algoritmalar, çok amaçlı optimizasyon, vertex enumeration, on-line vertex enumeration, algorithms, multiobjective optimization
- Yıl: 2017
- 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ı: 77
Özet
Köşe noktası sayma problemi, sonlu sayıda yarı uzayın kesişimi olarak verilmiş bir çokyüzlü P'nin bütün köşe noktalarını bulmaktır. Bu problem, çeşitli uygulama alanlarında karşılaşılan problemleri çözmek için tasarlanmış birçok algoritmanın temelini oluşturmaktadır ve bu problemleri çözmek için literatürde çok sayıda algoritma mevcuttur. Bir yanda, her yinelemede, çevrimiçi köşe noktası sayma problemi adı verilen problemleri çözen yinelemeli algoritmalar vardır. Başka bir deyişle, bu algoritmaların her yinelemesinde, şu anki çokyüzlü, P'yi tanımlayan başka bir yarı uzayla kesiştirilir. Diğer yanda ise, bütün yarı uzayları başlangıçtan itibaren girdi olarak alan simpleks türü algoritmalar vardır. Köşe noktası sayma probleminin kullanımlarından biri 'Benson'-türü çok amaçlı optimizasyon algoritmalarıdır. Bu algoritmaların amacı Pareto sınırına (amaç uzayında baskın olmayan noktalar kümesine) ulaşmak veya yaklaşmaktır. Benson Algoritması'nın her yinelemesinde, daha iyi bir dış yaklaşım bulmak için, Pareto sınırını içeren bir çokyüzlü ek bir yarı uzay ile kesiştirilir. Bu algoritma içinde kullanılan köşe noktası sayma probleminin özel bir yapısı vardır. Şöyle ki, bulunmak istenen çokyüzlünün, resesyon konisi pozitif ortant (orthant) olan sınırsız bir çokyüzlü olduğu bilinmektedir. Bu tezde, başlangıç çokyüzlüsü sınırlı olan bir çevrimiçi köşe noktası sayma problemini çözmek için kullanılan 'çift betimleme (double description)' metodunu göz önünde bulundurduk. (1) Sınırlı ya da sınırsız olması mümkün çokyüzlü P için köşe noktası sayma problemini en baştan başlayarak çözen yinelemeli bir algoritma oluşturduk. (2) Daha sonra, bu algoritmayı, sadece resesyon konisi pozitif ortant olan P için ve daha etkin çalışacak bir şekilde modifiye ettik. (3) Son olarak, bu problemlere yönelik ek bir algoritma oluşturduk. Bu algoritma için, çift betimleme yöntemini resesyon konisinin aşırı yönlerini daha etkin olarak kullanacak şekilde modifiye ettik. Bu algoritmaları detaylı bir şekilde anlatabilmek için açıklayıcı bir örnek sunduk. Bu algoritmaları, MATLAB kullanarak uygulamaya geçirdik; her bir algoritmayı 'Benson'-türü çok amaçlı bir optimizasyon algoritmasının içinde fonksiyon olarak kullandık ve rasgele oluşturulan doğrusal çok amaçlı optimizasyon problemleri için algoritmaların performanslarını test ettik. Bu doğrultuda, iki boyutlu problemler için algoritmaların çalışma süresi performanslarında bir fark yoktur. Ancak, problemlerin boyutu büyüdükçe son algoritma (Algoritma 3) diğerlerine göre daha verimli hale gelir.
Özet (Çeviri)
Vertex enumeration problem is to enumerate all vertices of a polyhedron P which is given by intersection of finitely many halfspaces. It is a basis for many algorithms designed to solve problems from various application areas and there are many algorithms to solve these problems in the literature. On the one hand, there are iterative algorithms which solve the so called 'on-line' vertex enumeration problem in each iteration. In other words, in each iteration of these algorithms, the current polyhedron is intersected with an additional halfspace that defines P. On the other hand, there are simplex-type algorithms which takes the set off all halfspaces as its input from the beginning. One of the usages of the vertex enumeration problem is the 'Benson-type' multiobjective optimization algorithms. The aim of these algorithms is to generate or approximate the Pareto frontier (the set of nondominated points in the objective space). In each iteration of the Benson's algorithm, a polyhedron which contains the Pareto frontier is intersected with an additional halfspace in order to find a finer outer approximation. The vertex enumeration problem to be used within this algorithm has a special structure. Namely, the polyhedron to be generated is known to be unbounded with a recession cone which is equal to the positive orthant. In this thesis, we consider the 'double description method' which is a method to solve an on-line vertex enumeration problem where the starting polyhedron is bounded. (1) We generate an iterative algorithm to solve the vertex enumeration problem from the scratch where polyhedron P is allowed to be bounded or unbounded. (2) Then, we slightly modify this algorithm to be more efficient while it only works for problems where the recession cone of P is known to be the positive orthant. (3) Finally, we generate an additional algorithm for these problems. For this one, we modify the double description method such that it uses the extreme directions of the recession cone more effectively. We provide an illustrative example to explain the algorithms in detail. We implement the algorithms using MATLAB; employ each of them as a function of a 'Benson-type' multiobjective optimization algorithm; and test the performances of the algorithms for randomly generated linear multiobjective optimization problems. Accordingly, for two dimensional problems, there is no clear distinction between the run-time performances of these algorithms. However, as the dimension of the vertex enumeration problem increases, the last algorithm (Algorithm 3) gets more efficient than the others.
Benzer Tezler
- On balancing social networks
Sosyal ağların dengelenmesi
ARANIYOS TEREFE WELDEGEBRIEL
Doktora
İngilizce
2019
Matematikİstanbul Teknik ÜniversitesiMatematik Mühendisliği Ana Bilim Dalı
DR. ÖĞR. ÜYESİ BURAK YILDIRAN STODOLSKY
- Görünmez çizgi ve görünmez yüzey algoritmalarının incelenmesi
Hidden line and hidden surface algorithms
TANSEL BOLAT
Yüksek Lisans
Türkçe
1997
Makine Mühendisliğiİstanbul Teknik ÜniversitesiKonstrüksiyon Ana Bilim Dalı
YRD. DOÇ. DR. HİKMET KOCABAŞ
- Gevşeme temelli kenar belirleme algoritması
Başlık çevirisi yok
GÜRAY GÜNGÖR
Yüksek Lisans
Türkçe
1998
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiBiyomedikal Mühendisliği Bilim Dalı
DOÇ. DR. TAMER ÖLMEZ
- Cisim genişlemeleri ve origami çizimleri
Field extensions and origami constructions
BURCU ŞANSAN
Yüksek Lisans
Türkçe
2019
Matematikİstanbul Teknik ÜniversitesiMatematik Mühendisliği Ana Bilim Dalı
DOÇ. DR. ERGÜN YARANERİ
- Aktif ve pasif yapı kontrolü
Active and passive structural control systems
ÖZGÜL ZOBU
Yüksek Lisans
Türkçe
1997
İnşaat Mühendisliğiİstanbul Teknik ÜniversitesiYapı Ana Bilim Dalı
DOÇ. DR. A. NECMETTİN GÜNDÜZ