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

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.Keywords: Quadratic Assignment Problem, Linearization, ComputationalComplexity, Polynomial Time Solvability