خوارزمية كارماكار

خوارزمية كارماركار هي خوارزمية ابتكرها ناريندرا كارماركار عام 1984 لحل مسائل البرمجة الخطية . وكانت أول خوارزمية فعالة نسبياً تحل هذه المسائل في زمن متعدد الحدود . أما طريقة القطع الناقص فهي أيضاً متعددة الحدود، لكنها أثبتت عدم كفاءتها عملياً.

يشير إلى${\displaystyle n}$عدد المتغيرات، m، وعدد قيود عدم المساواة، و${\displaystyle L}$يتطلب خوارزمية كارماركار عدد بتات الإدخال للخوارزمية${\displaystyle O(m^{1.5}n^{2}L)}$العمليات على${\displaystyle O(L)}$الأرقام المكونة من خانات، مقارنةً بـ${\displaystyle O(n^{3}(n+m)L)}$تتطلب خوارزمية القطع الناقص عمليات مماثلة. ^{[ 1 ]} في مسائل "المربع"، عندما يكون m من رتبة O( n )، تتطلب خوارزمية كارماركار${\displaystyle O(n^{3.5}L)}$العمليات على${\displaystyle O(L)}$الأرقام المكونة من خانات، مقارنةً بـ${\displaystyle O(n^{4}L)}$تُجرى هذه العمليات لخوارزمية القطع الناقص. وبالتالي، يكون زمن تشغيل خوارزمية كارماركار هو $${\displaystyle O(n^{3.5}L^{2}\cdot \log L\cdot \log \log L),}$$ باستخدام الضرب القائم على تحويل فورييه السريع (انظر ترميز Big O ).

تندرج خوارزمية كارماركار ضمن فئة طرق النقطة الداخلية : لا يتبع التخمين الحالي للحل حدود المجموعة الممكنة كما هو الحال في طريقة سيمبلكس ، ولكنه يتحرك عبر المنطقة الداخلية للمنطقة الممكنة، مما يحسن تقريب الحل الأمثل بنسبة محددة مع كل تكرار ويتقارب إلى حل أمثل ببيانات نسبية. ^{[ 2 ]}

لنفترض مسألة برمجة خطية في شكل مصفوفة:

تحدد خوارزمية كارماركار الاتجاه الأمثل التالي الممكن، ثم تُقلّص نطاقها بمعامل γ يتراوح بين 0 و1 . وقد وُصفت هذه الخوارزمية في عدد من المصادر. ^{[ 3 ] [ 4 ] [ 5 ] [ 6 ] [ 7 ] [ 8 ]} كما قام كارماركار بتوسيع نطاق هذه الطريقة ^{[ 9 ] [ 10 ] [ 11 ] [ 12 ]} لحل المسائل ذات القيود الصحيحة والمسائل غير المحدبة. ^{[ 13 ]}

خوارزمية التحجيم الأفيني

المدخلات: أ، ب، ج${\displaystyle x^{0}}$، معيار التوقف ، γ .

${\displaystyle k\leftarrow 0}$نفّذ أثناء عدم استيفاء معيار التوقف${\displaystyle v^{k}\leftarrow b-Ax^{k}}$${\displaystyle D_{v}\leftarrow \operatorname {diag} (v_{1}^{k},\ldots ,v_{m}^{k})}$${\displaystyle h_{x}\leftarrow (A^{T}D_{v}^{-2}A)^{-1}c}$${\displaystyle h_{v}\leftarrow -Ah_{x}}$لو${\displaystyle h_{v}\geq 0}$ثم أعد قيمة غير محدودة ${\displaystyle \alpha \leftarrow \gamma \cdot \min\{-v_{i}^{k}/(h_{v})_{i}\,\,|\,\,(h_{v})_{i}<0,\,i=1,\ldots ,m\}}$${\displaystyle x^{k+1}\leftarrow x^{k}+\alpha h_{x}}$${\displaystyle k\leftarrow k+1}$نهاية التكرار

لنفترض البرنامج الخطي $${\displaystyle {\begin{array}{lrclr}{\text{maximize}}&x_{1}+x_{2}\\{\text{subject to}}&2px_{1}+x_{2}&\leq &p^{2}+1,&p=0.0,0.1,0.2,\ldots ,0.9,1.0.\end{array}}}$$ أي أن هناك متغيرين${\displaystyle x_{1},x_{2}}$و11 قيدًا مرتبطة بقيم متغيرة لـ${\displaystyle p}$يوضح هذا الشكل كل تكرار للخوارزمية كنقاط دائرية حمراء. أما القيود فتظهر كخطوط زرقاء.

عندما ابتكر كارماركار الخوارزمية، كان يعمل لدى شركة آي بي إم كباحث ما بعد الدكتوراه في مختبر أبحاث سان خوسيه التابع لها في كاليفورنيا. وفي 11 أغسطس/آب 1983، ألقى ندوة في جامعة ستانفورد شرح فيها الخوارزمية، مع الإشارة إلى أن جهة عمله لا تزال مسجلة باسم آي بي إم. وبحلول خريف عام 1983، بدأ كارماركار العمل في شركة إيه تي آند تي ، وقدّم بحثه إلى ندوة جمعية آلات الحوسبة (ACM) حول نظرية الحوسبة (STOC) لعام 1984 (التي عُقدت في الفترة من 30 أبريل/نيسان إلى 2 مايو/أيار 1984)، مُشيرًا إلى أن مختبرات إيه تي آند تي بيل هي جهة عمله. ^{[ 16 ]} وبعد تطبيق الخوارزمية لتحسين شبكة الهاتف الخاصة بشركة إيه تي آند تي، ^{[ 17 ]} أدركوا أن اختراعه قد يكون ذا أهمية عملية. وفي أبريل/نيسان 1985، سارعت شركة إيه تي آند تي إلى التقدم بطلب للحصول على براءة اختراع لخوارزميته.

