A study on the quadratic assignment problem with symmetric rank1 input matrices دراسة مسألة التعيين التربيعية مع مصفوفات إدخال من الرتبة الأولى

Abstract

The quadratic assignment problem (QAP) is one of the most difficult combinatorial optimization problems in the NPhard class In this article we study a simple class of the symmetric quadratic assignment problems where the input matrices are rank one matrices We show that it remains NPhard if the objective function is convex otherwise it is polynomial time solvable We give a very small linearization for this special QAP Finally some lower bounds are discussed

تعتبر مسألة التعيين التربيعية من أصعب مسائل المثلويات التوافقية الشاقة والتي تعرف بـ NP hard (أي المسائل التي لا يقدر زمن حلها بكثيرة حدود في n حجم المسألة) ندرس في بحثنا هذا صفا بسيطا من مسائل التعيين التربيعية المتناظرة التي تكون فيها مصفوفات الإدخال مصفوفات من الرتبة الأولى ونبرهن على أن هذا النوع من المسائل يبقى من فئة المسائل الشاقة NP hard في حال كون دالة الهدف محدبة وفيما عدا ذلك فإنها بسيطة قابلة للحل وزمن حسابها على شكل كثيرة حدود تتزايد مع تزايد n حجم المسألة علاوة على ذلك، فإننا نحدد خطية ذلك الصف من مسائل التعيين التربيعية كخطوة أساسية في عملية إيجاد الحل الأمثل، كما ندرس بعض الحدود الدنيا للصف المذكور