Configuration linear program
ترتیب لکیری پروگرام (ترتیب-ایل پی) ایک لکیری پروگرامنگ تکنیک ہے جو مشترکہ اصلاح کے مسائل کو حل کرنے کے لیے استعمال ہوتی ہے۔ اسے اسٹاک کاٹنے کے مسئلے کے تناظر میں متعارف کرایا گیا تھا۔ بعد میں، اس کا اطلاق بن پیکنگ اور جاب شیڈولنگ کے مسائل پر کیا گیا ہے۔ کنفیگریشن-ایل پی میں، ہر ممکنہ ترتیب کے لیے ایک متغیر ہوتا ہے-آئٹمز کا ہر ممکنہ ملٹی سیٹ جو ایک بن میں فٹ ہو سکتا ہے (ان ترتیبات کو پیٹرن بھی کہا جاتا ہے)۔ عام طور پر، دشواری کے سائز میں ترتیبات کی تعداد متغیر ہوتی ہے، لیکن بعض صورتوں میں ترتیبات کی صرف کثیر تعداد کا استعمال کرتے ہوئے تخمینہ حل حاصل کرنا ممکن ہے۔ بن پیکنگ میں انٹیگرل ایل پی بن پیکنگ کے مسئلے میں، مختلف سائز کے n آئٹمز ہوتے ہیں۔ مقصد یہ ہے کہ اشیاء کو کم سے کم ڈبوں میں پیک کیا جائے، جہاں ہر ڈبے میں زیادہ سے زیادہ بی ہو سکتا ہے۔ ایک قابل عمل ترتیب سائز کا ایک مجموعہ ہے جس کا مجموعہ زیادہ سے زیادہ B ہوتا ہے۔ مثال: فرض کریں کہ آئٹم کے سائز 3,3,3، 3,3,4,4,4، 4,4، اور B = 12 ہیں۔ پھر ممکنہ ترتیبات یہ ہیں: 3333 ؛ 333 ؛ 33، 334 ؛ 3، 34، 344 ؛ 4، 44، 444۔ اگر ہمارے پاس سائز 3 کی صرف تین اشیاء ہوتیں، تو ہم 3333 ترتیب کا استعمال نہیں کر سکتے تھے۔ مختلف سائز کے سیٹ (اور ان کی تعداد) کو S سے ظاہر کریں۔ مختلف ترتیبات (اور ان کی تعداد) کے سیٹ کو C سے ظاہر کریں۔ ایس میں ہر سائز ایس اور سی میں ترتیب سی کے لیے، اشارہ کریں: این ایس-سائز ایس کی اشیاء کی تعداد۔ جیسا کہ، سی-ترتیب میں سائز ایس کے واقعات کی تعداد سی۔ ایکس سی-ایک متغیر جو ترتیب سی کے ساتھ ڈبوں کی تعداد کو ظاہر کرتا ہے۔ پھر، بن پیکنگ کی ترتیب ایل پی ہے: ایس میں تمام ایس کے لیے (-سائز ایس کے تمام این ایس آئٹمز پیک ہیں)۔ سی میں تمام سی کے لیے (-مجموعی طور پر زیادہ سے زیادہ این ڈبے ہوتے ہیں، لہذا ہر انفرادی ترتیب کے زیادہ سے زیادہ این)۔ کنفیگریشن ایل پی ایک انٹیجر لکیری پروگرام ہے، اس لیے عام طور پر یہ این پی ہارڈ ہوتا ہے۔ مزید برآں، یہاں تک کہ مسئلہ خود بھی عام طور پر بہت بڑا ہوتا ہے: اس میں C متغیرات اور S رکاوٹیں ہوتی ہیں۔ اگر سب سے چھوٹی آئٹم کا سائز ای بی ہے (کچھ فریکشن ای کے لیے (0,1) میں)، تو ہر ڈبے میں 1/ای آئٹمز تک ہو سکتے ہیں، لہذا ترتیبات کی تعداد سی ~ ایس 1/ای، جو کہ بہت بڑی ہو سکتی ہے اگر ای چھوٹا ہے (اگر ای کو مستقل سمجھا جاتا ہے، تو انٹیجر ایل پی کو مکمل تلاش کے ذریعے حل کیا جا سکتا ہے: زیادہ سے زیادہ ایس 1/ای ترتیبات ہیں، اور ہر ترتیب کے لیے زیادہ سے زیادہ این ممکنہ اقدار ہیں، لہذا چیک کرنے کے لیے زیادہ سے زیادہ امتزاج موجود ہیں۔ ہر امتزاج کے لیے، ہمیں S رکاوٹوں کو چیک کرنا ہوگا، لہذا رن ٹائم ہے، جو کہ n میں کثیر الجہتی ہے جب S، e مستقل ہوتے ہیں)۔ تاہم، یہ آئی ایل پی کئی تخمینہ الگورتھم کی بنیاد کے طور پر کام کرتا ہے۔ ان الگورتھم کا بنیادی خیال اصل مثال کو ایک نئی مثال میں کم کرنا ہے جس میں S چھوٹا اور e بڑا ہے، لہذا C نسبتا چھوٹا ہے۔ پھر، آئی ایل پی کو یا تو مکمل تلاش کے ذریعے حل کیا جا سکتا ہے (اگر ایس، سی کافی چھوٹے ہیں)، یا اسے فریکشنل ایل پی میں آرام دے کر۔ فریکشنل ایل پی بن پیکنگ کا فریکشنل کنفیگریشن ایل پی یہ مندرجہ بالا آئی ایل پی کی لکیری پروگرامنگ نرمی ہے۔ یہ آخری رکاوٹ کو رکاوٹ سے بدل دیتا ہے۔ دوسرے لفظوں میں، ہر ترتیب کو فریکشنل تعداد میں استعمال کیا جا سکتا ہے۔ یہ نرمی سب سے پہلے گلمور اور گوموری نے پیش کی تھی، اور اسے اکثر گلمور-گوموری لکیری پروگرام کہا جاتا ہے۔ مثال: فرض کریں کہ سائز 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 ڈبے ہیں۔ نوٹ کریں کہ صرف دو مختلف ترتیبات کی ضرورت ہے۔ مختصرا، فریکشنل LP کو اس طرح لکھا جا سکتا ہے: جہاں 1 سائز C کا ویکٹر (1، 1) ہے، A ایک S-by-C میٹرکس ہے جس میں ہر کالم ایک واحد ترتیب کی نمائندگی کرتا ہے، اور n ویکٹر (n1،.، nS) ہے۔ فریکشنل ایل پی کو حل کرنا ایک لکیری پروگرام جس میں کوئی انٹیگریلیٹی رکاوٹیں نہیں ہیں اسے متغیرات اور رکاوٹوں کی تعداد میں ٹائم پولینومیل میں حل کیا جا سکتا ہے۔ مسئلہ یہ ہے کہ فریکشنل کنفیگریشن ایل پی میں متغیرات کی تعداد ممکنہ ترتیبات کی تعداد کے برابر ہے، جو بہت زیادہ ہو سکتی ہے۔ کرمارکر اور کارپ ایک الگورتھم پیش کرتے ہیں جو اس مسئلے پر قابو پاتا ہے۔ سب سے پہلے، وہ فریکشنل ایل پی کے دوہری لکیری پروگرام کی تعمیر کرتے ہیں:۔ اس میں ایس متغیر y1،.، yS، اور C رکاوٹیں ہیں: ہر ترتیب c کے لیے، ایک رکاوٹ ہے، جہاں ترتیب c کی نمائندگی کرنے والا A کا کالم ہے۔ 3 اس کی درج ذیل معاشی تشریح ہے۔ ہر سائز s کے لیے، ہمیں ایک غیر منفی قیمت ys کا تعین کرنا چاہیے۔ ہمارا منافع تمام اشیاء کی کل قیمت ہے۔ ہم ان رکاوٹوں کے تابع منافع کو زیادہ سے زیادہ کرنا چاہتے ہیں کہ ہر ترتیب میں اشیاء کی کل قیمت زیادہ سے زیادہ 1 ہو۔ دوسرا، وہ ایلیپسائڈ طریقہ کار کی ایک قسم کا اطلاق کرتے ہیں، جس میں تمام رکاوٹوں کو درج کرنے کی ضرورت نہیں ہے-اسے صرف علیحدگی اوریکل کی ضرورت ہے۔ علیحدگی اوریکل ایک الگورتھم ہے جو، ویکٹر y کو دیکھتے ہوئے، یا تو اس بات پر زور دیتا ہے کہ یہ ممکن ہے، یا کسی رکاوٹ کو تلاش کرتا ہے جس کی یہ خلاف ورزی کرتا ہے۔ ڈوئل ایل پی کے لیے علیحدگی اوریکل کو سائز s اور اقدار y کے ساتھ نیپسیک کے مسئلے کو حل کرکے نافذ کیا جا سکتا ہے: اگر نیپسیک کے مسئلے کے زیادہ سے زیادہ حل کی کل قیمت زیادہ سے زیادہ 1 ہے، تو y ممکن ہے ؛ اگر یہ 1 سے بڑا ہے، y سے زیادہ ممکن نہیں ہے، اور نیپسیک کے مسئلے کا زیادہ سے زیادہ حل اس ترتیب کی نشاندہی کرتا ہے جس کے لیے رکاوٹ کی خلاف ورزی کی گئی ہے۔ تیسرا، وہ دکھاتے ہیں کہ، نیپسیک کے مسئلے کے تخمینہ حل کے ساتھ، کوئی بھی دوہری ایل پی کا تخمینہ حل حاصل کر سکتا ہے، اور اس سے، ابتدائی ایل پی کا تخمینہ حل ؛ کرمارکر-کارپ بن پیکنگ الگورتھم دیکھیں۔ مجموعی طور پر، کسی بھی رواداری عنصر ایچ کے لیے، زیادہ سے زیادہ ایل او پی ٹی (آئی) + ایچ پر لاگت کا ایک بنیادی قابل عمل حل تلاش کرتا ہے، اور وقت کے ساتھ چلتا ہے:، جہاں ایس مختلف سائز کی تعداد ہے، این مختلف اشیاء کی تعداد ہے، اور سب سے چھوٹی شے کا سائز ای بی ہے۔ خاص طور پر، اگر e ≤1/n اور h = 1 ہے، تو الگورتھم وقت میں زیادہ سے زیادہ LOPT + 1 ڈبے کے ساتھ حل تلاش کرتا ہے: اس الگورتھم کا ایک بے ترتیب ورژن متوقع وقت میں چلتا ہے: فریکشنل ایل پی کو گول کرنے کے لیے کرمارکر اور کارپ نے فریکشنل ایل پی کو مربوط ایل پی کے تخمینہ حل میں گول کرنے کا ایک طریقہ مزید تیار کیا۔ کرمارکر-کارپ بن پیکنگ الگورتھم دیکھیں۔ ان کے ثبوت سے پتہ چلتا ہے کہ اس ایل پی کا اضافی انضمام فرق او (لاگ 2 (این)) میں ہے۔ بعد میں، ہوبرگ اور روتھوس نے اپنے نتائج کو بہتر بنایا اور ثابت کیا کہ انضمام کا فرق O (لاگ (n)) میں ہے۔ انٹیگریلیٹی گیپ پر سب سے مشہور نچلی حد ایک مستقل ω (1) ہے۔ یکسانیت کے عین فرق کو تلاش کرنا ایک کھلا مسئلہ ہے۔ ڈبے کے ڈھانپنے میں، ڈبے کے ڈھانپنے کے مسئلے میں، مختلف سائز کے n آئٹمز ہوتے ہیں۔ مقصد یہ ہے کہ اشیاء کو زیادہ سے زیادہ ڈبوں میں پیک کیا جائے، جہاں ہر ڈبے میں کم از کم بی ہونا چاہیے۔ اس مسئلے کے لیے ایک قدرتی ترتیب ایل پی ہو سکتا ہے: جہاں اے کم از کم بی کے ساتھ آئٹمز کی تمام ترتیبات کی نمائندگی کرتا ہے (کوئی صرف شمولیت-کم سے کم ترتیبات لے سکتا ہے)۔ اس ایل پی کے ساتھ مسئلہ یہ ہے کہ، ڈبے کو ڈھانپنے کے مسئلے میں، چھوٹی اشیاء کو سنبھالنا دشواری کا باعث ہوتا ہے، کیونکہ چھوٹی اشیاء بہترین حل کے لیے ضروری ہو سکتی ہیں۔ چھوٹی اشیاء کی اجازت کے ساتھ، کرمارکر اور کارپ کی تکنیک کے لیے بھی ترتیبات کی تعداد بہت زیادہ ہو سکتی ہے۔ سیرک، جانسن اور کینین ایک متبادل ایل پی پیش کرتے ہیں۔ سب سے پہلے، وہ آئٹمز کے ایک سیٹ کی وضاحت کرتے ہیں جسے چھوٹا کہا جاتا ہے۔ T کو تمام چھوٹی اشیاء کا کل سائز سمجھیں۔ پھر، وہ ایک میٹرکس اے بناتے ہیں جو مجموعہ <2 کے ساتھ تمام ترتیبات کی نمائندگی کرتا ہے۔ پھر، وہ مندرجہ بالا ایل پی کو ایک اضافی رکاوٹ کے ساتھ سمجھتے ہیں: اضافی رکاوٹ اس بات کی ضمانت دیتی ہے کہ ڈبوں میں موجود "خالی جگہ" کو چھوٹی چھوٹی اشیاء سے پر کیا جا سکتا ہے۔ اس ایل پی کا ڈوئل زیادہ پیچیدہ ہے اور اسے ایک سادہ نیپسیک-مسئلہ علیحدگی اوریکل کے ذریعے حل نہیں کیا جا سکتا۔ سیرک، جانسن اور کینین اسے تقریبا 1/ایپسلون میں وقت کے ایکسپونینشل میں حل کرنے کے لیے ایک مختلف طریقہ پیش کرتے ہیں۔ جانسن اور سولس اوبا نے اسے تقریبا 1/ایپسلون میں وقت کے ایکسپونینشل میں حل کرنے کے لیے ایک بہتر طریقہ پیش کیا ہے۔ مشین شیڈولنگ میں غیر متعلقہ مشینوں کے شیڈولنگ کے مسئلے میں، کچھ مختلف مشینیں ہیں جن کو کچھ مختلف کاموں پر کارروائی کرنی چاہیے۔ جب مشین I جاب جے پر عمل کرتی ہے، تو اس میں پائی، جے وقت لگتا ہے۔ مقصد یہ ہے کہ مشینوں کے درمیان کاموں کو اس طرح تقسیم کیا جائے کہ مشین کا زیادہ سے زیادہ تکمیل کا وقت جتنا ممکن ہو اتنا کم ہو۔ اس مسئلے کا فیصلہ ورژن یہ ہے: وقت T دیا گیا ہے، کیا کوئی پارٹیشن ہے جس میں تمام مشینوں کا تکمیل کا وقت زیادہ سے زیادہ T ہے؟ ہر مشین i کے لیے، ملازمتوں کے بہت سے ذیلی سیٹ ہوتے ہیں جن پر مشین i کے ذریعے زیادہ سے زیادہ T پر وقت پر کارروائی کی جا سکتی ہے۔ اس طرح کے ہر ذیلی سیٹ کو مشین i کے لیے کنفیگریشن کہا جاتا ہے۔ Ci (T) کے ذریعے مشین i کے لیے تمام کنفیگریشن کا سیٹ، وقت T دیا گیا ہے۔ Ci (T) میں ہر مشین i اور کنفیگریشن c کے لیے، ایک متغیر کی وضاحت کریں جو 1 کے برابر ہے اگر مشین i میں استعمال ہونے والی اصل کنفیگریشن c ہے، اور بصورت دیگر 0 ہے۔ پھر، ایل پی کی رکاوٹیں یہ ہیں: ہر مشین کے لیے i میں 1،.، m ؛ ہر کام کے لیے j میں 1،.، n ؛ ہر i، j کے لیے۔ غیر متعلقہ مشینوں کے شیڈولنگ کے لیے کنفیگریشن-ایل پی کا انٹیگریلیٹی گیپ 2 ہے۔ ہائی ملٹی پلیسیٹی بن پیکنگ حوالہ جات بن پیکنگ نمبر پارٹیشننگ جاب شیڈولنگ لکیری پروگرامنگ بھی دیکھیں۔