Integer programming — صحیح عددی پروگرامنگ

صحیح عددی پروگرامنگ (ص ع پ؛ انگریزی: integer programming, IP) — یہ ریاضیاتی اصلاح کا وہ شعبہ ہے جس میں ایسے مسائل کا مطالعہ کیا جاتا ہے جہاں کچھ یا تمام متغیرات کو صرف صحیح عددی قدریں اختیار کرنی ہوتی ہیں۔

سب سے زیادہ مطالعہ شدہ خاص صورت صحیح عددی خطی پروگرامنگ (ص ع خ پ؛ انگریزی: integer linear programming, ILP) ہے، جس میں ہدف فنکشن اور قیود خطی ہوتے ہیں۔ خطی پروگرامنگ کے برعکس، جہاں متغیرات کوئی بھی حقیقی قدر اختیار کر سکتے ہیں، صحیح عددیت کی شرط ص ع پ کے مسائل کو حل کرنا نمایاں طور پر زیادہ پیچیدہ بنا دیتی ہے۔

صحیح عددی پروگرامنگ معاشیات، لاجسٹکس، پیداوار کی منصوبہ بندی اور دیگر شعبوں میں وسیع پیمانے پر استعمال ہوتی ہے، جہاں متغیرات فطری طور پر منقطع ہوتے ہیں (مثلاً تیار کردہ اکائیوں کی تعداد یا کارکنوں کی تعداد)۔

تعریف اور اصطلاحات

صحیح عددی خطی پروگرامنگ کا عمومی مسئلہ درج ذیل طریقے سے لکھا جا سکتا ہے:

ویکٹر $x$ معلوم کریں جو:

زیادہ سے زیادہ (یا کم سے کم) کرے $c^{T}x$

شرائط کے ساتھ:

$Ax\le b$

$x\ge 0$

$x\in {\mathbb{\mathbb{Z}}}^n$ (ویکٹر $x$ کے تمام اجزاء — صحیح اعداد ہیں)

جہاں $x$ — متغیرات کا ویکٹر، $c$ اور $b$ — ویکٹرز، اور $A$ — گتانکوں کی میٹرکس ہے۔

متغیرات کے تقاضوں کے اعتبار سے مسائل کی درج ذیل اقسام ممتاز کی جاتی ہیں:

• مکمل صحیح عددی پروگرامنگ: تمام متغیرات صحیح اعداد ہونے چاہیے۔
• مخلوط صحیح عددی پروگرامنگ (انگریزی: mixed-integer programming, MIP): صرف کچھ متغیرات صحیح عددی ہونے چاہیے۔
• بولین (0-1) پروگرامنگ: متغیرات صرف 0 یا 1 کی قدریں اختیار کرتے ہیں، جس سے "ہاں/نہیں" قسم کے منطقی فیصلوں کی ماڈلنگ ممکن ہوتی ہے۔

کلیدی خصوصیات اور پیچیدگی

حسابی پیچیدگی

صحیح عددی خطی پروگرامنگ کا مسئلہ عمومی صورت میں NP-hard ہے۔ اس کا مطلب یہ ہے کہ کوئی معروف الگورتھم موجود نہیں جو ص ع پ کے کسی بھی دلخواہ مسئلے کا عین بہترین حل کثیر رقمی وقت میں تلاش کر سکے۔ یہ پیچیدگی مسئلے کی اشتراکی نوعیت کی وجہ سے ہے، کیونکہ ممکنہ صحیح عددی حلوں کی تعداد متغیرات کی تعداد بڑھنے کے ساتھ اعشاری طور پر بڑھ سکتی ہے۔

خطی پروگرامنگ سے تعلق (LP-نرمی)

ص ع پ کے کسی بھی مسئلے کے لیے اس کی خطی نرمی — خطی پروگرامنگ (ایل پی) کا مسئلہ — وضع کی جا سکتی ہے، جس میں متغیرات کی صحیح عددیت کی شرط ہٹا دی جاتی ہے۔ LP-نرمی کے حل میں دو اہم خصوصیات ہیں:

1. اسے نمایاں طور پر زیادہ تیزی سے (کثیر رقمی وقت میں) تلاش کیا جا سکتا ہے۔
2. LP-نرمی کے ہدف فنکشن کی بہترین قدر اصل صحیح عددی مسئلے کی بہترین قدر کے لیے ایک تخمینہ (زیادہ سے زیادہ کرنے کے مسئلے میں اوپری حد اور کم سے کم کرنے میں نچلی حد) فراہم کرتی ہے۔

تاہم، LP-نرمی کے کسری حل کو قریب ترین صحیح اعداد تک گول کرنا عموماً صحیح عددی مسئلے کا بہترین یا حتیٰ کہ قابل قبول حل نہیں دیتا۔

مکمل یونی ماڈیولریٹی کی خاصیت

