Geri Dön

Quadratic assignment problem: linearizations and polynomial time solvable cases

Karesel atama problemi: doğrusallaştırmalar ve polinom zamanda çözülebilir durumlar

PDF İndir

  1. Tez No: 180668
  2. Yazar: GÜNEŞ ERDOĞAN
  3. Danışmanlar: PROF. BARBAROS TANSEL
  4. Tez Türü: Doktora
  5. Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
  6. Anahtar Kelimeler: Karesel Atama Problemi, Doğrusallaştırma, HesaplamaZorluğu, Polinom Zamanlı Çözülebilirlik, Quadratic Assignment Problem, Linearization, ComputationalComplexity, Polynomial Time Solvability
  7. Yıl: 2006
  8. Dil: İngilizce
  9. Üniversite: İhsan Doğramacı Bilkent Üniversitesi
  10. Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. Sayfa Sayısı: 134

Özet

Ö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.

Özet (Çeviri)

ABSTRACTQUADRATIC ASSIGNMENT PROBLEM: LINEARIZATIONSAND POLYNOMIAL TIME SOLVABLE CASESGüneş ErdoğanPh.D. in Industrial EngineeringSupervisor: Prof. Barbaros TanselOctober 2006The Quadratic Assignment Problem (QAP) is one of the hardest combinatorialoptimization problems known. Exact solution attempts proposed for instances ofsize larger than 15 have been generally unsuccessful even though successfulimplementations have been reported on some test problems from the QAPLIBup to size 36. In this dissertation, we analyze the binary structure of the QAPand present new IP formulations. We focus on ?flow-based? formulations,strengthen the formulations with valid inequalities, and report computationalexperience with a branch-and-cut algorithm. Next, we present new classes ofinstances of the QAP that can be completely or partially reduced to the LinearAssignment Problem and give procedures to check whether or not an instance isan element of one of these classes. We also identify classes of instances of theKoopmans-Beckmann form of the QAP that are solvable in polynomial time.Lastly, we present a strong lower bound based on Bender?s decomposition.

Benzer Tezler

  1. Tez No

    167015

    Robust set-valued estimation and its application to in-flinht alignment of sins

    Dayanıklı küme değerli kestirim ve bunun gövdeye bağlı ataletsel seyrüsefer sistemlerinin uçuş sırasında hizalanması konusuna uygulanması

    NİYAZİ BURAK SEYMEN

    Yüksek Lisans

    İngilizce

    İngilizce

    2005

    Elektrik ve Elektronik MühendisliğiOrta Doğu Teknik Üniversitesi

    Elektrik ve Elektronik Mühendisliği Ana Bilim Dalı

    PROF. DR. MÜBECCEL DEMİREKLER

  2. Tez No

    382649

    Two-finger keyboard design for turkish language

    Türk dili için iki-parmak klavye tasarımı

    HÜSEYİN KARATEKE

    Yüksek Lisans

    İngilizce

    İngilizce

    2015

    Endüstri ve Endüstri MühendisliğiGaziantep Üniversitesi

    Endüstri Mühendisliği Ana Bilim Dalı

    DOÇ. DR. KÜRŞAD AĞPAK

  3. Tez No

    438049

    Karesel atama probleminin tavlama benzetimi ve paralel programlama teknikleri kullanarak çözümü

    Solving quadratic assignment problem using simulated annealing and parallel programming techniques

    SELAHATTİN AKKAŞ

    Yüksek Lisans

    Türkçe

    Türkçe

    2016

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolPamukkale Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    DOÇ. DR. KADİR KAVAKLIOĞLU

  4. Tez No

    486795

    Parallel evolutionary algorithms for quadratic assignment problem

    İkinci derece atama problemi için paralel evrimsel algoritmalar

    ALPER KIZIL

    Yüksek Lisans

    İngilizce

    İngilizce

    2017

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolYaşar Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    YRD. DOÇ. DR. KORHAN KARABULUT

  5. Tez No

    275871

    A heuristic solution algorithm to quadratic assignment problem

    Kareli atama problemleri için sezgisel yaklaşım

    AYŞE HANDE EROL

    Yüksek Lisans

    İngilizce

    İngilizce

    2010

    Endüstri ve Endüstri MühendisliğiMarmara Üniversitesi

    Endüstri Mühendisliği Ana Bilim Dalı

    YRD. DOÇ. DR. SEROL BULKAN

Geri Dön