Minimum Ağırlıklı Maksimum Eşleme Problemi İçin Polihedral Yaklaşımlar

Date

2016-12-31

Author

Tural, Mustafa Kemal

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

245
views

0
downloads

Bizim bu çalışmada ele alacağımız problem NP-hard kategorisinde bulunan Minimum Ağırlıklı Maksimal Eşleme (MAME) problemidir. Çalışmamızda, MAME problemlerini çözmek için kullanılan bilinen bir tam sayılı programlama formülasyonunu ele alıp daha da geliştirmeyi planlıyoruz. Formülasyonu şu ana kadar çözülebilenlerden daha büyük boyutlu problemleri çözebilecek şekilde güçlendirmeyi amaçlıyoruz. Problem için güçlü geçerli eşitsizlikler (strong valid inequalities) bularak bunların formülasyona eklenmesi ile çözüm uzayının daraltılması ve dolayısı ile daha hızlı en iyi tamsayılı çözümün bulunmasını hedefliyoruz. Aynı zamanda belli özel çizgeler için maksimal eşleme politopunu karakterize etmek istiyoruz.

Subject Keywords

Çizge Kuramı, Kombinatorik, Optimizasyon

URI

https://hdl.handle.net/11511/61954

Collections

Department of Industrial Engineering, Project and Design

Suggestions

OpenMETU
Core

Orta büyümeli grupların Schreier çizgelerinin spektrumları Benli, Mustafa Gökhan(2017-12-31) Bu projede orta büyümeli grupların Schreier çizgelerinin spektrumları hakkında araştırma yapılacaktır. Grubun yapısı ile spektrum arasındaki bağlantı incelenecektir.
Çok Kriterli Problemlerde Karar Vericinin Tercih Fonksiyonunun Tahmin Edilmesi İçin Yaklaşımlar Karakaya, Gülşah(2018-12-31) Birden fazla ve genellikle birbirleri ile çelişen kriterlerin bulunduğu çok kriterli karar verme problemlerinde en iyi - karar vericinin en beğendiği - çözümü bulma işi kolay değildir. Karar vericinin en beğendiği çözümü bulmak için uygulanan yöntemlerden birisi interaktif bir şekilde karar vericiden tercih bilgisini almaktır. Alınan bilgiler ışığında yeni sorular sorularak en beğenilen çözüme yaklaşılması hedeflenir. Karar vericinin tercih fonksiyonu tahmin edilebilirse, bu tercih fonksiyonuna has özellikl...
Ağaç Türü Çizgelerde Maksimal Eşleme Politopu Tural, Mustafa Kemal (2015-09-09) Verilen ağırlıklı bir çizge için, minimum ağırlıklı maksimal eşleme (MAME) problemi, çizgede en az ağırlığa sahip bir maksimal eşleme bulma problemidir. MAME problemi genel olarak NP-hard bir problem olmasına rağmen özel bazı çizge sınıflarında polinom zamanda çözülebilmektedir. Örneğin, ağaç türü çizgelerde bütün kenar ağırlıkların bir olduğu durumda MAME probleminin lineer zamanda çözülebildiği gösterilmiştir. Bu çalışmada, ağaç türü çizgeler için maksimal eşlemelerin insidans vektörler...
Çok Dönemli Randevu Çizelgeleme Problemi İçin Rassal Programlama Yaklaşımları Batun, Sakine; Bilgiç, Utku Tarik(2017-12-31) Randevu çizelgeleme problemleri özellikle sağlık sistemlerinde önemli bir yere sahiptir. Doktor randevularının oluşturulması, ameliyathanelerin çizelgelenmesi, periyodik tedavilerin çizelgelenmesi ve kıt teşhis kaynaklarının kullanımının planlanması, problemin sağlık sistemlerinde en sık karşılaşılan örnekleridir. Randevu çizelgeleri oluşturulurken gözetilen hasta bekleme zamanlarının azaltılması, doktorların ve diğer kaynakların atıl zamanlarının azaltılması, fazla mesai sürelerinin azaltılması gibi amaçla...
Çok Kriterli Tam Sayılı Optimizasyon Problemlerinde Etkin Çözümlerin Bulunması İçin Yaklaşımlar Karakaya, Gülşah(2016-12-31) Çok kriterli optimizasyon problemlerinde, tek kriterli optimizasyon problemlerinden farklı olarak genellikle birbirleri ile çelişen kriterler göz önüne alınarak tercih edilen çözüm/çözümler bulunur. Literatürde iki kriterli optimizasyon problemleri için çalışmalara sıkça rastlanırken üç ya da daha fazla kriterli optimizasyon problemleri için yapılan çalışmaların sayısı daha kısıtlıdır. Bu projede çok kriterli (iki, üç ya da daha fazla) tam sayılı optimizasyon problemlerinde tüm etkin çözümleri bulabilen bir...

Citation Formats

M. K. Tural, “Minimum Ağırlıklı Maksimum Eşleme Problemi İçin Polihedral Yaklaşımlar,” 2016. Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/61954.