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

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

بجعل ${\displaystyle n$ تدل على عدد المتغيرات و ${\displaystyle L$ على عدد وحدات بت في مدخلات الخوارزمية، خوارزمية كارماركر بحاجة إلى ${\displaystyle O(n^{3.5 L)$ عملية على خانات ${\displaystyle O(L)$ , في اللقاء بحاجة إلى ${\displaystyle O(n^{6 L)$ عمليات بخوارزمية الاهليجي.

بالتالي زمن تشغيل خوارزمية كارماركر هو:

{\displaystyle O(n^{3.5 L^{2 \cdot \log L\cdot \log \log L)

باستخدام الضرب القائم على FFT (انظر رمز O الكبير ).

تندرج خوارزمية كارماركر ضمن فئة أساليب النقاط الداخلية : لا يتبع التخمين الحالي للحل حدود المجموعة الممكنة كما هوالحال في طريقة simplex ، لكنه يتحرك بداخل المنطقة الممكنة، مما يحسن تقريب الحل الأمثل بكسر واضح مع جميع التكرار، والوصول إلى الحل الأمثل مع البيانات المنطقية.

الخوارزمية

بالنظر في معضلة البرمجة الخطية في شكل المصفوفة:

Maximise $c T x$
. $Ax \leq b$	Subject to

تحدد خوارزمية كارماركر الاتجاه التالي الممكن إلى المثالية وتوازن بمعامل $0 < γ \leq 1$ .

وسع كامارك الطريقة ، لتحل مسائل بقيود اعداد سليمة والمسائل غير المحدبة.

Input: A, b, c, ${\displaystyle x^{0$ , stopping criterion, $γ$ .

  ${\displaystyle k\leftarrow 0$

do while stopping criterion not satisfied

   ${\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$

  if  ${\displaystyle h_{v \geq 0$  then

    return unbounded

  end if

   ${\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$

 end do

مثال

مثال الحل

بالنظر في البرنامج الخطي

{\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 ، بدأ كارماركر العمل في إيه تي آند تي وقدم منطقته إلى Symposium on Theory of Computing ACM لعام 1984 حول نظرية الحوسبة (STOC ، التي عقدت في 30 أبريل - 2 مايو1984) مشروحًا حتى انتمائه لمختبرات بيل لإيه تي آند تي . بعد تطبيق الخوارزمية على تحسين شبكة هاتف إيه تي آند تي، أدركوا حتى اختراعه يمكن حتىقد يكون ذا أهمية عملية. في أبريل 1985 ، تقدمت إيه تي آند تي بطلب للحصول على براءة اختراع على خوارزمية كارماركر.

المراجع

Adler, Ilan; Karmarkar, Narendra; Resende, Mauricio G.C.; Veiga, Geraldo (1989). "An Implementation of Karmarkar's Algorithm for Linear Programming". Mathematical Programming. 44 (1–3): 297–335. doi:10.1007/bf01587095.
ناريندرا كارماركار (1984). " خوارزمية زمنية جديدة متعددة الحدود للبرمجة الخطية " ، Combinatorica ، المجلد 4 ، العدد. أربعة ، ص. 373 – 395.

^ Strang, Gilbert (1 June 1987). "Karmarkar's algorithm and its place in applied mathematics". The Mathematical Intelligencer. 9 (2): 4–10. doi:10.1007/BF03025891. ISSN 0343-6993. MR = 0883185 0883185. CS1 maint: ref=harv (link)
^ A new polynomial-time algorithm for linear programming نسخة محفوظة 14 فبراير 2019 على مسقط واي باك مشين.
^ Karmarkar, N. (1984). "A new polynomial-time algorithm for linear programming". Combinatorica. 4 (4): 373–395. doi:10.1007/BF02579150.
^ Karmarkar, Narendra K. (1989). "Power Series Variants of Karmarkar-Type Algorithms". AT&T Technical Journal. 68 (3): 20–36. doi:10.1002/j.1538-7305.1989.tb00316.x.
^ Karmarkar N. K., Lagarias, J.C., Slutsman, L., and Wang, P., Power Series Variants of KarmarkarType Algorithm, AT & T technical Journal 68, No. 3, May/June (1989).
^ Karmarkar, N.K., Interior Point Methods in Optimization, Proceedings of the Second International Conference on Industrial and Applied Mathematics, SIAM, pp. 160181 (1991)
^ Karmarkar, N. K. and Kamath, A. P., A continuous Approach to Deriving Upper Bounds in Quadratic Maximization Problems with Integer Constraints, Recent Advances in Global Optimization, pp. 125140, Princeton University Press (1992).
^ 26. Karmarkar, N. K., Thakur, S. A., An Interior Point Approach to a Tensor Optimisation Problem with Application to Upper Bounds in Integer Quadratic Optimization Problems, Proceedings of Second Conference on Integer Programming and Combinatorial Optimisation, (May 1992).
^ 27. Kamath, A., Karmarkar, N. K., A Continuous Method for Computing Bounds in Integer Quadratic Optimisation Problems, Journal of Global Optimization (1992).
^ Karmarkar, N. K., Beyond Convexity: New Perspectives in Computational Optimization. Springer Lecture Notes in Computer Science LNCS 6457, Dec 2010
^ Sinha L.P., Freedman, B. A., Karmarkar, N. K., Putcha, A., and Ramakrishnan K.G., Overseas Network Planning, Proceedings of the Third International Network Planning Symposium, NETWORKS' 86, Tarpon Springs, Florida (June 1986).