A Polyhedral approach to quadratic assignment problem

Abstract

ÖZET KARESEL ATAMA PROBLEMİNE POLYHEDRAL BİR YAKLAŞIM Ahmet Sertaç Murat Koksaldı Endüstri Mühendisliği, Yüksek Lisans Tez Yöneticisi : Doç. Mustafa Akgül Eylül, 1994 Bu tez çalışmasında, Karesel Atama Problemi ele alınmıştır. Karesel Atama Problemi İVP-zorlukta olduğu için, polinom zamanlı bir çözüm yöntemi mevcut değildir. Olabilir çözümlerin en iyiliğinin ispatı ancak küçük boyutlu problemlerde mümkündür. Çalışmamızda, Karesel Atama Problemi polyhedral bir açıdan ele alınmıştır. Karesel Atama Probleminin graf teorik bir ifadesi tanımlanmıştır. Daha sonra, Karesel Atama Poytopu ve, geçerli bazı eşitsizlik ve eşitlik alt kümeleri tanımlanmıştır. Son olarak da, Karesel Atama Probleminin yeni ifadesinin kullanıldığı bir poly hedral kesen düzlem yöntemi ile yapılan testlerin sonuçlan verilmiştir. Anahtar Sözcükler: Karesel Atama Problemi, Karesel Atama Poytopu, polyhedral kesen düzlem yöntemi

ABSTRACT A POLYHEDRAL APPROACH TO QUADRATIC ASSIGNMENT PROBLEM Ahmet Sertaç Murat Koksaldı M.S. in Industrial Engineering Supervisor: Assoc. Prof. Mustafa Akgül September, 1994 In this thesis, Quadratic Assignment Problem is considered. Since Quadratic Assignment Problem is jVP-hard, no polynomial time exact solution method exists. Proving optimality of solutions to Quadratic Assignment Problems has been limited to instances of small dimension. In this study, Quadratic Assign ment Problem is handled from a polyhedral point of view. A graph theoretic formulation of the problem is presented. Later, Quadratic Assignment Poly- tope is defined and subsets of valid equalities and inequalities for Quadratic Assignment Polytope is given. Finally, results of the experiments with a poly hedral cutting plane algorithm using the new formulation is also presented. Keywords: Quadratic Assignment Problem, Quadratic Assignment Polytope, polyhedral cutting plane algorithm IV