ص ع خ پ کے مسائل کا ایک اہم طبقہ ایسا ہے جو اپنی LP-نرمیوں جتنی آسانی سے حل ہو جاتا ہے۔ یہ وہ مسائل ہیں جن میں قیود کی میٹرکس $A$ مکمل یونی ماڈیولر ہوتی ہے (یعنی اس کی کسی بھی مربع ذیلی میٹرکس کا تعین کنندہ 0، +1 یا −1 کے برابر ہے)۔ اگر میٹرکس $A$ مکمل یونی ماڈیولر ہو اور ویکٹر $b$ صحیح عددی ہو، تو LP-نرمی کے قابل قبول حلوں کے کثیر الاضلاع کے تمام رأس خود بخود صحیح عددی ہوں گے۔ نتیجتاً سمپلیکس طریقے سے ملنے والا حل صحیح عددی ہوگا۔ ایسے مسائل کی مثالیں نقل و حمل کا مسئلہ اور تفویض کا مسئلہ ہیں۔

حل کے طریقے

مکمل یونی ماڈیولریٹی کی خاصیت سے عاری عمومی ص ع پ مسائل کے حل کے لیے مضمر شمار کے خیالات پر مبنی درست طریقے وضع کیے گئے ہیں۔

• شاخ و حد کا طریقہ (انگریزی: Branch and Bound) — بنیادی درست طریقہ، جو قابل قبول حلوں کے مجموعے کو منظم طریقے سے ذیلی مجموعوں میں تقسیم کرنے (شاخ بندی) اور ان ذیلی مجموعوں کو کاٹنے پر مبنی ہے جن میں یقیناً بہترین حل موجود نہیں۔ ذیلی مجموعوں کی امیدواری کے تخمینے کے لیے LP-نرمی استعمال کی جاتی ہے۔

• قاطع ہواسطوں کا طریقہ (گوموری کا طریقہ؛ انگریزی: Cutting Plane Method) — ایک تکراری طریقہ جو مسئلے میں یکے بعد دیگرے نئے خطی قیود ("قطعیں") شامل کرتا ہے۔ یہ قطعیں LP-نرمی کے کسری حلوں کو "کاٹتی" ہیں، لیکن کسی بھی قابل قبول صحیح عددی حل کو متاثر نہیں کرتیں، اور آہستہ آہستہ LP-نرمی کے قابل قبول حلوں کے خطے کو صحیح عددی حلوں کے محدب خول کے قریب لاتی ہیں۔

جدید حل کنندے عموماً ہائبرڈ الگورتھم استعمال کرتے ہیں، جیسے شاخ و قطع کا طریقہ (انگریزی: Branch and Cut)، جو دونوں طریقوں کے فوائد کو یکجا کرتا ہے۔

مثالیں اور استعمال کے شعبے

صحیح عددی پروگرامنگ اشتراکی اصلاح کے بہت سے کلاسیکی مسائل کی ماڈلنگ کی اجازت دیتی ہے۔

• بستے کا مسئلہ: 0-1 پروگرامنگ کا کلاسیکی مسئلہ، جس میں زیادہ سے زیادہ کل قیمت کے ساتھ اشیاء کا ایک مجموعہ منتخب کرنا ہوتا ہے، جبکہ کل وزن کی حد سے تجاوز نہ کیا جائے۔
• سیلزمین کا مسئلہ: شہروں کے مقررہ مجموعے سے گزرنے والے مختصر ترین راستے کی تلاش کا مسئلہ۔ اسے صحیح عددی پروگرامنگ کے مسئلے کے طور پر وضع کیا جا سکتا ہے، جہاں متغیرات گراف کے کناروں کو حتمی راستے میں شامل کرنے کے ذمہ دار ہیں۔

اپنی لچک کی بدولت، ص ع پ آپریشنز ریسرچ میں سب سے زیادہ مطلوب آلات میں سے ایک ہے اور درج ذیل شعبوں میں استعمال ہوتی ہے:

• لاجسٹکس اور سپلائی چین مینجمنٹ: نقل و حمل کے راستوں کی اصلاح، گوداموں کی جگہ کا تعین، ذخیرہ اندوزی کا انتظام۔
• پیداوار کی منصوبہ بندی: پیداواری نظام الاوقات کی تیاری، وسائل کی تقسیم، آلات کی لوڈنگ۔
• مالیات اور معاشیات: سرمایہ کاری پورٹ فولیو کی تشکیل، سرمائے کی سرمایہ کاری کا بجٹ بندی۔
• ٹیلی کمیونیکیشن اور توانائی: مواصلاتی نیٹ ورکس کی ڈیزائننگ، توانائی یونٹوں کے آپریشن کی منصوبہ بندی۔

یہ بھی دیکھیں

• خطی پروگرامنگ
• شاخ و حد کا طریقہ

حوالہ جات

</references>