Karmarkar–Karp bin packing algorithms
کرمارکر-کارپ (کے کے) بن پیکنگ الگورتھم بن پیکنگ کے مسئلے کے لیے کئی متعلقہ تخمینہ الگورتھم ہیں۔ ڈبے کی پیکنگ کا مسئلہ مختلف سائز کی اشیاء کو ایک جیسی صلاحیت کے ڈبوں میں پیک کرنے کا مسئلہ ہے، جیسے کہ ڈبوں کی کل تعداد ہر ممکن حد تک کم ہو۔ بہترین حل تلاش کرنا کمپیوٹیشنل طور پر مشکل ہے۔ کرمارکر اور کارپ نے ایک الگورتھم وضع کیا جو کثیر الجہتی وقت میں چلتا ہے اور زیادہ سے زیادہ ڈبوں کے ساتھ حل تلاش کرتا ہے، جہاں او پی ٹی بہترین حل میں ڈبوں کی تعداد ہے۔ انہوں نے قدرے مختلف تخمینہ ضمانتوں اور رن ٹائم حدود کے ساتھ کئی دیگر الگورتھم بھی وضع کیے۔ کے کے الگورتھم کو بن پیکنگ کے مطالعہ میں ایک پیشرفت سمجھا جاتا تھا: پہلے سے معروف الگورتھم میں ضرب کا تخمینہ پایا گیا، جہاں کچھ مستقلات کے لیے ڈبوں کی تعداد زیادہ سے زیادہ تھی، یا زیادہ سے زیادہ۔ کے کے الگورتھم سب سے پہلے تھے جنہوں نے اضافی تخمینہ حاصل کیا۔ ان پٹ بن پیکنگ کے مسئلے کے لیے ان پٹ مختلف سائز کی اشیاء کا ایک مجموعہ ہے، a1،. an۔ مندرجہ ذیل اشارے کا استعمال کیا جاتا ہے: n-اشیاء کی تعداد۔ m-مختلف آئٹم سائز کی تعداد۔ 1 میں ہر ایک i کے لیے، m: si i-th سائز ہے ؛ ni سائز si کی اشیاء کی تعداد ہے۔ B-ڈبے کا سائز۔ ایک مثال I کو دیکھتے ہوئے، ہم اشارہ کرتے ہیں: او پی ٹی (I) = مثال I کا بہترین حل۔ ایف او پی ٹی (I) = (a1 +. + an)/B = نظریاتی طور پر زیادہ سے زیادہ ڈبوں کی تعداد، جب تمام ڈبے مکمل طور پر اشیاء یا آئٹم کے حصوں سے بھرے ہوتے ہیں۔ ظاہر ہے، ایف او پی ٹی (I) ≤ او پی ٹی (I)۔ اعلی سطحی اسکیم کے کے الگورتھم بنیادی طور پر ترتیب لکیری پروگرام کو حل کرتے ہیں: یہاں، اے میٹرکس ہے جس میں ایم قطاریں ہیں۔ اے کا ہر کالم ایک قابل عمل ترتیب کی نمائندگی کرتا ہے-آئٹم سائز کا ایک ملٹی سیٹ، اس طرح کہ ان تمام سائزوں کا مجموعہ زیادہ سے زیادہ بی ہو۔ ترتیبات کا مجموعہ C ہے۔ x سائز C کا ایک ویکٹر ہے۔ x کا ہر عنصر xc ترتیب c کے استعمال ہونے کی تعداد کی نمائندگی کرتا ہے۔ مثال: فرض کریں کہ آئٹم کے سائز 3,3,3، 3,3,4,4,4، 4,4، اور B = 12 ہیں۔ پھر سی = 10 ممکنہ ترتیبات ہیں: 3333 ؛ 333 ؛ 33، 334 ؛ 3، 34، 344 ؛ 4، 44، 444۔ میٹرکس اے کی دو قطاریں ہیں: [4,3,2، 2,1,1، 1,0,0، 0] s = 3 کے لیے اور [0,0,0، 1,0,1، 2,1,2، 3] s = 4 کے لیے۔ ویکٹر n [5,5] ہے کیونکہ ہر سائز کے 5 آئٹم ہوتے ہیں۔ ایک ممکنہ بہترین حل x = [1، 0,0,0، 0,0، 1,0,0، 1] ہے، جو ترتیبات 3333، 344، 444 کے ساتھ تین ڈبوں کے استعمال سے مطابقت رکھتا ہے۔ اس مسئلے کو حل کرنے میں دو اہم مشکلات ہیں۔ سب سے پہلے، یہ ایک انٹیجر لکیری پروگرام ہے، جسے حل کرنا کمپیوٹیشنل طور پر مشکل ہے۔ دوسرا، متغیرات کی تعداد C ہے-ترتیبات کی تعداد، جو بہت زیادہ ہو سکتی ہے۔ کے کے الگورتھم کئی تکنیکوں کا استعمال کرتے ہوئے ان مشکلات سے نمٹتے ہیں، جن میں سے کچھ کو پہلے ہی ڈی لا ویگا اور لیوکر نے متعارف کرایا تھا۔ یہاں الگورتھم کی ایک اعلی سطحی تفصیل ہے (جہاں اصل مثال ہے): 1-a۔ آئیے چھوٹی اشیاء کو ہٹا کر بنائی گئی ایک مثال بنیں۔ 2-اے۔ آئیے آئٹمز کو گروپ کرنے اور ہر گروپ میں آئٹمز کے سائز کو گروپ کی سب سے اونچی آئٹم پر گول کرنے کی ایک مثال بنیں۔ 3-اے۔ انضمام کی رکاوٹوں کے بغیر ترتیب لکیری پروگرام کی تعمیر کریں۔ 4. آرام دہ لکیری پروگرام کے لیے a (فریکشنل) حل x کا حساب لگائیں۔ 3-بی۔ کے لیے ایک لازمی حل کے لیے x کو گول کریں۔ 2-بی۔ حل حاصل کرنے کے لیے آئٹمز کو "ان گروپ" کریں۔ 1-بی۔ حل حاصل کرنے کے لیے چھوٹی چھوٹی اشیاء شامل کریں۔ ذیل میں، ہم ان میں سے ہر ایک مرحلے کو باری باری بیان کرتے ہیں۔ مرحلہ 1۔ چھوٹی اشیاء کو ہٹانا اور شامل کرنا چھوٹی اشیاء کو ہٹانے کا محرک یہ ہے کہ جب تمام اشیاء بڑی ہوں تو ہر ڈبے میں موجود اشیاء کی تعداد کم ہونی چاہیے، اس لیے ممکنہ ترتیبات کی تعداد (نسبتا) کم ہے۔ ہم کچھ مستقل منتخب کرتے ہیں، اور اصل مثال سے اس سے چھوٹی تمام اشیاء کو ہٹا دیتے ہیں۔ آئیے نتیجہ خیز مثال بنیں۔ نوٹ کریں کہ ہر ڈبے میں زیادہ تر اشیاء ہو سکتی ہیں۔ ہم پیک کرتے ہیں اور کچھ ڈبوں کے ساتھ پیکنگ کرتے ہیں۔ اب، ہم چھوٹی اشیاء کو موجودہ ڈبوں میں من مانی ترتیب میں شامل کرتے ہیں، جب تک کہ گنجائش ہو۔ جب موجودہ ڈبوں میں مزید جگہ نہ ہو تو ہم ایک نیا ڈبہ کھولتے ہیں (جیسا کہ نیکسٹ فٹ ڈبے کی پیکنگ میں ہوتا ہے)۔ حتمی پیکنگ میں ڈبوں کی تعداد ہونے دیں۔ پھر: ثبوت۔ اگر کوئی نیا ڈبہ نہیں کھولا جائے تو ڈبوں کی تعداد باقی رہتی ہے۔ اگر ایک نیا ڈبہ کھولا جاتا ہے، تو شاید آخری کے علاوہ تمام ڈبوں میں کم از کم کل سائز ہوتا ہے، لہذا کل مثال کا سائز کم از کم ہے۔ لہذا، لہذا زیادہ سے زیادہ حل کے لیے کم از کم ڈبے کی ضرورت ہوتی ہے۔ تو۔ خاص طور پر، g = 1/n لینے سے، ہمیں ملتا ہے:، چونکہ۔ لہذا، یہ فرض کرنا عام ہے کہ تمام اشیاء 1/n سے بڑی ہیں۔ مرحلہ 2۔ آئٹمز کو گروپ کرنا اور ان گروپ کرنا آئٹمز کو گروپ کرنے کا محرک مختلف آئٹم سائز کی تعداد کو کم کرنا، ترتیب ایل پی میں رکاوٹوں کی تعداد کو کم کرنا ہے۔ گروپ بندی کا عمومی عمل یہ ہے: آئٹمز کو نزولی سائز کے لحاظ سے آرڈر کریں۔ اشیاء کو گروپوں میں تقسیم کریں۔ ہر گروپ کے لیے، گروپ کے تمام آئٹمز کے سائز کو گروپ کے سب سے بڑے سائز میں تبدیل کریں۔ گروہ بندی کے کئی مختلف طریقے ہیں۔ لکیری گروپنگ ایک انٹیجر پیرامیٹر ہونے دیں۔ سب سے بڑی اشیاء کو گروپ 1 میں رکھیں ؛ گروپ 2 میں اگلی سب سے بڑی اشیاء ؛ اور اسی طرح (آخری گروپ میں اشیاء سے کم ہو سکتی ہیں)۔ آئیے یہ اصل مثال ہے۔ آئیے پہلا گروپ (سب سے بڑی اشیاء کا گروپ)، اور پہلے گروپ کے بغیر گروپ شدہ مثال بنیں۔ پھر: تمام آئٹمز کا سائز ایک جیسا ہوتا ہے۔ مختلف سائز کی تعداد میں ہے۔ - چونکہ گروپ 1 میں گروپ 2 کا غلبہ ہے (گروپ 1 میں تمام کے آئٹمز گروپ 2 میں کے آئٹمز سے بڑے ہیں) ؛ اسی طرح، گروپ 2 میں گروپ 3 میں، وغیرہ کا غلبہ ہے۔ - چونکہ ہر آئٹم کو ایک ڈبے میں پیک کرنا ممکن ہے۔ اس لیے۔ درحقیقت، ڈبوں کے ساتھ حل دیے جانے پر، ہم زیادہ سے زیادہ ڈبوں کے ساتھ حل حاصل کر سکتے ہیں۔ جیومیٹرک گروپنگ ایک انٹیجر پیرامیٹر ہونے دیں۔ ہندسی گروہ بندی دو مراحل میں آگے بڑھتی ہے: مثال کو کئی مثالوں میں اس طرح تقسیم کریں کہ، ہر مثال میں، تمام سائز وقفے میں ہوں۔ نوٹ کریں کہ، اگر تمام آئٹمز کا سائز کم از کم ہے، تو مثالوں کی تعداد زیادہ سے زیادہ ہے۔ ہر مثال پر، پیرامیٹر کے ساتھ لکیری راؤنڈنگ انجام دیں۔ آئیے نتیجہ خیز مثالیں ہوں۔ لیٹ اینڈ۔ پھر، مختلف سائز کی تعداد کو مندرجہ ذیل طور پر پابند کیا جاتا ہے: تمام r کے لیے، اور۔ چونکہ تمام آئٹمز اس سے بڑی ہیں، اس لیے ہمارے پاس ہیں۔ تمام r کا خلاصہ کرنے سے پتہ چلتا ہے۔ ڈبوں کی تعداد مندرجہ ذیل ہے: تمام r کے لیے،-چونکہ اس میں اشیاء ہیں، اور وہ سب اس سے چھوٹے ہیں، لہذا انہیں زیادہ سے زیادہ ڈبوں میں پیک کیا جا سکتا ہے۔ اس لیے۔ اس لیے۔ متبادل ہندسی گروہ بندی آئیے ایک انٹیجر پیرامیٹر بنیں۔ آئٹمز کو نیچے کے سائز کے مطابق آرڈر کریں۔ انہیں گروہوں میں اس طرح تقسیم کریں کہ ہر گروپ کا کل سائز کم از کم ہو۔ چونکہ ہر آئٹم کا سائز B سے کم ہے، اس لیے ہر گروپ میں آئٹمز کی تعداد کم از کم ہے۔ ہر گروپ میں آئٹمز کی تعداد کمزور ہوتی جا رہی ہے۔ اگر تمام آئٹمز اس سے بڑی ہیں، تو ہر گروپ میں آئٹمز کی تعداد زیادہ سے زیادہ ہے۔ ہر گروپ میں، صرف بڑی اشیاء کو گول کیا جاتا ہے۔ یہ اس طرح کیا جا سکتا ہے کہ: ۔ مرحلہ 3. ایل پی کی تعمیر اور حل کو گول کرنا ہم انضمام کی رکاوٹوں کے بغیر ترتیب لکیری پروگرام پر غور کرتے ہیں: یہاں، ہمیں ہر ترتیب کا ایک فریکشنل نمبر استعمال کرنے کی اجازت ہے۔ مثال: فرض کریں کہ سائز 3 کی 31 اشیاء اور سائز 4 کی 7 اشیاء ہیں، اور ڈبے کا سائز 10 ہے۔ ترتیبات یہ ہیں: 4، 44، 34، 334، 3، 33، 333۔ رکاوٹیں ہیں [0,0,1,2,1,2,3] * x = 31 اور [1,2,1,1,0,0,0] * x = 7۔ فریکشنل ایل پی کا ایک بہترین حل ہے [0,0,0، 7,0,0، 17/3] یعنی: ترتیب 334 کے 7 ڈبے اور ترتیب 333 کے 17/3 ڈبے ہیں۔ نوٹ کریں کہ صرف دو مختلف ترتیبات کی ضرورت ہے۔ ایل او پی ٹی کے ذریعے لکیری پروگرام کے بہترین حل کی نشاندہی کریں۔ مندرجہ ذیل تعلقات واضح ہیں: ایف او پی ٹی (I) ≤ ایل او پی ٹی (I)، کیونکہ ایف او پی ٹی (I) ڈبوں کی (ممکنہ طور پر جزوی) تعداد ہے جب تمام ڈبے مکمل طور پر اشیاء یا اشیاء کے حصوں سے بھرے ہوتے ہیں۔ واضح طور پر کوئی بھی حل اس سے زیادہ موثر نہیں ہو سکتا۔ ایل او پی ٹی (I) ≤ او پی ٹی (I)، کیونکہ ایل او پی ٹی (I) کم رکاوٹوں کے ساتھ کم سے کم مسئلے کا حل ہے۔ او پی ٹی (I) <2 * ایف او پی ٹی (I)، چونکہ کسی بھی پیکنگ میں کم از کم 2 * ایف او پی ٹی (I) ڈبوں کے ساتھ، دو کم سے کم بھرے ڈبوں کا مجموعہ زیادہ سے زیادہ بی ہوتا ہے، لہذا انہیں ایک ہی ڈبے میں ملایا جا سکتا ہے۔ فریکشنل ایل پی کے حل کو ایک لازمی حل کے لیے درج ذیل طور پر گول کیا جا سکتا ہے۔ فرض کریں کہ ہمارے پاس فریکشنل ایل پی کا حل x ہے۔ ہم مندرجہ ذیل طور پر انٹیگرل آئی ایل پی کے حل میں ایکس کو گول کرتے ہیں۔ فرض کریں کہ x فریکشنل LP کا ایک بہترین بنیادی قابل عمل حل ہے۔ فرض کریں کہ یہ ڈبے کے طور پر ہے (نوٹ کریں کہ یہ فریکشنل نمبر ہو سکتا ہے)۔ چونکہ فریکشنل ایل پی میں m کی رکاوٹیں ہوتی ہیں (ہر مختلف سائز کے لیے ایک)، x میں زیادہ سے زیادہ m غیر صفر متغیر ہوتے ہیں، یعنی زیادہ سے زیادہ m مختلف ترتیبات استعمال کی جاتی ہیں۔ ہم x سے ایک لازمی پیکنگ بناتے ہیں جس میں ایک بنیادی حصہ اور ایک بقایا حصہ ہوتا ہے۔ اصل حصے میں ہر ترتیب c کے فرش (xc) ڈبے ہوتے ہیں جن کے لیے xc> 0 ہوتا ہے۔ بقیہ حصے کے لیے (R سے ظاہر)، ہم دو امیدوار پیکنگ بناتے ہیں: ہر ترتیب c کا ایک واحد بن جس کے لیے xc> 0 ؛ تمام m ڈبوں کی ضرورت ہوتی ہے۔ ایک لالچی پیکنگ، جس میں 2 * ایف او پی ٹی (آر) سے کم ڈبے ہوں (کیونکہ اگر کم از کم 2 * ایف او پی ٹی (آر) ڈبے ہیں، تو دو سب سے چھوٹے کو ملایا جا سکتا ہے)۔ ان پیکنگز میں سے سب سے چھوٹے کے لیے کم از کم (m، 2 * FOPT (R)) ≤ اوسط (m، 2 * FOPT (R)) = FOPT (R) + m/2 کی ضرورت ہوتی ہے۔ اس میں اضافہ کرتے ہوئے اصل حصے کے گول ڈبے زیادہ تر ڈبوں میں پیداوار دیتے ہیں۔ اس تبادلوں کے الگورتھم کا نفاذ کا وقت O (n لاگ n) ہے۔ اس کا مطلب یہ بھی ہے۔ مرحلہ 4. فریکشنل ایل پی کو حل کرنا فریکشنل ایل پی کو حل کرنے میں اہم چیلنج یہ ہے کہ اس میں متغیرات کی ایک بڑی تعداد ہو سکتی ہے-ہر ممکنہ ترتیب کے لیے ایک متغیر۔ دوہری ایل پی فریکشنل ایل پی کا دوہری لکیری پروگرام یہ ہے:۔ اس میں m متغیرات ہیں، اور C رکاوٹیں-ہر ترتیب کے لیے ایک رکاوٹ۔ اس کی درج ذیل معاشی تشریح ہے۔ ہر سائز s کے لیے، ہمیں غیر منفی قیمت کا تعین کرنا چاہیے۔ ہمارا منافع تمام اشیاء کی کل قیمت ہے۔ ہم ان رکاوٹوں کے تابع منافع کو زیادہ سے زیادہ کرنا چاہتے ہیں کہ ہر ترتیب میں اشیاء کی کل قیمت زیادہ سے زیادہ 1 ہو۔ اس ایل پی میں اب صرف m متغیر ہیں، لیکن رکاوٹوں کی ایک بہت بڑی تعداد ہے۔ یہاں تک کہ تمام رکاوٹوں کو درج کرنا بھی ناقابل عمل ہے۔ خوش قسمتی سے، ایلیپسائڈ طریقہ کار کی ایک قسم کا استعمال کرتے ہوئے، تمام رکاوٹوں کو درج کیے بغیر کسی بھی دی گئی درستگی تک مسئلے کو حل کرنا ممکن ہے۔ یہ متغیر ان پٹ کے طور پر ملتا ہے، ایک علیحدگی اوریکل: ایک فنکشن جو، ایک ویکٹر y ≤ 0 دیا گیا ہے، مندرجہ ذیل دو اختیارات میں سے ایک کو واپس کرتا ہے: اس بات پر زور دیں کہ y قابل عمل ہے، یعنی ؛ یا-اس بات پر زور دیں کہ y ناقابل عمل ہے، اور ایک مخصوص رکاوٹ کو واپس کرتا ہے جس کی خلاف ورزی کی گئی ہے، یعنی، ایک ویکٹر a ایسا ہے۔ ایلیپسائڈ طریقہ ایک بڑے ایلیپسائڈ سے شروع ہوتا ہے، جس میں پورا قابل عمل ڈومین ہوتا ہے۔ ہر مرحلے t پر، یہ موجودہ ایلیپسائڈ کا مرکز لیتا ہے، اور اسے علیحدگی اوریکل کو بھیجتا ہے: اگر اوریکل کہتا ہے کہ یہ ممکن ہے، تو ہم ایک "آپٹیمیلیٹی کٹ" کرتے ہیں: ہم ایلیپسائڈ سے تمام پوائنٹس y کاٹتے ہیں جس کے لیے۔ یہ نکات یقینی طور پر بہترین نہیں ہیں۔ اگر اوریکل کہتا ہے کہ یہ ناقابل عمل ہے اور رکاوٹ a کی خلاف ورزی کرتا ہے، تو ہم "فزیبلٹی کٹ" کرتے ہیں: ہم ایلیپسائڈ سے تمام پوائنٹس y کاٹتے ہیں جس کے لیے۔ یہ نکات یقینی طور پر قابل عمل نہیں ہیں۔ کٹ بنانے کے بعد، ہم ایک نیا، چھوٹا ایلیپسائڈ بناتے ہیں۔ یہ دکھایا جا سکتا ہے کہ یہ عمل مطلوبہ درستگی میں وقت کے کثیر الجہتی میں ایک لگ بھگ حل میں بدل جاتا ہے۔ دوہری ایل پی کے لیے ایک علیحدگی اوریکل ہمیں کچھ m غیر منفی نمبر دیے گئے ہیں۔ ہمیں مندرجہ ذیل دو اختیارات کے درمیان فیصلہ کرنا ہوگا: ہر قابل عمل ترتیب کے لیے، اس ترتیب سے مطابقت رکھنے والے کا مجموعہ زیادہ سے زیادہ 1 ہے ؛ اس کا مطلب ہے کہ y قابل عمل ہے۔ ایک قابل عمل ترتیب موجود ہے جس کے لیے کا مجموعہ 1 سے بڑا ہے ؛ اس کا مطلب ہے کہ y ناقابل عمل ہے۔ اس صورت میں، ہمیں ترتیب بھی واپس کرنی ہوگی۔ اس مسئلے کو نیپسیک کے مسئلے کو حل کرکے حل کیا جا سکتا ہے، جہاں آئٹم کی اقدار ہیں، آئٹم کا وزن ہے، اور وزن کی گنجائش B (ڈبے کا سائز) ہے۔ اگر زیادہ سے زیادہ نیپسیک حل کی کل قیمت زیادہ سے زیادہ 1 ہے، تو ہم کہتے ہیں کہ y ممکن ہے۔ اگر زیادہ سے زیادہ نیپسیک حل کی کل قیمت 1 سے زیادہ ہے، تو ہم کہتے ہیں کہ y ناقابل عمل ہے، اور زیادہ سے زیادہ نیپسیک حل میں موجود اشیاء ایک ایسی ترتیب سے مطابقت رکھتی ہیں جو ایک رکاوٹ کی خلاف ورزی کرتی ہے (چونکہ ویکٹر کے لیے a جو اس ترتیب سے مطابقت رکھتا ہے)۔ نیپسیک کے مسئلے کو ڈائنامک پروگرامنگ کے ذریعے فرضی کثیر الجہتی وقت میں حل کیا جا سکتا ہے:، جہاں m ان پٹ کی تعداد ہے اور V مختلف ممکنہ اقدار کی تعداد ہے۔ کثیر الجہتی وقت الگورتھم حاصل کرنے کے لیے، ہم ان پٹ راؤنڈنگ کا استعمال کرتے ہوئے تقریبا نیپسیک کے مسئلے کو حل کر سکتے ہیں۔ فرض کریں کہ ہم رواداری کے ساتھ حل چاہتے ہیں۔ ہم ہر ایک کو/n کے قریب ترین ضرب تک گول کر سکتے ہیں۔ پھر، 0 اور 1 کے درمیان ممکنہ اقدار کی تعداد n/ہے، اور رن ٹائم ہے۔ حل کم از کم بہترین حل مائنس/این ہے۔ ایک لگ بھگ علیحدگی اوریکل کے ساتھ ایلیپسائڈ طریقہ ایلیپسائڈ طریقہ کو تقریبا علیحدگی اوریکل استعمال کرنے کے لیے ڈھال لیا جانا چاہیے۔ موجودہ ایلیپسائڈ مرکز کو دیکھتے ہوئے: اگر تخمینہ اوریکل 1 سے بڑی قیمت کے ساتھ حل واپس کرتا ہے، تو یقینی طور پر ناقابل عمل ہے، اور حل اس ترتیب سے مطابقت رکھتا ہے جو ایک رکاوٹ a کی خلاف ورزی کرتا ہے۔ ہم "فزیبلٹی کٹ" کرتے ہیں، ایلیپسائڈ کو تمام پوائنٹس y کاٹتے ہیں جس کے لیے۔ اگر لگ بھگ اوریکل زیادہ سے زیادہ 1 کی قیمت کے ساتھ حل واپس کرتا ہے، تو ممکن ہو سکتا ہے یا نہیں بھی، لیکن گول کرنا (اس سے ظاہر کرنا) ممکن ہے۔ راؤنڈنگ کی تعریف کے مطابق، ہم یہ جانتے ہیں۔ ہم اب بھی ایک "آپٹیمیلیٹی کٹ" کرتے ہیں: ہم ایلیپسائڈ سے تمام پوائنٹس y کاٹتے ہیں جس کے لیے۔ نوٹ کریں کہ یہ ناقابل عمل ہو سکتا ہے، اس لیے اس کی قیمت او پی ٹی سے زیادہ ہو سکتی ہے۔ لہذا، ہم کچھ نکات کو ہٹا سکتے ہیں جن کا مقصد زیادہ سے زیادہ ہے۔ تاہم، ہٹائے گئے پوائنٹس مطمئن کرتے ہیں ؛ کوئی پوائنٹ نہیں ہٹایا جاتا ہے اگر اس کی قیمت قیمت سے زیادہ ہو۔ لگ بھگ علیحدگی اوریکل کا استعمال دوہری ایل پی کے لیے ایک قابل عمل حل y * فراہم کرتا ہے، زیادہ تر تکرار کے بعد، جہاں۔ لگ بھگ علیحدگی اوریکل کے ساتھ ایلیپسائڈ طریقہ کار کا کل رن ٹائم ہے۔ رکاوٹوں کو ختم کرنا ایلیپسائڈ طریقہ کار کے دوران، ہم فارم کی زیادہ سے زیادہ ق رکاوٹوں کا استعمال کرتے ہیں۔ دیگر تمام رکاوٹوں کو ختم کیا جا سکتا ہے، کیونکہ ان کا ایلیپسائڈ طریقہ کار کے نتیجہ y * پر کوئی اثر نہیں پڑتا ہے۔ ہم مزید رکاوٹوں کو ختم کر سکتے ہیں۔ یہ معلوم ہے کہ، m متغیر کے ساتھ کسی بھی LP میں، m رکاوٹوں کا ایک مجموعہ ہوتا ہے جو زیادہ سے زیادہ حل کا تعین کرنے کے لیے کافی ہوتا ہے (یعنی، زیادہ سے زیادہ قیمت یکساں ہوتی ہے چاہے صرف یہ m رکاوٹیں استعمال کی جائیں)۔ ہر بار رکاوٹوں کے ایک مخصوص سیٹ کو دور کرنے کی کوشش کرتے ہوئے، ہم اوپر کے طور پر ایلیپسائڈ طریقہ کو بار بار چلا سکتے ہیں۔ اگر نتیجے میں ہونے والی غلطی زیادہ سے زیادہ ہے، تو ہم ان رکاوٹوں کو مستقل طور پر دور کرتے ہیں۔ یہ دکھایا جا سکتا ہے کہ ہمیں زیادہ سے زیادہ خاتمے کی ضرورت ہے، لہذا جمع کرنے کی غلطی زیادہ سے زیادہ ہے۔ اگر ہم پابندیوں کے سیٹ کو تعیناتی طور پر آزماتے ہیں، تو بدترین صورت میں، m ٹرائلز میں سے ایک کامیاب ہو جاتا ہے، لہذا ہمیں زیادہ تر اوقات میں ایلیپسائڈ طریقہ چلانے کی ضرورت ہوتی ہے۔ اگر ہم بے ترتیب طور پر ہٹانے کے لیے رکاوٹوں کا انتخاب کرتے ہیں، تو تکرار کی متوقع تعداد ہے۔ آخر میں، ہمارے پاس ایک کم شدہ دوہری ایل پی ہے، جس میں صرف m متغیر اور m رکاوٹیں ہیں۔ کم شدہ ایل پی کی زیادہ سے زیادہ قیمت کم از کم کہاں ہے۔ پرائمل ایل پی کو حل کرنا ایل پی ڈوئلٹی تھیوریم کے ذریعہ، پرائمل ایل پی کی کم از کم قیمت ڈوئل ایل پی کی زیادہ سے زیادہ قیمت کے برابر ہوتی ہے، جسے ہم ایل او پی ٹی سے ظاہر کرتے ہیں۔ ایک بار جب ہمارے پاس کم شدہ ڈوئل ایل پی ہوتا ہے، تو ہم اس کا ڈوئل لیتے ہیں، اور کم شدہ پرائمل ایل پی لیتے ہیں۔ اس ایل پی میں صرف m متغیرات ہیں-جو کہ C ترتیبات میں سے صرف m سے مطابقت رکھتے ہیں۔ کم شدہ ڈوئل ایل پی کی زیادہ سے زیادہ قیمت کم از کم ہے۔ یہ دکھایا جا سکتا ہے کہ کم شدہ ابتدائی ایل پی کا بہترین حل زیادہ سے زیادہ ہے۔ حل زیادہ سے زیادہ میٹر ترتیبات کا استعمال کرتے ہوئے قریب قریب بہترین بن پیکنگ دیتا ہے۔ تعیناتی الگورتھم کا کل رن ٹائم، جب تمام آئٹمز اس سے بڑے ہوتے ہیں، ہے:، بے ترتیب الگورتھم کا متوقع کل رن ٹائم ہے: اینڈ ٹو اینڈ الگورتھم کرمارکر اور کارپ نے تین الگورتھم پیش کیے، جو مختلف پیرامیٹرز کے ساتھ مندرجہ بالا تکنیکوں کا استعمال کرتے ہیں۔ ان تمام الگورتھم کا رن ٹائم ایک فنکشن پر منحصر ہوتا ہے، جو کہ ایک کثیر الجہتی فنکشن ہے جو ٹالرنس ایچ = 1 کے ساتھ فریکشنل ایل پی کو حل کرنے میں لگنے والے وقت کو بیان کرتا ہے، جو کہ تعیناتی ورژن کے لیے ہے۔ الگورتھم 1 ایک مستقل ہونا چاہیے جو مطلوبہ تخمینہ کی درستگی کی نمائندگی کرتا ہے۔ 1-اے۔ سیٹ کریں۔ جی۔ 2-اے سے چھوٹی تمام اشیاء کو ہٹا کر ایک مثال بنائی جائے۔ سیٹ کریں۔ آئیے پیرامیٹر k کے ساتھ لکیری گروپنگ کے ذریعے بنائی گئی ایک مثال بنیں، اور بقیہ مثال بنیں (k سب سے بڑی اشیاء کا گروپ)۔ اس بات کو نوٹ کریں۔ 3-اے۔ انضمام کی رکاوٹوں کے بغیر ترتیب لکیری پروگرام کی تعمیر کریں۔ 4. x کے لیے حل کا حساب لگائیں، جس میں رواداری h = 1 ہو۔ نتیجہ ڈبوں کے ساتھ ایک فریکشنل ڈبے کی پیکنگ ہے۔ رن ٹائم ہے۔ 3-بی۔ کے لیے ایک لازمی حل کے لیے x کو گول کریں۔ فریکشنل حصے کے لیے زیادہ سے زیادہ ڈبے شامل کریں۔ ڈبوں کی کل تعداد ہے۔ 2-بی۔ زیادہ سے زیادہ کے ڈبوں میں اشیاء کو پیک کریں ؛ ایک پیکنگ حاصل کریں۔ ڈبوں کی تعداد ہے۔ 1-بی۔ حل حاصل کرنے کے لیے جی سے چھوٹی اشیاء شامل کریں۔ ڈبوں کی تعداد یہ ہے: مجموعی طور پر، ڈبوں کی تعداد اندر ہے اور رن ٹائم اندر ہے۔ منتخب کرنے سے ہم حاصل کرتے ہیں۔ الگورتھم 2 ایک حقیقی پیرامیٹر اور ایک انٹیجر پیرامیٹر ہونے دیں جس کا تعین بعد میں کیا جائے۔ 1-اے۔ جی۔ 2 سے چھوٹی تمام اشیاء کو ہٹا کر ایک مثال بنائی جائے۔ کرتے وقت: 2-a۔ پیرامیٹر k کے ساتھ متبادل جیومیٹرک گروپنگ کریں۔ نتیجہ خیز مثال بنیں، اور بقیہ مثال بنیں۔ ہمارے پاس ہے۔ 3-اے۔ انضمام کی رکاوٹوں کے بغیر ترتیب لکیری پروگرام کی تعمیر کریں۔ 4. x کے لیے حل کا حساب لگائیں، جس میں رواداری h = 1 ہو۔ نتیجہ ڈبوں کے ساتھ ایک فریکشنل ڈبے کی پیکنگ ہے۔ رن ٹائم ہے۔ 3-بی۔ کے لیے ایک لازمی حل کے لیے x کو گول کریں۔ فریکشنل حصے کے لیے ڈبے شامل نہ کریں۔ اس کے بجائے، بس پیک شدہ اشیاء کو ہٹا دیں۔ 2-بی۔ زیادہ تر ڈبوں میں اشیاء کو پیک کریں۔ 2. ایک بار، باقی اشیاء کو زیادہ سے زیادہ ڈبوں میں لالچ سے پیک کریں۔ مرحلہ 2 میں لوپ کے ہر تکرار پر، x کے فریکشنل حصے میں زیادہ سے زیادہ m (K) پیٹرن ہوتے ہیں، لہذا۔ ایف او پی ٹی ہر تکرار میں کے کے عنصر سے گرتا ہے، اس لیے تکرار کی تعداد زیادہ سے زیادہ ہوتی ہے۔ لہذا، استعمال ہونے والے ڈبوں کی کل تعداد یہ ہے: 1-بی۔ حل حاصل کرنے کے لیے جی سے چھوٹی اشیاء شامل کریں۔ ڈبوں کی تعداد یہ ہے: رن ٹائم اندر ہے۔ اب، اگر ہم k = 2 اور g = 1/FOPT (I) کا انتخاب کرتے ہیں، تو ہمیں ملتا ہے:، اور اس لیے:، تو ڈبوں کی کل تعداد میں ہے۔ رن ٹائم ہے۔ ایک ہی الگورتھم کو مختلف پیرامیٹرز کے ساتھ استعمال کیا جا سکتا ہے تاکہ درستگی کے ساتھ رن ٹائم کو ٹریڈ آف کیا جا سکے۔ کچھ پیرامیٹر کے لیے، اور منتخب کریں۔ پھر، پیکنگ کو زیادہ تر ڈبوں کی ضرورت ہوتی ہے، اور رن ٹائم اندر ہوتا ہے۔ الگورتھم 3 تیسرا الگورتھم اس وقت مفید ہوتا ہے جب سائز m کی تعداد کم ہوتی ہے (ہائی ملٹی پلیسیٹی بن پیکنگ بھی دیکھیں)۔ 1-اے۔ سیٹ کریں۔ جی سے چھوٹی تمام اشیاء کو ہٹا کر ایک مثال بنائی جائے۔ اگر تب: 3-اے۔ انضمام کی رکاوٹوں کے بغیر ترتیب لکیری پروگرام کی تعمیر کریں۔ 4. x کے لیے حل کا حساب لگائیں، جس میں رواداری h = 1 ہو۔ نتیجہ ڈبوں کے ساتھ ایک فریکشنل ڈبے کی پیکنگ ہے۔ رن ٹائم ہے۔ 3-بی۔ کے لیے ایک لازمی حل کے لیے x کو گول کریں۔ فریکشنل حصے کے لیے ڈبے شامل نہ کریں۔ اس کے بجائے، بس پیک شدہ اشیاء کو ہٹا دیں۔ بقیہ ٹکڑوں پر الگورتھم 2 کا مرحلہ 2 چلائیں۔ 1-بی۔ حل حاصل کرنے کے لیے جی سے چھوٹی اشیاء شامل کریں۔ ڈبوں کی تعداد یہ ہے: یہ زیادہ تر ڈبوں میں استعمال ہوتا ہے، اور رن ٹائم اندر ہوتا ہے۔ بہتری کے کے تکنیکوں کو بعد میں بہتر بنایا گیا تاکہ اس سے بھی بہتر تخمینہ فراہم کیا جا سکے۔ روتھوس الگورتھم 2 کی طرح ہی اسکیم استعمال کرتا ہے، لیکن مرحلہ 2 میں ایک مختلف گول کرنے کے طریقہ کار کے ساتھ۔ اس نے ایک "گلوئنگ" مرحلہ متعارف کرایا، جس میں چھوٹی اشیاء کو ایک ساتھ چپکا کر ایک بڑی چیز حاصل کی جاتی ہے۔ اس گلوئنگ کا استعمال سب سے چھوٹی آئٹم کے سائز کو تقریبا بڑھانے کے لیے کیا جا سکتا ہے۔ جب تمام سائز کم از کم ہوتے ہیں، تو ہم الگورتھم 2 کی گارنٹی میں تبدیل کر سکتے ہیں، اور حاصل کر سکتے ہیں:، جس سے ڈبے نکلتے ہیں۔ ہوبرگ اور روتھوس اسی طرح کی اسکیم کا استعمال کرتے ہیں جس میں اشیاء کو پہلے "کنٹینرز" میں پیک کیا جاتا ہے، اور پھر کنٹینرز کو ڈبے میں پیک کیا جاتا ہے۔ ان کے الگورتھم کو زیادہ تر ڈبوں کی ضرورت ہوتی ہے۔ حوالہ جات بن پیکنگ