packing समस्याओं का मकसद, दिए गए साइज़ के आइटम के सेट को तय packing वाले कंटेनर में पैक करने का सबसे अच्छा तरीका ढूंढना है. एक सामान्य ऐप्लिकेशन, डिलीवरी ट्रक पर बॉक्स को सही तरीके से लोड कर रहा है. आम तौर पर, क्षमता कम होने की वजह से सभी आइटम पैक नहीं किए जा सकते. ऐसे मामले में, सबसे बड़ी समस्या यह है कि आइटम का एक ऐसा सबसेट ढूंढें जिसमें कंटेनर में फ़िट होने वाले, कुल साइज़ की ज़्यादा से ज़्यादा सीमा हो.
पैकिंग की कई तरह की समस्याएं होती हैं. इनमें से दो सबसे अहम हैं, नैपसैक की समस्याएं और बिन पैकिंग.
नपसैक से जुड़ी समस्याएं
सामान्य नैपसैक समस्या में, एक कंटेनर (नैप्सैक) मौजूद होता है. आइटम में वैल्यू और साइज़ भी होते हैं. लक्ष्य उन आइटम के सबसेट को पैक करना होता है जिनकी कुल वैल्यू सबसे ज़्यादा हो.
ऐसे खास मामले के लिए जहां वैल्यू, साइज़ के बराबर होती है, लक्ष्य का मकसद पैक किए गए आइटम के कुल साइज़ को बढ़ाना होता है.
OR-टूल की मदद से, एल्गोरिदम लाइब्रेरी में मौजूद kनैपैक की समस्याओं को हल करने के लिए कई सॉल्वर इस्तेमाल किए जा सकते हैं.
kनैपैक की समस्या के कुछ सामान्य वर्शन भी उपलब्ध हैं. यहां कुछ उदाहरण दिए गए हैं:
कई डाइमेंशन वाले क्नैपैक की समस्याएं, जिनमें सामान की एक से ज़्यादा संख्या होती है. जैसे, वज़न और वॉल्यूम. साथ ही, हर सामान की मात्रा को हिसाब से पैक किए जाने की क्षमता होती है. यहां, डाइमेंशन शब्द का मतलब यह ज़रूरी नहीं है कि लंबाई, लंबाई, और चौड़ाई के आम तौर पर इस्तेमाल किए जाने वाले जगह से जुड़े डाइमेंशन के बारे में बताया गया हो. हालांकि, कुछ समस्याओं में जगह के हिसाब से डाइमेंशन भी शामिल हो सकते हैं. जैसे, आयताकार बॉक्स को आयताकार स्टोरेज बिन में पैक करने का सबसे सही तरीका ढूंढना.
कई नैपसैक की समस्याएं, जिनमें कई क्नैपैक होते हैं. साथ ही, उनका लक्ष्य, सभी नैपसैक में पैक किए गए सामान की कुल वैल्यू को बढ़ाना होता है.
ध्यान दें कि आपको एक में कई डाइमेंशन वाली समस्या हो सकती है.
बिन-पैकिंग की समस्या
पैकिंग की सबसे आम समस्याओं में से एक bin-packing है. इसमें कई कंटेनर (जिन्हें bin-packing कहा जाता है) होते हैं और उनमें एक जैसी क्षमता होती है. एक से ज़्यादा नैपसैक की समस्या के उलट, बिन की संख्या तय नहीं होती. इसके बजाय, लक्ष्य यह है कि ऐसे बिन कम से कम रखें जिनमें सभी आइटम हों.
इस आसान से उदाहरण में, एक से ज़्यादा kSnapsack की समस्या और बिन पैकिंग की समस्या के बीच का अंतर बताया गया है. मान लीजिए कि किसी कंपनी के पास डिलीवरी के लिए ट्रक हैं, जिनमें से हर एक के वज़न की क्षमता 18,000 पाउंड है. साथ ही, सामान डिलीवर करने के लिए 1,30,000 पाउंड वज़न का सामान है.
एक से ज़्यादा कापैक: आपके पास पांच ट्रक हैं और आपको ज़्यादा से ज़्यादा वज़न वाले आइटम का सबसेट लोड करना है.
बिन पैकिंग: आपके पास 20 ट्रक हैं (सभी सामान रखने के लिए इससे ज़्यादा) और आपको कम से कम ट्रक का इस्तेमाल करना है, जिनमें ये सभी सामान रखे जा सकते हैं.
नीचे दिए गए सेक्शन में बताया गया है कि OR-टूल की मदद से पैकिंग से जुड़ी अलग-अलग तरह की समस्याओं को कैसे हल किया जाए. इसकी शुरुआत kSnapsack समस्या से होती है.