Quadratic assignment problem: linearizations and polynomial time solvable cases

ÖZETKARESEL ATAMA PROBLEM : DOĞRUSALLAŞTIRMALARVE POL NOM ZAMANDA ÇÖZÜLEB L R DURUMLARGüneş ErdoğanEndüstri Mühendisliği Bölümü DoktoraTez Yöneticisi: Prof. Barbaros TanselEkim 2006Karesel Atama Problemi (KAP) bilinen en zor kombinatoryal eniyilemeproblemlerinden biridir. QAPLIB'deki boyutu 36'yı bulan bazı testproblemlerinde başarılı çözümler elde edilmiş olsa da, tam çözüm yöntemleriboyutu 15'i geçen problemlerde genel olarak başarısız olmuştur. Bu tezde,KAP'ın ikili yapısını inceleyip yeni tamsayı programlar sunmaktayız. ?Akış-tabanlı? formülasyonlara odaklanıp, bunları geçerli eşitsizliklerle kuvvetlendirip,dallan-ve-kes algoritması ile edindiğimiz hesapsal tecrübeyi sunmaktayız.Devamla, KAP'ın Doğrusal Atama Problemine tamamen veya kısmenindirgenebilen özel hallerini sunmakta ve verilen bir problemin bu sınıfların birelemanı olup olmadığını kontrol eden prosedürler vermekteyiz. Ayrıca KAP'ınKoopmans-Beckmann formuülasyonunun polinom zamanda çözülebilir sınıflarınıortaya çıkartmaktayız. Son olarak, Bender ayrışımına dayanan kuvvetli bir altsınır sunmaktayız.Anahtar Kelimeler: Karesel Atama Problemi, Doğrusallaştırma, HesaplamaZorluğu, Polinom Zamanlı Çözülebilirlik