Çatışma kısıtlı enküçük kapsar ağaç probleminin çözümü için lagrange gevşetmesinin kullanılması

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.