Using lagrangean relaxation for solving the minimum spanning tree problem with conflicts
Çatışma kısıtlı enküçük kapsar ağaç probleminin çözümü için lagrange gevşetmesinin kullanılması
- Tez No: 881093
- Danışmanlar: PROF. İ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: 2023
- 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ı: Endüstri Mühendisliği Bilim Dalı
- Sayfa Sayısı: 104
Özet
Bu tezde NP-zor bir problem olan Çatışma Kısıtlı Enküçük Kapsar Ağaç Problemi ele alınmaktadır. Ağırlıklı bir çizge ve birbirleriyle çatışan kenarlar kümesi verildiğinde amaçlanan çizgedeki tüm düğümleri kapsayan ve birbirleriye çatışan herhangi iki kenarı içermeyen enküçük toplam kenar ağırlığına sahip ağacı bulmaktır. Bu çalışmada eniyi amaç fonksiyon değerine bir alt sınır elde etmek için Lagrange gevşetmesi yöntemi uygulandı ve Lagrange ikil problemi altgradyan algoritması ile çözüldü. Ayrıca problemin eniyi amaç fonksiyonu değerine bir üst sınır bulabilmek için altgradyan algoritmasının her bir yinelenmesinde elde edilen olursuz çözümlere uygulanmak üzere basit bir yerel arama sezgiseli ile birleştirilmiş bir Lagrange sezgiseli tasarlandı. Bilgisayısal sonuçlar, önerilen Lagrange gevşetmesi ve Lagrange sezgiselinin yazında önerilen yöntemleri ya zaman verimliliği olarak ya da amaç fonksiyonu değeri için bulunan alt ve üst sınırların kalitesi olarak geçtiği gösterildi. Sonrasında önerilen Lagrange gevşetmesi ve Lagrange sezgiseli, önişleme süreci, olursuzluk testi ve geçerli eşitsizlikler ile beraber dal-sınır algoritmasının içerisinde kullanıldı ve bir kesin çözüm algoritması önerildi. Önerilen kesin çözüm algoritması yazındaki diğer kesin çözüm algoritmaları ve en güncel ticari tam sayı programlama çözücülerinden Gurobi 9.5.2 ile başarım açısından deneysel olarak karşılaştırıldı. Dal-sınır algoritması içerisinde Lagrange gevşetmesi kullanmanın olumlu ve olumsuz yönleri tartışıldı ve varılan sonuçlar bilgisayısal deneylerle desteklendi.
Özet (Çeviri)
This thesis studies minimum spanning tree problem with conflicts, which is known to be NP-hard. Given an edge weighted graph and a set of conflicting edge pairs, the goal is to find a minimum cost spanning tree which does not contain any conflicting edge pair. In this study, a Lagrangean Relaxation scheme is proposed to obtain lower bound on the optimum objective value and Lagrangean dual problem is solved via subgradient algorithm. A Lagrangean heuristic is also devised which is combined with a simple local search in order to obtain upper bounds from infeasible solutions obtained throughout the iterations of the subgradient algorithm. Extensive computational experiments show that the proposed Lagrangean relaxation scheme and the Lagrangean heuristic outperforms the ones proposed in the literature either in terms of time efficiency or bound quality. The Lagrangean relaxation scheme and the Lagrangean heuristic are then embedded in a branch-and-bound algorithm, along with a preprocessing procedure, an infeasibility test procedure and valid inequalities to create an exact solution algorithm. The exact solution algorithm proposed in this study is also compared with the ones in the literature and state of the art commercial solver Gurobi 9.5.2. Positive and negative aspects of using Lagrangean relaxation in a branch-and-bound algorithm are also discussed.
Benzer Tezler
- Solving the capacitated multifacility Weber problem approximately
Sınırlı sığalı çok tesisli Weber problemi için yaklaşık çözüm yöntemleri
BURAK BOYACI
Yüksek Lisans
İngilizce
2009
Endüstri ve Endüstri MühendisliğiBoğaziçi ÜniversitesiEndüstri Mühendisliği Bölümü
PROF. İ. KUBAN ALTINEL
- Birim yüklenme probleminin matematiksel ve akıllı sezgisel yaklaşımlar kullanılarak çözülmesi
Solving unit commitment problem using mathematical and intelligent heuristic approaches
ÜMMÜHAN BAŞARAN FİLİK
Doktora
Türkçe
2010
Elektrik ve Elektronik MühendisliğiAnadolu ÜniversitesiElektrik-Elektronik Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. MEHMET KURBAN
- Alt-uzay dönüşüm yöntemi ile Fır süzgeç tasarımı
Finite-duration impulse response filter design using subspace transformations
MEHMET DEVRİM AZAK
Yüksek Lisans
Türkçe
1997
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiElektronik-Haberleşme Eğitimi Ana Bilim Dalı
PROF. DR. ALİ NUR GÖNÜLEREN
- Üç serbestlik dereceli silindirik bir manipulatörün tasarımı, simülasyonu ve kontrolu
Design simulation and control of a cylindirical 3dof manipulator
S.HAYDAR İÇLİ
- Traveling salesman problem: Solution with branch and data correction algorithms
Gezgin satıcı problemi: Dallan ve sınırla ve veri düzeltme algoritmaları ile çözüm
HÜSEYİN YILMAZ
Yüksek Lisans
İngilizce
2001
Elektrik ve Elektronik MühendisliğiOrta Doğu Teknik ÜniversitesiElektrik ve Elektronik Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. CÜNEYT F. BAZLAMAÇCI