Algorithms for on-line vertex enumeration problem

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. Anahtar sözcükler: köşe noktası sayma, çevrimiçi köşe noktası sayma, algoritmalar, çok amaçlı optimizasyon.