Cutting-plane method
ریاضیاتی اصلاح میں، کٹنگ پلین طریقہ اصلاح کے مختلف طریقوں میں سے کوئی بھی ہے جو لکیری عدم مساوات کے ذریعے ایک قابل عمل سیٹ یا معروضی فنکشن کو بار بار بہتر بناتا ہے، جسے کٹس کہا جاتا ہے۔ اس طرح کے طریقہ کار عام طور پر مکسڈ انٹیجر لینیر پروگرامنگ (ایم آئی ایل پی) کے مسائل کے انٹیجر حل تلاش کرنے کے ساتھ ساتھ عام، ضروری نہیں کہ تفریق پذیر کنویکس اصلاح کے مسائل کو حل کرنے کے لیے استعمال کیے جاتے ہیں۔ ایم آئی ایل پی کو حل کرنے کے لیے طیاروں کو کاٹنے کا استعمال رالف ای گوموری نے متعارف کرایا تھا۔ غیر عدد لکیری پروگرام کو حل کرکے ایم آئی ایل پی کے کام کے لیے طیارہ کے طریقوں کو کاٹنا، دیئے گئے عدد پروگرام کی لکیری نرمی۔ لکیری پروگرامنگ کا نظریہ یہ بتاتا ہے کہ ہلکے مفروضوں کے تحت (اگر لکیری پروگرام کا ایک بہترین حل ہے، اور اگر قابل عمل خطے میں کوئی لکیر نہیں ہے)، کوئی بھی ہمیشہ ایک انتہائی نقطہ یا ایک کونے کا نقطہ تلاش کر سکتا ہے جو زیادہ سے زیادہ ہے۔ حاصل کردہ زیادہ سے زیادہ کو انٹیجر حل ہونے کے لیے ٹیسٹ کیا جاتا ہے۔ اگر ایسا نہیں ہے تو، اس بات کی ضمانت ہے کہ ایک لکیری عدم مساوات موجود ہے جو حقیقی قابل عمل سیٹ کے کنویکس ہل سے زیادہ سے زیادہ کو الگ کرتی ہے۔ اس طرح کی عدم مساوات کو تلاش کرنا علیحدگی کا مسئلہ ہے، اور اس طرح کی عدم مساوات ایک کٹ ہے۔ آرام دہ لکیری پروگرام میں ایک کٹ شامل کیا جا سکتا ہے۔ پھر، موجودہ غیر عدد حل اب نرمی کے لیے ممکن نہیں ہے۔ یہ عمل اس وقت تک دہرایا جاتا ہے جب تک کہ ایک بہترین عدد حل نہ مل جائے۔ عام کنویکس مسلسل اصلاح اور متغیرات کے لیے کٹنگ پلین کے طریقوں کو مختلف ناموں سے جانا جاتا ہے: کیلی کا طریقہ، کیلی-چینی-گولڈسٹین طریقہ، اور بنڈل کے طریقے۔ وہ عام طور پر غیر تفریق پذیر کنویکس کم سے کم کرنے کے لیے استعمال ہوتے ہیں، جہاں ایک کنویکس آبجیکٹ فنکشن اور اس کے ذیلی میلان کا مؤثر طریقے سے جائزہ لیا جا سکتا ہے لیکن تفریق پذیر اصلاح کے لیے معمول کے میلان کے طریقے استعمال نہیں کیے جا سکتے۔ یہ صورتحال لگرینجین دوہری افعال کی کنکیو میکسمائزیشن کے لیے سب سے زیادہ عام ہے۔ ایک اور عام صورتحال ڈینٹزگ-وولف کے سڑنے کا ایک منظم اصلاح کے مسئلے پر اطلاق ہے جس میں متغیرات کی ایک متغیر تعداد کے ساتھ فارمولیشنز حاصل کی جاتی ہیں۔ تاخیر سے کالم کی پیداوار کے ذریعے مانگ پر ان متغیرات کو پیدا کرنا متعلقہ دوہری مسئلے پر کٹنگ پلین انجام دینے کے مترادف ہے۔ ہسٹری کٹنگ طیاروں کو رالف گوموری نے 1950 کی دہائی میں انٹیجر پروگرامنگ اور مکسڈ انٹیجر پروگرامنگ کے مسائل کو حل کرنے کے طریقہ کار کے طور پر تجویز کیا تھا۔ تاہم، خود گوموری سمیت زیادہ تر ماہرین نے عددی عدم استحکام کی وجہ سے انہیں ناقابل عمل اور غیر موثر قرار دیا کیونکہ حل کی طرف پیش رفت کے لیے کٹوتیوں کے کئی دور درکار تھے۔ حالات اس وقت بدل گئے جب 1990 کی دہائی کے وسط میں جیرارڈ کارنیوجولز اور ساتھی کارکنوں نے انہیں برانچ اینڈ باؤنڈ (جسے برانچ اینڈ کٹ کہا جاتا ہے) اور عددی عدم استحکام پر قابو پانے کے طریقوں کے ساتھ مل کر بہت موثر ثابت کیا۔ آج کل، تمام تجارتی ایم آئی ایل پی حل کرنے والے کسی نہ کسی طرح گوموری کٹس کا استعمال کرتے ہیں۔ گوموری کٹس ایک سمپلیکس ٹیبلو سے بہت مؤثر طریقے سے تیار کیے جاتے ہیں، جبکہ بہت سی دوسری اقسام کے کٹس یا تو مہنگے ہوتے ہیں یا یہاں تک کہ الگ کرنے کے لیے این پی سخت ہوتے ہیں۔ ایم آئی ایل پی کے لیے دیگر عام کٹوتیوں میں، خاص طور پر لفٹ اینڈ پروجیکٹ گوموری کٹوتیوں پر حاوی ہے۔ گوموری کا کٹ ایک انٹیجر پروگرامنگ کے مسئلے کو (کینونکل شکل میں) اس طرح وضع کیا جائے: جہاں A ایک میٹرکس ہے اور b، c ایک ویکٹر ہے۔ ویکٹر x نامعلوم ہے اور لکیری رکاوٹوں کا احترام کرتے ہوئے مقصد کو زیادہ سے زیادہ کرنے کے لیے پایا جانا چاہیے۔ عمومی خیال یہ طریقہ پہلے اس ضرورت کو چھوڑ کر آگے بڑھتا ہے کہ xi انٹیجر ہوں اور ایک بنیادی قابل عمل حل حاصل کرنے کے لیے متعلقہ آرام دہ لکیری پروگرامنگ کے مسئلے کو حل کریں۔ ہندسی طور پر، یہ حل کنویکس پولیٹوپ کا ایک ورٹیکس ہوگا جو تمام قابل عمل نکات پر مشتمل ہوگا۔ اگر یہ ورٹیکس ایک انٹیجر پوائنٹ نہیں ہے تو طریقہ کار ایک طرف ورٹیکس اور دوسری طرف تمام قابل عمل انٹیجر پوائنٹس کے ساتھ ایک ہائپرپلین تلاش کرتا ہے۔ اس کے بعد پائے جانے والے سرے کو خارج کرنے کے لیے اسے ایک اضافی لکیری رکاوٹ کے طور پر شامل کیا جاتا ہے، جس سے ایک ترمیم شدہ لکیری پروگرام بنتا ہے۔ اس کے بعد نیا پروگرام حل کیا جاتا ہے اور یہ عمل اس وقت تک دہرایا جاتا ہے جب تک کہ انٹیجر حل نہ مل جائے۔ مرحلہ 1: آرام دہ لکیری پروگرام کو حل کرنا ایک لکیری پروگرام کو حل کرنے کے لیے سمپلیکس طریقہ کا استعمال کرتے ہوئے اس شکل کی مساوات کا ایک مجموعہ تیار ہوتا ہے جہاں xi ایک بنیادی متغیر ہے اور xj "s غیر بنیادی متغیر ہیں (یعنی۔ بنیادی حل جو آرام دہ لکیری پروگرام کا بہترین حل ہے اور) ہے۔ ہم سمپلیکس طریقہ کار کے ذریعہ تیار کردہ آخری جھانکی کو ظاہر کرنے کے لیے کوفیشنٹس اور بار کے ساتھ لکھتے ہیں۔ یہ کوفشنٹس میٹرکس A اور ویکٹر b کے کوفشنٹس سے مختلف ہیں۔ مرحلہ 2: ایک لکیری رکاوٹ تلاش کریں اب ایک غیر بنیادی متغیر پر غور کریں جو عدد نہیں ہے۔ مندرجہ بالا مساوات کو دوبارہ لکھیں تاکہ انٹیجر کے حصے بائیں طرف شامل کیے جائیں اور فریکشنل حصے دائیں طرف ہوں: قابل عمل خطے میں کسی بھی انٹیجر پوائنٹ کے لیے، بائیں طرف ایک انٹیجر ہے کیونکہ تمام اصطلاحات،،، انٹیجر ہیں۔ اس مساوات کا دایاں رخ سختی سے 1 سے کم ہے: درحقیقت، سختی سے 1 سے کم ہے جبکہ منفی ہے۔ لہذا مشترکہ قدر 0 سے کم یا اس کے برابر ہونی چاہیے۔ لہذا عدم مساوات کو قابل عمل خطے میں کسی بھی انٹیجر پوائنٹ کے لیے برقرار رکھنا چاہیے۔ مزید برآں، غیر بنیادی متغیرات کسی بھی بنیادی حل میں 0s کے برابر ہوتے ہیں اور اگر xi بنیادی حل x کے لیے عدد نہیں ہے، تو نتیجہ اس لیے اوپر کی عدم مساوات بنیادی قابل عمل حل کو خارج کرتی ہے اور اس طرح مطلوبہ خصوصیات کے ساتھ ایک کٹ ہے۔ مزید واضح طور پر، قابل عمل خطے میں کسی بھی عدد نقطہ کے لیے منفی ہے، اور آرام دہ لکیری پروگرام کے بنیادی قابل عمل (غیر عدد) حل کے لیے سختی سے مثبت ہے۔ اس عدم مساوات کے لیے ایک نیا سست متغیر xk متعارف کراتے ہوئے، لکیری پروگرام میں ایک نئی رکاوٹ شامل کی گئی ہے، یعنی کنویکس آپٹیمائزیشن کٹنگ پلین کے طریقے غیر لکیری پروگرامنگ میں بھی لاگو ہوتے ہیں۔ بنیادی اصول بند نصف خالی جگہوں کے ایک محدود سیٹ کے ذریعے غیر لکیری (کنویکس) پروگرام کے قابل عمل علاقے کا تخمینہ لگانا اور تقریبا لکیری پروگراموں کی ترتیب کو حل کرنا ہے۔ بینڈرز کی سڑنے والی شاخ اور کٹ برانچ اور باؤنڈ کالم نسل ڈینٹزگ-وولف سڑنے کے حوالہ جات ایوریل، مورڈیکائی (2003) بھی دیکھیں۔ غیر لکیری پروگرامنگ: تجزیہ اور طریقے۔ ڈوور پبلکیشنز۔ کارنیوجولس، جیرارڈ (2008)۔ مخلوط عدد لکیری پروگراموں کے لیے درست عدم مساوات۔ ریاضیاتی پروگرامنگ سر۔ بی، (2008) 112:3-44۔ کارنیوجولس، جیرارڈ (2007)۔ 1990 کی دہائی میں گوموری کٹس کا احیاء۔ اینلز آف آپریشنز ریسرچ، جلد۔ 149 (2007)، پی پی۔ 63-66۔ بیرونی روابط "انٹیجر پروگرامنگ" سیکشن 9.8 اپلائیڈ میتھمیٹیکل پروگرامنگ باب 9 انٹیجر پروگرامنگ (مکمل متن)۔ بریڈلی، ہیکس، اور میگنتی (ایڈیسن-ویسلی، 1977) آپٹیمائزیشن الگورتھم اور طریقے