مسئله بسته‌بندی

مساله بسته بندی کلاسیک ()،   (BPP)     به دلیل کاربردهای بسیار زیاد و ساختار ترکیبیاتی خوب آن به طور گسترده ای در مقالات تحقیق در عملیات، علوم کامپیوتر و مهندسی صنایع مورد توجه قرار گرفته است . از دیدگاه نظری این مساله می‌تواند زیر مساله تعداد زیادی از مسائل بهینه‌سازی ترکیبیاتی (مانند مساله مسیریابی خودرو) باشد. این مساله اولین بار در سال 1971 میلادی توسط  معرفی گردید.  در مساله بسته‌بندی یک بعدی مجموعه‌ای متناهی از اشیاء وزن‌دار باید در کمترین تعداد ممکن از بسته‌های با ظرفیت یکسان قرار داده شود . 

مسئله بسته‌بندی را می‌توان به عنوان یک حالت خاص از مسئله برش ورق در نظر گرفت.

## تعریف و مدلسازی ریاضی مساله بسته‌بندی
 
فرض کنید تعداد n شی با وزن‌های w1، w2، ... ، wn داده شده باشد. یک بسته‌بندی از این اشیاء را در کمترین تعداد ممکن از بسته‌های مشابه به ظرفیت واحد پیدا کنید که مجموع وزن اشیاء داخل هر بسته از ظرفیت بسته تجاوز نکند.
 
مساله بسته‌بندی می تواند به صورت یک مساله برنامه ریزی خطی عدد صحیح و به صورت زیر مدلسازی شود.

که در آن  y_j = 1 اگر بسته j مورد استفاده قرار گیرد و  x_{ij} = 1 اگر شی iام در بین j ام بسته بندی شود.
 
## پیچیدگی مساله
مساله بسته‌بندی یک مساله قویاً NP -سخت است. چون حتی در حالتی که همه پارامترهای مساله با یک چند‌جمله‌ای از ابعاد مساله محدود شوند نیز مساله NP -سخت باقی می‌ماند و بنابراین می‌توان نتیجه گرفت که با فرض P≠NP الگوریتمی شبه چندجمله‌ای برای BPP وجود ندارد .

به علاوه، هیچ الگوریتم تقریبی با فاکتور تقریب کوچکتر از \tfrac 3 2 برای مساله بسته‌بندی وجود ندارد مگر اینکه \mathsf{P} = \mathsf{NP}. این می‌تواند با کاهش از مسئلهٔ افراز ثابت شود: با توجه به نمونه‌ای از مساله افراز که مجموع همهٔ اعداد ورودی 2T است، نمونه‌ای از مساله بسته‌بندی را ایجاد کنید که در آن ظرفیت بسته  است. اگر افراز برابر ورودی‌ها وجود داشته باشد، پس بسته‌بندی بهینه نیاز به 2 بسته دارد؛ بنابراین، هر الگوریتم با نسبت تقریب کوچکتر از  باید کمتر از 3 بسته را برگرداند، که باید 2 بسته باشد. در مقابل، اگر افراز برابر ورودی‌ها وجود نداشته باشد، پس بسته‌بندی بهینه حداقل به 3 بسته نیاز دارد.
## الگوریتم های تقریبی برای مساله بسته‌بندی
برای اندازه‌گیری عملکرد یک الگوریتم تقریبی، دو نوع نسبت تقریب در ادبیات موضوع مورد بررسی قرار می‌گیرند. برای یک لیست داده شده از اشیاء L، عدد A(L) تعداد بسته‌های استفاده شده را نشان می‌دهد زمانی که الگوریتم A بر روی لیست L اعمال می‌شود، در حالی که \mathrm{OPT}(L) تعداد بهینه برای این لیست را نشان می‌دهد. نسبت عملکرد بدترین حالت مطلق R_A برای یک الگوریتم A به صورت زیر تعریف می‌شود:

: R_A \equiv \inf\{r \geq 1 : \forall  L \quad  A(L)/\mathrm{OPT}(L) \leq r \}.

از طرف دیگر، نسبت بدترین حالت مجانبی R_A^{\infty} به صورت زیر تعریف می‌شود:

: R_A^\infty \equiv \inf\{ r \geq 1: \exists N >0, \forall  L \   (\mathrm{OPT}(L) \geq N) \quad A(L)/\mathrm{OPT}(L) \leq r \}.

به طور معادل، R_A^{\infty} کوچکترین عددی است که برای ثابت *K*ای و برای همهٔ لیست‌های *L:*****

: A(L) \leq R^{\infty}_A \cdot \mathrm{OPT}(L) + K.

علاوه بر این، می‌توان لیست‌ها را به آنهایی محدود کرد که همهٔ اشیاء در آن‌ها اندازه‌ای حداکثر \alpha دارند. برای چنین لیست‌هایی، نسبت‌های عملکرد اندازه محدود به صورت R_A(\text{size}\leq \alpha) و R_A^\infty(\text{size}\leq \alpha) نشان داده می‌شوند.

الگوریتم‌های تقریبی برای بسته‌بندی در جعبه می‌توانند به دو دسته تقسیم شوند: 
# هیوریستیک‌های آنلاین، که اشیاء را در ترتیب داده شده در نظر می‌گیرند و آن‌ها را یکی یکی درون بسته‌ها قرار می‌دهند. این هیوریستیک‌ها همچنین قابل اجرا برای نسخهٔ آنلاین این مسئله هستند.
# هیوریستیک‌های آفلاین، که لیست داده شده از اشیاء را تغییر می‌دهند، به عنوان مثال با مرتب‌سازی اشیاء بر اساس اندازه. این الگوریتم‌ها دیگر قابل اجرا برای نسخهٔ آنلاین این مسئله نیستند. با این حال، آن‌ها یک تضمین تقریب بهبود یافته دارند در حالی که مزیت پیچیدگی زمان کوچک خود را حفظ می‌کنند. یک زیر دسته از هیوریستیک‌های آفلاین، طرح‌های تقریب مجانبی است. این الگوریتم‌ها یک تضمین تقریب به شکل (1+\varepsilon)\mathrm{OPT}(L) + C دارند برای بعضی ثابت که ممکن است بستگی به 1/\varepsilon داشته باشد. برای یک \mathrm{OPT}(L) به صورت دلخواه بزرگ، این الگوریتم‌ها به صورت دلخواه نزدیک به \mathrm{OPT}(L) می‌شوند. با این حال، این به قیمت افزایش (شدید) پیچیدگی زمانی در مقایسه با رویکردهای هیوریستیک‌ است.

## جستارهای وابسته
* مسئله تقسیم‌بندی
* مسئله جمع زیرمجموعه‌ها

## منابع

* 
رده:روش‌های بهینه‌سازی