أصبحت براءة الاختراع هذه وقودًا إضافيًا للجدل الدائر حول مسألة براءات اختراع البرمجيات . ^{[ 18 ]} وقد أثار هذا قلق العديد من علماء الرياضيات، مثل رونالد ريفست (أحد حاملي براءة اختراع خوارزمية RSA )، الذي أعرب عن رأيه بأن البحث يسير على أساس أن الخوارزميات يجب أن تكون مجانية. حتى قبل منح براءة الاختراع فعليًا، طُرحت فكرة وجود أعمال سابقة قابلة للتطبيق. ^{[ 19 ]} وادعى علماء الرياضيات المتخصصون في التحليل العددي ، بمن فيهم فيليب جيل وآخرون، أن خوارزمية كارماركار تُعادل طريقة حاجز نيوتن المُسقطة بدالة حاجز لوغاريتمية ، إذا تم اختيار المعاملات بشكل مناسب. ^{[ 20 ]} ويرى الباحث القانوني أندرو تشين أن حجة جيل كانت معيبة، إذ إن الطريقة التي وصفوها لا تُشكل "خوارزمية"، لأنها تتطلب اختيار معاملات لا تنبع من المنطق الداخلي للطريقة، بل تعتمد على توجيه خارجي، وتحديدًا من خوارزمية كارماركار. ^{[ 21 ]} علاوة على ذلك، تُعتبر إسهامات كارماركار غير بديهية في ضوء جميع الأعمال السابقة، بما في ذلك أعمال فياكو-مكورميك وجيل وغيرهم ممن استشهد بهم سالتزمان. ^{[ 21 ] [ 22 ] [ 23 ]} مُنحت براءة الاختراع تقديرًا للأصالة الجوهرية لعمل كارماركار، كبراءة اختراع أمريكية رقم 4,744,028 : "طرق وأجهزة لتخصيص الموارد بكفاءة" في مايو 1988.

صممت شركة AT&T نظام حاسوب متعدد المعالجات يعمل بتقنية المتجهات خصيصًا لتشغيل خوارزمية كارماركار، وأطلقت على هذا المزيج من الأجهزة والبرامج اسم KORBX، ^{[ 24 ]} وسوّقت هذا النظام بسعر 8.9 مليون دولار أمريكي. ^{[ 25 ] [ 26 ]} وكان البنتاغون أول عميل لها . ^{[ 27 ] [ 28 ]}

وقد جادل معارضو براءات اختراع البرمجيات بأن هذه البراءات قد أفسدت دورات التفاعل الإيجابية التي كانت تميز العلاقة بين الباحثين في البرمجة الخطية والصناعة، وعلى وجه التحديد عزلت كارماركار نفسه عن شبكة الباحثين الرياضيين في مجاله. ^{[ 29 ]}

انتهت صلاحية براءة الاختراع نفسها في أبريل 2006، والخوارزمية متاحة حاليًا للجمهور .

أصدرت المحكمة العليا الأمريكية حكمًا في قضية غوتشالك ضد بنسون [30] يقضي بعدم جواز تسجيل براءات اختراع للرياضيات . في تلك القضية ^{، تناولت المحكمة أولًا إمكانية تسجيل براءات اختراع لخوارزميات الحاسوب ،} وخلصت إلى عدم جواز ذلك لأن نظام براءات الاختراع لا يحمي الأفكار والمفاهيم المجردة المشابهة. وفي قضية دايموند ضد ديهر [ ^{31 ]، صرّحت} المحكمة العليا قائلةً: "لا تتمتع الصيغة الرياضية بحد ذاتها بحماية قوانين براءات الاختراع لدينا، ولا يمكن التحايل على هذا المبدأ بمحاولة حصر استخدام الصيغة في بيئة تكنولوجية محددة." ^{[ 32 ]} وفي قضية مايو للخدمات التعاونية ضد بروميثيوس لابز ^{[ 33 ]} ، أوضحت المحكمة العليا كذلك أن "مجرد تطبيق مبدأ رياضي على جهاز مادي، أي حاسوب، لا يُعد تطبيقًا قابلاً للتسجيل كبراءة اختراع لهذا المبدأ." ^{[ 34 ]}

استخدم الجيش الأمريكي خوارزمية كارماركار للتخطيط اللوجستي خلال حرب الخليج . ^{[ 1 ]}

• أدلر، إيلان ؛ كارماركار، ناريندرا؛ ريسيندي، ماوريسيو جي سي ؛ فيغا، جيرالدو (1989). "تطبيق خوارزمية كارماركار للبرمجة الخطية". البرمجة الرياضية . 44 ( 1-3 ): 297-335 . doi : 10.1007/bf01587095 . S2CID 12851754 . 
• ناريندرا كارماركار (1984). " خوارزمية جديدة متعددة الحدود للبرمجة الخطية "، كومبيناتوريكا ، المجلد 4 ، العدد 4، ص  373-395 .